Graph theory

Question

How many simple graph are possible on six  vertices in which the number of edge is odd??

Comments

i think -1 is not required.

---

yep, it should be 2$^{14}$

---

It is 2¹⁴

same as ¹⁵C₁ + ¹⁵C₃ + ¹⁵C₅ + ¹⁵C₇ + ¹⁵C₉+ ¹⁵C₁₁+ ¹⁵C₁₃+ ¹⁵C₁₅

Answer 1

Option A

Number of graph = 2^n(n-1)/2

2^30/2=2^15

Comments

Where is option A?
And asking number of graphs with odd no. edges

READ PROPERLY

Answer 2

Actually, the question should be: simple graphs are possible on six labeled vertices in which the number of edges is 'odd'.

Answer: we can do with recurrence method

for n=3 , no. of simple graphs are possible = 2^(3C2)= 2^3 =8  // [maximum edges with n vertices in simple graph: n(n-1)/2= 3*2/2 = 3]

Now, as @Mk Utkarsh solved, we can calculate no. of simple graphs with odd edges like:

C(3,1)+C(3,3)= 3+1= 4  // [this is combination form]    // 2^2  ( 2^3 /2 )

 

for n=4 , no. of simple graphs are possible = 2^(4C2)= 2^6 =64

Now, we can calculate no. of simple graphs with odd edges( Total edges =6) like:

C(6,1)+C(6,3)+C(6,5) = 6+20+6= 32    // ( 2^6 / 2  = 2^6-1 = 2^5 =32)

 

for n=5 , no. of simple graphs are possible = 2^(5C2)= 2^10 =1024

Now, we can calculate no. of simple graphs with odd edges( Total edges =10) like:

C(10,1)+C(10,3)+C(10,5)+C(10,7)+C(10,9) = 10+120+252+120+10= 512  // (2^10-1 = 2^9 =512)

 

NOW, YOU CAN SEE THAT SIMPLE GRAPHS WITH ODD NO. OF EDGES OVER 'n' VERTICES ARE:

=[ 2^(nC2) ] / 2 .

Now put n=6

no. of simple graphs with odd no. of edges over 6 vertices = [2^(6C2)] /2

= (2^15) / 2

= 2^14 graphs