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

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

---

Suppose if 11 and 7 both given in option, then what option we have to choose?

---

why are half of answers here making up a new concept of "vertex-less graph"? That's not even a thing in gate. Only edge-less graphs are okay to consider.

Answer 1

Answer is (C)

Comments

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.

---

 

For n vertices, minimum number of edges = 0, maximum number of edges = nC2

For n = 1, edge count 1

For n = 2 edge count from 0 to 1 = 2

For n = 3 edge count from 0 to 3 = 4

answer = 1 + 2 + 4 = 7

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

@Rajarshi Sarkar @pavansan why not it's like (2) ^3C2 .Because those 3C2 edges can be either present or not.So,everyedge has 2 possibilties?

---

@Tejaswee_Bommaluleni first of all it's written that upto 3 nodes meaning we are going to take number of nodes from 1 to 3(not 0 as standard resources usually say that empty graph is an edgeless graph but not empty vertex set)

now if we take (2)^(3C2) means that we are considering labeled graph and finding different possible ways to make graph out of those 3 nodes only, but if we think about unlabeled nodes than few of these combination become isomorphic so we won't (and can't) count them distinct ofcourse.

now you might wonder why unlabeled nodes; It’s a matter of default assumption in the language of graph theory.

now u may revisit the best ans, hope u understood

---

Thank You @Sanskar Chouhan

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.

Answer 5

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

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.

---

This approach is good but you should also,for 3 nodes if we have max 3 edges then 4 possible graph, and for 2 nodes max edge is 2 then 2 possible graph and for 1 node  then 1 possible graph.total =4+2+1.

Answer 6

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