The Gateway to Computer Science Excellence
+3 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)


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

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

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

in Graph Theory by Boss (13.6k points)
edited by | 251 views
Why divided by 2(n-1)?

1 Answer

+1 vote


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 by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,241 answers
104,601 users