16 votes 16 votes Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..? Graph Theory discrete-mathematics graph-theory graph-matching + – dhingrak asked Dec 2, 2014 edited Oct 9, 2023 by Hira Thakur dhingrak 10.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 17 votes 17 votes 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! )}$ jayendra answered Dec 5, 2014 edited Dec 24, 2017 by krish__ jayendra comment Share Follow See all 2 Comments See all 2 2 Comments reply Himanshu1 commented Jan 1, 2016 reply Follow Share explain how K2n=( 2n! ) / ( 2^n * n! ) 2 votes 2 votes krish__ commented Dec 24, 2017 reply Follow Share \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} 7 votes 7 votes Please log in or register to add a comment.
15 votes 15 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). Akash Kanase answered Dec 3, 2015 Akash Kanase comment Share Follow See all 0 reply Please log in or register to add a comment.