in Graph Theory
417 views
1 vote
1 vote

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

in Graph Theory
417 views

1 Answer

5 votes
5 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)