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