retagged by
34,433 views
76 votes
76 votes

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

  1. $15$
  2. $10$
  3. $7$
  4. $9$
retagged by

12 Answers

Best answer
123 votes
123 votes

Answer is (C)

edited by
52 votes
52 votes
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.$
38 votes
38 votes
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)
edited by
14 votes
14 votes
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$$.
edited by
Answer:

Related questions

39 votes
39 votes
8 answers
1
Kathleen asked Sep 15, 2014
17,664 views
The maximum number of edges in a $n$-node undirected graph without self loops is$n^2$$\frac{n(n-1)}{2}$$n-1$$\frac{(n+1)(n)}{2}$
19 votes
19 votes
3 answers
2
Kathleen asked Oct 4, 2014
7,978 views
The number of edges in a regular graph of degree $d$ and $n$ vertices is ____________
8 votes
8 votes
1 answer
3
go_editor asked Jun 13, 2016
3,961 views
Consider the graph shown in the figure below:Which of the following is a valid strong component?$a, c, d$$a, b, d$$b, c, d$$a, b, c$
26 votes
26 votes
5 answers
4
Kathleen asked Oct 4, 2014
9,905 views
The number of substrings (of all lengths inclusive) that can be formed from a character string of length $n$ is$n$$n^2$$\frac{n(n-1)}{2}$$\frac{n(n+1)}{2}$