Let $ G $ be a connected graph and $ C $ be an odd-length cycle in G. Show that if $ H $ has a perfect matching, then $ G $ has a perfect matching .

Question

Let $ G $ be a connected graph and $ C $ be an odd-length cycle in G. We define graph $H$ as follows:

$$ V (H) = {{(V (G) - V (C)) ∪ {c}}}, $$ where $ c $ is a new vertex that we add arbitrarily $$ E (H) = \{E (G - C) ∪ {(c, x) | \exists v \in V(C)\ \mathrm{such\ that}\ {(v, x) ∈ E (G))}}\} $$

Show that if $ H $ has a perfect matching, then $ G $ has a perfect matching .

I'm having problems to prove this statement, I don't seem to found a perfect matching when we remove $V(C)$ and I am not sure if I'm understanding how $E(H)$ is constructed.

I think it can be solved by Tutte's theorem but I don't know how to use it to get to the right path.

Any help?

Answer 1

I don't think you need Tutte's Theorem here. First we need to establish what exactly the graph $H$ is. The vertices $V(H)$ are the vertices of $G$ minus the cycle $C$, with one vertex added in. This vertex is not arbitrary. Notice that in $E(H)$, the vertex $c$ has one edge that existed in the $G$ but does not exists in $G-C$. What you can imagine here is that you delete the cycle and all the edges incident to vertices in the cycle, then bring back one vertex and a single edge that was not in the cycle, but was deleted when you removed the cycle from $G$. Now we suppose $H$ has a perfect matching. Since the vertex $c$ has a single edge incident to it, the edge $(c,x)$ must be in the matching; if it weren't then $c$ would not be matched to an edge. The idea here is to build the matching in $G$ by taking the matching in $H$ and showing that if we pick some of the edges of the cycle, that we can 'glue' these together to get a matching in all of $G$.

First we notice that an odd cycle does not admit a perfect matching. For example, take a pentagon with vertices $\{1,2,3,4,5\}$. The 'closest thing' to a perfect matching you can make in this pentagon is to pick the edges say $(1,2)$ and $(3,4)$. Then vertex $5$ has no selected edges adjacent to it and so picking those edges is not a matching. However, if we let $c$ take the place of vertex $5$ (since it has one of the edges that vertex $5$ had), then every vertex of $G$ is in the matching with no overlaps and so we have a perfect matching. It should be easy enough to see how this generalizes to any odd cycle.