edited by
853 views
5 votes
5 votes

How many labelled sub-graphs of $K_n$ are isomorphic to $W_{n-1}$?

(Where $K_n$ : Complete graph with $n$ vertices , $W_n$ : Wheel graph with $ n+1$ vertices)

1.$\frac{(n-1)!}{2}$

2. $\frac{(n-2)!}{2}$

3. $\frac{n!}{2(n-1)}$

4. $\frac{n!}{2(n-1)^2}$

edited by

1 Answer

2 votes
2 votes

OPTION C

In complete Graph with n vertices , each vertex has n-1 degree ,connecting to every other node.

In wheel Graph with n vertices , center vertex has n-1 degree & every other vertex has degree 3 , forming a cycle around center vertex.


For making a wheel Graph(n vertices) from Kn 

Steps - 

 1) Chose center vertex (labeled)  = nC(It can be anyone of n vertices)

 2) make a cycle of remaining n-1 vertices  = $\frac{(n-1)!}{2(n-1)}$

             (this is similar to Round-Table arrangement of (n-1) people,considering clockwise &

               anticlockwise same) 


so, Total ways =   nC * $\frac{(n-1)!}{ 2(n-1)}$  = $\frac{n!}{ 2(n-1)}$ = C(Ans)

edited by

Related questions

28 votes
28 votes
6 answers
1
go_editor asked Feb 12, 2015
12,725 views
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ isA multiple of 4EvenOddCongruent to 0 $mod$ 4...
4 votes
4 votes
1 answer
3