graph theorymatching-theory
Statement: If a graph has more than one perfect matchings, then it has an even cycle.
I was trying to prove this result. My try:
Let $M$ and $M'$ be two perfect matchings in graph $G$. Symmetric difference of $M$ and $M'$ consists of vertices of degrees 0 or 2. Therefore components of the symmetric difference are either isolated vertices or cycles.
But I am stuck here. How do I prove that at least one of those cycles must be an even cycle?
Any help. Thank You.
First, why the claim is true. Take any vertex. If it's matches to the same vertex in both perfect matching, then it had degree zero on the symmetric difference. Otherwise it has degree two.
Second, after removing all isolated vertices in the symmetric difference, all vertices have degree two. Take any such vertex and follow its two edges. What you get is a growing path that eventually closed to a cycle since the graph is finite.
Since trees have no cycles, this implies that any two perfect matching are equal, by consisting their symmetric difference.
A different proof is by induction. The idea is that every leaf must be matched to its unique neighbor.
Here is an example of a $4$-regular, $2$-edge-connected graph with $30$ vertices and no perfect matching, taken from this paper:
The proof that there is no perfect matching is straightforward, Tutte's theorem style: each of the middle vertices can be matched to only one of the outer components, and the other two are left to fend for themselves with an odd number of vertices.
This picture generalizes similarly to how you generalized the bridgeless cubic construction to a $k$-regular construction for odd $k$. In fact, the above graph is slightly more complex than it has to be, because it's planar, which you didn't ask for. The generalization can just have $k-2$ vertices in the center and $k$ petals, each with a single edge to each of the vertices in the center $(k-2)$ edges total.
Then, of course, you need the petals to be $(k-2)$-edge-connected, nearly-$k$-regular graphs (with $k-2$ vertices of degree $k-1$, the remainder of degree $k$) on an odd number of vertices, but that shouldn't be hard. For example, let a petal be made up of three vertex sets $A$, $B$, $C$ of size $k-2$, $k-1$, $2$, respectively: $2k-1$ vertices in total. Each vertex in $A$ is adjacent to each vertex in $B$ - and the vertices in $A$ will also be connected to the center. Each vertex in $B$ is also adjacent to each vertex in $C$, bringing their degree up to $k$; finally, the two vertices in $C$ are adjacent to each other.
The entire graph has $k(2k-1)+(k-2) = 2k^2-2$ vertices, which is an even number.
Best Answer
Firstly, don't forget to show that there must be some degree 2 vertices in that symmetric difference, and hence at least one cycle.
Lastly, show that the edges of any such cycle must alternate between $M$ and $M'$, making it even length.