I'm working on a question:
Let $P_n$ be the number of perfect matchings in $K_{2n}$. Prove by mathematical induction that for each integer $n\geq1$, $P_n$ is the product of odd integers from $1$ to $2n-1$.
So far, I've come up with this:
Let $S(n)$ be the statement that the number of perfect matchings, $P_n$, in $K_{2n}$ is the product of the odd integers from $1$ to $2n-1$.
First, consider $n=1$. $K_{2\times1}$ has $1$ perfect matching, and $2\times1-1=1$ which leaves $P_1=1$. So we know $S(n)$ is true for $n=1$.
Now assume that $S(k)$ is true for some integer $k$. That is, assume that $K_{2k}$ has $P_k$ perfect matchings and that $P_k=1\times3\times…\times(2k-3)\times(2k-1)$
Now consider $S(k+1)$.
$$1\times3\times…\times(2k-1)\times(2(k+1)-1)$$
$$=1\times3\times…\times(2k-1)\times(2k+1)$$
$$=P_k\times(2k+1)\text{ (by the inductive hypothesis)}$$
$$=P_k+2kP_k$$
This is where I am stuck, as I need to show that this is equal to $P_{k+1}$. I've been trying for a few hours but am not on the right path obviously. I've messed around with looking at how many edges there are in a $K_{2n}$ graph, which is $n(2n-1)$ and then looking at what happens to that number when two new vertices are added (or $n$ is increased by $1$), which was something like $n(2n-1)+4n+1$, all in the hope of using the number of edges and vertices together to make some argument about augmenting paths, but that has gone nowhere. I've tried looking at maximal paths, but that doesn't seem to fit. I even thought up a nifty little semi-baked algorithm for finding all the perfect matchings in a complete graph, but abandoned that part-way through as it isn't helpful at all. I am suffering from a huge brain-fart. Any help with how I could move forward with this proof would be greatly appreciated. Proofs aren't my strongest point, and neither is graph theory.
Thanks for your time and patience, all!
Best Answer
Let the vertices of $K_{2k+2}$ be $v_1,v_2,\ldots, v_{2k+2}$. One idea is to partition the set of perfect matchings of $K_{2k+2}$ based on which edge incident to $v_1$ is used.
Can you count the perfect matchings of $K_{2k+2}$ that use the edge $(v_1,v_2)$? How about those that use $(v_1,v_3)$? etc.