The Gateway to Computer Science Excellence
+10 votes
3.1k views

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

in Graph Theory by Active (1k points) | 3.1k views

2 Answers

+14 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 $K_{2n}=\dfrac{(2n!)}{( 2^n  *  n! )}$
by Loyal (8.1k points)
edited by
+2

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

+5
\begin{align} \#\text{Perfect matchings of $K_{2n}$} &= (2n-1)(2n-3)(2n-5)\cdots 5.3.1\\ &=\dfrac{(2n)(2n-1)(2n-2)(2n-3)\cdots 5.4.3.2.1}{(2n)(2n-2)\cdots4.2}\\ &=\dfrac{(2n)!}{(2*n)(2*(n-1))\cdots(2*2)(2*1)}\\ &= \bbox[yellow,5px,border: 2px solid red]{\dfrac{(2n)!}{2^n\times n!}} \end{align}
+12 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).
by Boss (41.5k points)

Related questions

+1 vote
2 answers
1
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,490 answers
195,432 comments
100,658 users