The Gateway to Computer Science Excellence
+1 vote

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

in Graph Theory by | 172 views

1 Answer

+4 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)

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
52,345 questions
60,487 answers
95,294 users