GATE CSE 1994 | Question: 1.6, ISRO2008-29

Question

The number of distinct simple graphs with up to three nodes is

• A. $15$
• B. $10$
• C. $7$
• D. $9$

Comments

They have played with words quite well up to should be in bold

---

@rupesh17 Your Generalized solution is not correct. For 4 unlabeled vertices we have 11 simple graphs (not 7). See below references.

https://mathworld.wolfram.com/SimpleGraph.html

https://garsia.math.yorku.ca/~zabrocki/math3260w03/nall.html

 

As per my current understanding no general solution for unlabeled vertices simple graph.If anyone knows please comment.

 

---

I guess instead of 15, it should be 16 in the series. Thank you for your answer..!

Answer 1

Answer is (C)

Comments

best explanation

---

why have we considered unlabelled vertices?

---

I had the same doubt. If you try with labeled upto 3 nodes:-

1 node =1

2 node =2

3 node = 8

1+2+8=11

Which is not in option

---

What about null graph ? If 8 is in the option, I think that we have to go with 8.

---

its upto 3 nodes, why have we not considered null graph, null graph is also a simple graph?

---

do you know what is null graph?

---

Edge less graph are called Null graph.

But where it is mentioned that we have to take unlabelled graph.

---

Shubhanshu where it is mentioned we need to take labeled graph?

and Rajesh R if 8 was in option still 7 is the correct answer because a null graph(a graph without any vertices) is not considered a simple graph. 

---

@Mk Utkarsh 

 a null graph(a graph without any vertices) is not considered a simple graph. 

Can you provide a reference to this statement. 

---

I was wrong

http://oeis.org/A005470/list

here the list mentions graph with no vertex so yeah we can say that 8 is the answer.

---

Thanks :)

---

There is no standard definition of Null Graph. Null Graph may refer to a graph in which set of vertices and edges both are empty or it may also refer to a graph(also called an empty graph or edgeless graph) in which set of vertices is a non-empty set but set of edges is an empty set.

So, here for this question , answer can be (7) or (8) but mostly resources consider edgeless graphs as null graphs if $n$ $\geqslant$ $1$.

http://mathworld.wolfram.com/EmptyGraph.html

http://mathworld.wolfram.com/NullGraph.html

https://en.wikipedia.org/wiki/Null_graph

https://math.stackexchange.com/questions/1196921/is-there-any-difference-between-empty-graph-and-null-graph

 

 

 

---

@amar can we take disconnected graphs also??

---

best explaination bro..

---

Can we generalize it as $2^{n}-1$ or not ?

---

rahul sharma 5 Why number of 1 node graph with 3 labeled vertices =1?

It should be 3, as each vertex is uniquely labeled.

similarly why 2 node graph with 3 labeled vertices =2

we have to choose 2 nodes from 3, so 3 ways

and then we can have 0 or 1 edge, so 2 possibility

hence total number of 2 node graph with 3 labeled vertices =3*2=6

---

shashank023 because when it is not mentioned to consider graph as labeled, by default we consider it as unlabeled. 

---

I’m asking that if it was mentioned that graph is labeled then what will be the ans.

---

what to write if 7 and 8 both are in the options?

---

no of simple graph with n nodes = ${2}^{\binom{n}{2}}$.

---

@Deepak Poonia Sir I why null graph is not considered for answer of this question and it was not mentioned that graph is labelled or unlabelled.

---

Null graph(or Empty graph or Edgeless graph) is a graph with At Least One Vertex & No Edge.

Every graph must have At Least 1 Vertex. MOST of the authors don’t consider graphs with No vertex. MOST authors define graph to have at least one vertex.

In this question, if you assume that Vertices are labeled then answer will be $ 1 + 2 + 8 = 11 ,$ which is Not in the options, So, we answer according to Unlabeled.

---

@Deepak Poonia Sir 

Source wikipedia:-

“

In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").

”

---

@abir_banerjee 

Also from Wikipedia:

"Some authors exclude K0 from consideration as a graph (either by definition, or more simply as a matter of convenience). Whether including K0 as a valid graph is useful depends on context."

Same thing I told in previous message. 

