Want to find the number of perfect matching in a complete graph K2n where 2n is the number of vertices:
Came up with the following method -
1. Counting Edges>Total no. of edges = C(2n,2), Choose 1 edge in C(2n,2) ways.
>Remaining no. of edges C(2n-2,2). (Since 2 vertices already selected.
>So, no. of ways of choosing 2 edges = C(2n,2)*C(2n-2,2).
>Total ways of choosing edges -> C(2n,2)*C(2n-2,2)*..*C(2,2)
> => ((2n)!)/(2^n) *(Note: Missing n! in denominator)*
Referred - How to find the number of perfect matchings in complete graphs?. My understanding(and doubts) for this method is given below:
2. Counting with Vertices>Choose a vertex. Choose another vertex (part of same edge): 2n-1 ways.*(Why no. of ways of selecting first vertex not considered??)*
>Choose next vertex. Choose the pair vertex (part of same edge): 2n-3 ways.
>So end result - (2n-1)*(2n-3)*..*(3)*(1) (Product of all odd numbers less than 2n)
>Simplification gives -> ((2n)!)/((2^n)*n!)
The 1st and 2nd method essentially becomes the same if in the 2nd method I consider no. of ways of choosing the first vertex in a pair and also divides each pair selection by 2! (since order of choosing vertices in each pair doesn't matter)
1.What am I missing in the 1st method? 2.Why number of ways of choosing the starting vertex not considered when selecting each pair of vertices in 2nd method?