# Maximality of matching after contracting an odd cycle in a graph

Let $$M$$ be a matching in a graph $$G$$ and let $$C$$ be a cycle in $$G$$ of length $$2k+1$$ for some integer $$k \geq 1$$. Suppose $$C$$ contains exactly $$k$$ edges of $$M$$, and has one vertex $$x$$ that is not incident with an edge of $$M$$. Prove that $$M$$ is maximum in $$G$$ if and only if $$M'$$ is maximum in $$G'$$, where $$M' = M \backslash E(C)$$ and $$G'$$ is the graph obtained from $$G$$ by contracting the edges of $$C$$.

I wanted to confirm if this statement correct since I seem to have come up with a counterexample. We can take $$C$$ to be a triangle (3-cycle) and add an extra edge $$e$$ to the triangle to get $$G$$. We can then take $$M$$ to be any one of the two edges connected to $$e$$ so that the ocnditions of the theorem are satisfied. But this gives $$G' = e$$ and $$M'$$ is the empty graph which is clearly not maximal in $$G'$$.

$$M$$ is not a maximum matching; your graph has a matching of size $$2$$ (take $$e$$ and the edge of $$C$$ opposite $$e$$) and $$M$$ has only size $$1$$. So it's fine that $$M'$$ is not a maximum matching in $$G'$$.
For the forward direction, first suppose that $$M'$$ is not maximum in $$G'$$, that is there is a matching $$N$$ such that $$N$$ has more edges than $$M'$$. We can easily find a matching of $$G$$ larger than $$M$$ by appending $$k$$ edges from $$C$$.
Conversely, suppose that $$M$$ is not maximal in $$G$$ meaning there is a matching $$N$$ of $$G$$ that is larger than $$M$$. When $$C$$ is contracted the resulting matching $$N \backslash E(C)$$ has more edges than $$M'$$, contradicting the maximality of $$M'$$ as desired.
I didn't really use the existence of $$x$$, and furthermore, I'm asked to show next $$x$$ is necessary which I'm struggling with.