in Graph Theory retagged by
1,288 views
3 votes
3 votes

Total number of simple graphs that can be drawn using six vertices are:

  1. $2^{15}$
  2. $2^{14}$
  3. $2^{13}$
  4. $2^{12}$
in Graph Theory retagged by
1.3k views

1 comment

No of simple graph = 2^ (n(n-1)/2)

       For six vertices = 2^15

Option A is correct
2
2

3 Answers

2 votes
2 votes

A graph with no loops and no parallel edges is called a simple graph.

  • The maximum number of edges possible in a single graph with ‘n’ vertices is $ nC_{2}$ where $nC_{2} = n(n – 1)/2$.

  • The number of simple graphs possible with ‘n’ vertices =$ 2^{nc_{2}} = 2^{n(n-1)/2}.$

graph with no edge=$\binom{n(n-1)/2)}{0}$

graph with 1 edge=$\binom{n(n-1)/2)}{1}$

graph with 2 edge=$\binom{n(n-1)/2)}{2}$

graph with 3 edge=$\binom{n(n-1)/2)}{3}$

.

.

.

.

graph with $n(n-1)/2$ edge=$\binom{n(n-1)/2)}{n(n-1/2}$

So total number of graph possible=$\binom{n(n-1)/2)}{0}$+$\binom{n(n-1)/2)}{1}$+$\binom{n(n-1)/2)}{2}$+....+$\binom{n(n-1)/2)}{n(n-1/2}$=$2^{n(n-1)/2}$

 

=$2^{n(n-1)/2}$

=$2^{6(6-1)/2}$

=$2^{6*5/2}$

=$2^{15}$

 

0 votes
0 votes
With n vertex we have max of $\frac{n*(n-1)}{2}$ edges. (i.e complete graph)  => we have max 15 edges

Now for each edge we have two possibility , It can be included in graph or not included in the graph

So 2 * 2 * 2 ….* 2  15 times => $2^{15}$ possible simple graph
0 votes
0 votes
Option A is right Answer

For six vertices = 2^15
Answer:

Related questions