The size of the maximum matching is bounded by the size of the minimum vertex cover

Prove, using the weak duality theorem of linear programming, that:

For any graph $G$ (not necessarily bipartite), the size of the maximum matching is at most the size of the minimum vertex cover.

I am a student doing advanced course in combinatorial and actually I do not know where to start in the proof, because this is a general graph, not a bipartite one. So hints would really appreciated. Thanks in advance.

• What are your thoughts on the problem, what have you tried? – Seirios Sep 28 '13 at 6:57
• the question is obvious, i need using weak duality theorem to prove that size of Max Matching <= Min Vertex Cover – Showen Disel Sep 28 '13 at 7:12
• Hello, welcome to Math.SE. Please read this post and the others there for information on writing a good question for this site. In particular, people will be more willing to help if you edit your question to include some motivation, and an explanation of your own attempts. – Lord_Farin Sep 28 '13 at 7:42
• I am a student doing advanced course in combinatorial and Actually i do not know where to start in the proof, because this is a general graph not bipartite. So hints would really appreciated, Thanks in advance – Showen Disel Sep 28 '13 at 8:32
• Thank you for your response. I will try to get the question reopened. – Lord_Farin Sep 28 '13 at 10:02

1 Answer

Let $G=(V,E)$ be a graph, let $M\subseteq E(G)$ be a maximum matching of the graph $G$, and let $C\subseteq V(G)$ be the minimum vertex cover of $G$. Since edges in $M$ are disjoint in the sense that no two share an endpoint, each vertex in $v\in C$ covers at most one edge in $M$. Thus $|C|\ge |M|$.

• can you give an example where the cardinality of C and M aren't equal? – Andrew Cassidy Nov 19 '15 at 17:27
• Yes: a $K_{1,4}$ with an edge added between "neighboring" vertices. In that case $|C|=1$ and $|M|=2$. – blazs Nov 19 '15 at 20:06
• thank you, but what does the symbol K mean? – Andrew Cassidy Nov 19 '15 at 20:19
• It's a star. My example is a star with 4 edges, where you add an edge between a pair of "neighboring" nonadjacent vertices. – blazs Nov 19 '15 at 20:21
• so K(1, 4) in an adjacency list is: {"center": ["1", "2", "3", "4"], "1": ["center"], "2": ["center"], "3": ["center"], "4": ["center"]}. let's add a connect between 1 and 2 which I think is what you're talking about: {"center": ["1", "2", "3", "4"], "1": ["center", "2"], "2": ["center", "1"], "3": ["center"], "4": ["center"]}. The C now is ("center", "2") or ("center", "2"). So cardinality is 2 not 1? – Andrew Cassidy Nov 19 '15 at 21:17