The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
236 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}$

in Graph Theory by Boss (13.4k points)
edited by | 236 views
0
Why divided by 2(n-1)?

1 Answer

+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.5k points)
edited by

Related questions

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
49,832 questions
54,800 answers
189,505 comments
80,726 users