# 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

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