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'$.
 A: $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'$.
As you've shown, the theorem is false if we consider maximal matchings (matchings we cannot add any edge to) rather than maximum matchings (matchings of the largest possible cardinality). I apologize for the terminology; it is well-established but terrible.
A: I wanted to confirm if this proof is correct:
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.
