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

0 votes
0 votes

@shaktisingh

Generalized solution for this question .....since graph with n nodes can have n(n-1)/2 edges hence  total simple  graph possible for unlabeled vertices are  n(n-1)/2 +1…..(here +1 is because graph with no edges) 

example-- for 3 vertices   max  edges  can be 3*2/2=3 hence 4 graphs possible ..(graph with no edge+ graph with 1 edge +graph with 2 edge +graph with 3 edge)

Question is for upto n nodes  hence 

for upto 1  graph possible only 1

for upto 2 nodes    (1+2)

for 3 nodes (1+2+4)

for n nodes  (1+2+4+ 7+11+15+….+upto n terms)

nth term of this series =n(n-1)/2 +1

hence for n nodes

sum of this series =$n(n^{^{2}}+5)$/6… are total graphs possible

 

0 votes
0 votes
Firstly 3 nodes are here Which defines we can have C(3,2) edges are possible

Make a Set of these Edges

For each of them we have two choices Hence 2^3 ways are there

According to the Question maker He did not considered the Phi graph (Graph with No vertices)

Hence Total 7 possibilities
0 votes
0 votes

The answer is option C.

Explanation:

For node = 1 :     for node = 1, there is only one graph is possible.

For node = 2 :    for node = 2, there are two distinct graph is possible. Either two nodes are isolated or connected.

For node = 3:    for node = 3, there are four distinct graph is possible.  Lets see why four graphs are possible. If we represent a graph using adjacency matrix, then for simple graph all diagonal elements are zero. So, for 3*3 square matrix there ar 6 available choices are there. But here we want only distinct graph so the choice will 6/2=3, because  for this example, edge between (1,2) is similar  to edge between (2,1). So, there are 3 distinct graph is possible with connected edges, And one graph is possible when all  the vertices are disconnected. So total number of graph for node = 3 is (3+1)=4.

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

 = (1+2+4)=7.

Answer:

Related questions

39 votes
39 votes
8 answers
9
Kathleen asked Sep 15, 2014
17,663 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
10
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
11
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
12
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}$