1,288 views

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}$

### 1 comment

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

For six vertices = 2^15

Option A is correct

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}$

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
by

For six vertices = 2^15

1 vote