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'$.


2 Answers 2


$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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.