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

The number of max edges a simple graph can have is $n\times (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 unlabled simple graphs on 3 nodes will be  $4$.

Similarly for two node graph we have option of $0$ or $1$ edge.

So the total number of simple graphs upto three nodes are:

$$4 + 2 + 1 = 7$$

Comments

1. What would be the answer if nodes were labelled??

2. In this question it is not given whether graph is labelled or not, then why we are assuming it to be unlabelled one

---

what does it meant ?

Similarly for two node graph we have option of 0 or 1 edge.

---

it means either we can take edge between the 2 node or not.

Answer 2

Number of graphs (labelled) possible on n vertices = $2^\frac{n(n-1)}{2}$

So, for upto 3 nodes = $1+2+8=11$

No option matches.

 

So, the question wants to know it for unlabelled. There's no formula for that, we have to do it manually.

So, by brute force: $1+2+4=7$

 

Option C

Answer 3

Minimum no of vertices required for a graph = 1

Number of distinct graphs with 1 node = 1

Number of distinct graphs with  2 nodes = 2  (one without edge and one with edge)

Number of distinct graphs with 3 nodes = 4  (Although total no of possible graphs for 3 nodes is  2 power (n(n-1)/2) = 8, but distinct are 4 as:

                                                                                1st being null graph in which there is no edge.

                                                                                2nd being graph in which there is 1 edge.

                                                                               3rd being graph in which there are 2 edges.

                                                                               4th being graph in which there are 3 edges.)

So total no of distinct graphs upto 3 nodes = 1 + 2 + 4 = 7.

But this is with the assumption that the nodes are unlabelled.

Had they been labelled, the answer would have been 1 + 2 + 8 =11 and this is not in the option and hence our assumption is correct.

Answer 4

ans should be 11:

here they said upto three three nodes means we have |V|=1, or |V|=2,  or |V|=3

here total possible graph are 11

Comments

you are counting "labeled" graph. but in the question I guess they didn't ask number of labeled graphs. so 11 option is not there.

---

you are right, if it is unlabelled then only we can say ans is 7. they have not mentioned anything in the question. but from options we have to go by unlabelled only. agree with you. thanks.