in Graph Theory edited by
537 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}$

in Graph Theory edited by
537 views

1 comment

Why divided by 2(n-1)?
0
0

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