The Gateway to Computer Science Excellence
+1 vote
109 views

Number of perfect matching in W(n>=4 and n is even) _________.

in Graph Theory by (111 points) | 109 views

1 Answer

+3 votes
Perfect Matching means degree of every vertex is 1

No perfect matching  exist for wheel graph when no.of vertices are odd ( think about it )

In a wheel graph with n vertices(even), there are n-1 vertices in cycle and one wheel vertex connected to remaining all vertices.

For matching that wheel vertex , we have n-1 vertices===> possibilities are n-1

Remaining n-2 (even) matched with other neighbour ===> only one possibility.

 

Total possibilities = (n-1)*1 = (n-1)
by Veteran (64.7k points)

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
50,647 questions
56,497 answers
195,494 comments
100,826 users