GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
412 views

Is there a way to find no of perfect matchings in a complete graph Kwhere n could be either even or odd..?

asked in Graph Theory by Active (1.4k points)   | 412 views

2 Answers

+4 votes
Best answer

if n is odd then perfect matching 0. because in perfect matching degree of each vertex must be 1, which is not possible if n is odd.

and if n is even then num of perfect matching in K2n=( 2n! ) / ( 2^n  *  n! )

answered by Boss (7.6k points)  
selected by

explain how  K2n=( 2n! ) / ( 2^n  *  n! )

+1 vote
For Kn

if n is odd , then there is no perfect matching.

n is even then you can count it like ->

(n-1) (n-3) (n-5)...1 (This will end in 1 as n is even).
answered by Veteran (41.2k points)  

Related questions

+1 vote
2 answers
1
asked in Graph Theory by shikharV Boss (5.1k points)   | 181 views
+3 votes
2 answers
2
Top Users Feb 2017
  1. Arjun

    5224 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. Debashish Deka

    2356 Points

  6. sriv_shubham

    2298 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1654 Points

  10. mcjoshi

    1628 Points

Monthly Topper: Rs. 500 gift card

20,832 questions
25,989 answers
59,623 comments
22,046 users