NIELIT 2017 DEC Scientific Assistant A - Section B: 20

Question

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

• A. $2^{15}$
• B. $2^{14}$
• C. $2^{13}$
• D. $2^{12}$

Comments

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

       For six vertices = 2^15

Option A is correct

Answer 1

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

 

Answer 2

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

Answer 3

Option A is right Answer

For six vertices = 2^15