Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 1

up vote 1 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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