4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What are your thoughts on the problem, what have you tried? $\endgroup$ – Seirios Sep 28 '13 at 6:57
  • $\begingroup$ the question is obvious, i need using weak duality theorem to prove that size of Max Matching <= Min Vertex Cover $\endgroup$ – Showen Disel Sep 28 '13 at 7:12
  • $\begingroup$ 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. $\endgroup$ – Lord_Farin Sep 28 '13 at 7:42
  • 3
    $\begingroup$ 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 $\endgroup$ – Showen Disel Sep 28 '13 at 8:32
  • 1
    $\begingroup$ Thank you for your response. I will try to get the question reopened. $\endgroup$ – Lord_Farin Sep 28 '13 at 10:02
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ can you give an example where the cardinality of C and M aren't equal? $\endgroup$ – Andrew Cassidy Nov 19 '15 at 17:27
  • $\begingroup$ Yes: a $K_{1,4}$ with an edge added between "neighboring" vertices. In that case $|C|=1$ and $|M|=2$. $\endgroup$ – blazs Nov 19 '15 at 20:06
  • $\begingroup$ thank you, but what does the symbol K mean? $\endgroup$ – Andrew Cassidy Nov 19 '15 at 20:19
  • $\begingroup$ It's a star. My example is a star with 4 edges, where you add an edge between a pair of "neighboring" nonadjacent vertices. $\endgroup$ – blazs Nov 19 '15 at 20:21
  • $\begingroup$ 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? $\endgroup$ – Andrew Cassidy Nov 19 '15 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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