251 views

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 | 251 views
0
Why divided by 2(n-1)?

+1 vote

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)

by Boss (15.9k points)
edited