# Bounding minimal cover with maximal matching in connected graph

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

-
where did you find this? –  Jorge Fernández Mar 29 '13 at 17:42
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 –  eladidan Mar 29 '13 at 18:47

## 1 Answer

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 ;-)

-
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 –  eladidan Mar 31 '13 at 19:40