GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
606 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)   | 606 views

2 Answers

+6 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.7k points)  
selected by

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

+2 votes
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.5k points)  

Related questions

0 votes
1 answer
1
+1 vote
2 answers
2
asked in Graph Theory by shikharV Boss (5.2k points)   | 220 views


Top Users Jun 2017
  1. Bikram

    3704 Points

  2. Hemant Parihar

    1484 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1408 Points

  5. Niraj Singh 2

    1311 Points

  6. Rupendra Choudhary

    1194 Points

  7. rahul sharma 5

    1132 Points

  8. Debashish Deka

    994 Points

  9. srestha

    932 Points

  10. Arjun

    930 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1960 Points

  2. Niraj Singh 2

    1306 Points

  3. junaid ahmad

    502 Points

  4. sudsho

    410 Points

  5. akankshadewangan24

    388 Points


23,355 questions
30,066 answers
67,371 comments
28,382 users