Let $G=\left(V,E\right)$ be a connected graph where $\left|V\right|\,\mbox{mod}\,2\equiv0$. Denote $\nu$ to be $G$'s maximal matching (a set of disjoint edges) size and $\tau$ to be $G$'s minimal vertex cover (a set of vertices that meets all edges) size. Prove: $\tau<2\nu$.

Note: It is easy to see that $\tau\leq 2\nu$. Let $F$ be a matching of size $\nu$. Define $C=\bigcup F$ . Then $C$ is a cover of size $2\nu$

EDIT: Not to be confused with König's theorem which deals in bipartite graphs in which $\tau=\nu$.

  • $\begingroup$ where did you find this? $\endgroup$ – Jorge Fernández Hidalgo Mar 29 '13 at 17:42
  • $\begingroup$ It is part of a homework assignment in an advanced course in combinatorics that I'm taking. I've got a proof by induction pending on a lemma, but I thought I'd publish the question without my proof first to see if someone can think of a neater proof $\endgroup$ – eladidan Mar 29 '13 at 18:47

One way to prove it is to show that you can remove one vertex from $C$. First, we can remove from $G$ any non-$F$ edges that have both ends in $C$. This won't change the maximal matching (because we are removing only non-matching edges), and won't change our cover (because we will remove one vertex from $C$, so the other end will be still in $C$, I assume that $G$ does not contain loops). However, what is left are: stars and triangles (other options would imply that $F$ was not a matching of maximal size). If you have any star (a single edge from $F$ is also a star), then only one vertex from it suffices, and so you can remove the other one from $C$. If all you have left are triangles, then there has to be at least two (because $|V|$ is even) that were connected, and thus there exists an augmenting path, so $F$ was not of maximal size.

It's just a sketch, but I hope it helps ;-)

  • $\begingroup$ Very nice. Take care to notice that for the reduced graph to contain only stars, you cannot take any maximum-matching F but you can always construct such an F $\endgroup$ – eladidan Mar 31 '13 at 19:40

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.