Half-reading is misleading & dangerous. 

IIT, IISc, NPTEL professors consider graphs to have at least one vertex. You can follow that. 

---

This is a screenshot from the very famous graph theory book by Reinhard Diestel, often called as "Diestel's graph theory book" which is considered as a standard textbook and followed by many people all over the world.
Now,  we can see vertex set can be empty and according to this 8 should be the correct answer provided graph is unlabeled. So,”theoretically” both 7 and 8 are the "possible" answers for an unlabeled graph. It should not be like that: 7 is correct and 8 is not correct though it is another case that $8$ is not given as the option.

To avoid ambiguity in the questions, it would be very helpful if more details would be added in the questions. It might create long questions but chances of ambiguity will be less.

Graph Theory is considered as a young subject and so, terms should be properly defined in the question. For example, a complete graph is defined as a graph whose vertices are pairwise adjacent, while a clique is a set of pairwise adjacent vertices in a graph. Many authors use the terms interchangeably. And, there are other examples too. So, to avoid ambiguity, it would be much helpful if things are defined properly and as much as details should be added in the question.  

---

@ankitgupta.1729

That’s well written.

It depends on the author whether they allow empty vertex set or not in the graph definition. Particularly, in IISc CSA Graph Theory course also, Diestel is followed, But Prof doesn’t allow empty vertex set in the definition of Graph.

Conclusion: 7, 8 both are correct answers, But since 8 is Not given in the options, so, 7 is unambiguously correct answer.

Answer 2

Answer: C

The number of max edges a simple graph can have is $\frac{n×(n−1)}{2}$.

So, for a graph with $3$ nodes the max number of edges is $3.$
Now there can be $0$ edges, $1$ edge, $2$ edges or $3$ edges in a $3$ node simple graph.
So the total number of unlabeled simple graphs on $3$ nodes will be  $4.$
Similarly for two node graph we have option of $0$ or $1$ edge and for one node graph we have option of $0$ edge.
So the total number of simple graphs upto three nodes $=4+2+1=7.$

Comments

can i say it is $2^n - 1$?

---

Sourabh Kumar according to this http://oeis.org/A005470/list 8 is the answer

---

No you cannot Generalize 2^n−1.

As Up to 4 nodes Answer will be ,

Up to 3 nodes= 8 + for 4 nodes= 11,

So 8+11=19.

Answer 3

With n number of nodes, max edges are possible $\frac{n(n-1)}{2}$ in a simple graph. each edge has two choices, it'll be taken in a graph or it won't be taken. so total no of graphs are possible
$2^{\frac{n(n-1)}{2}}$.
in the question, it is asked upto three nodes:
with 1 node total graph possible = 1
with two nodes graph possible = 2
with three nodes, possible graphs= $2^{\frac{3(3-1)}{2}}  = 2^3 = 8$   but there are 3 non distinct graphs which are isomorphic to each other, so with n=3 nodes total graphs possible = 8 but total unique graph possible = 4

upto 3 nodes $1 + 2 +4 = 7 $hence answer is (C)

Comments

in 7,you have not counted null graph? why?

total unique graph means?

---

" but there are 3 non distinct graphs which are isomorphic to each other, so with n=3 nodes total graphs possible = 8 but total unique graph possible = 4"

did not understand this part

 

---

Good explanation, here if we take labeled nodes then answer is 11 which is not in the option so go with the 7 because if we take unlabeled nodes then 7 simple graphs will be possible.

Answer 4

A graph is an ordered pair (V,E). So, given a set V, graph will be different if E is different. Lets see how many different E we can get when |V| = 3.

For |V| = 3, we can have |E| = 0, 1, 2 or 3. So, 4 possible graphs.

Now, the question asks for |V| upto 3. So, we have to consider |V| = 2 and |V| = 1 also. When |V| = 2, we can have |E| = 1 or 0, so 2 possibilities. For |V| = 1, |E| can be only 0 and hence only one possibility.  So, total number of possibilities is $$4 + 2 + 1  = 7$$.

Comments

this won't work, having an edge on one node means there is some other node with one edge also.

---

Yes. That was a bad mistake. I have corrected it now.