<p>In this document <a href="https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf" rel="nofollow noreferrer">https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf</a>
they prove the integrality of the matching polytope using the integrality of the perfect matching polytope.</p>
<p>The only part I don't understand is on page 4-5, when they claim that <span class="math-container">$\tilde x(\tilde \delta(U)) \geq \tilde x(\tilde \delta(X' \setminus W')) + \tilde x(\tilde \delta(W \setminus X))$</span>. I don't understand why this doesn't hold with equality, since the values on copied edges in the duplicated graph are identical.</p>
<p>Can someone clarify this proof? Is it a mistake?</p>

CC BY-SA 4.0
2020-07-20T22:42:42.647Z
It is my notes that are based on Schrijver's book. You can of course look at Schrijver's book. I don't recall the details now but even if it is an equality the proof goes through, right?
Chandra Chekuri
CC BY-SA 4.0
2020-07-21T06:20:32.393Z
Yes, the proof would go through if it were an equality. In Schrijver's book on pg. 440, he proves the integrality of the matching polytope and states this inequality without proof. So the evidence points to it being an inequality.
Karagounis Z
CC BY-SA 4.0
2020-07-21T06:23:21.187Z
I've tried to follow your proof but I can't understand what $\delta(E[A, W \setminus X])$ means. How you can take the delta of a set of edges?
Karagounis Z
CC BY-SA 4.0
2020-07-23T16:40:49.620Z
It is a typo. There should not be a $\delta$ in $\delta(E[A,W\setminus X])$ - it should simply be $E[A,W\setminus X]$ which is the set of edges with one end point in $A$ and the other in $W \setminus X$.
Chandra Chekuri
CC BY-SA 4.0
2020-07-24T05:55:28.647Z
Thank you for clarifying that
Karagounis Z
<graph-theory><optimization><linear-programming><matching><integer-programming>
Is the matching polytope integral?
Karagounis Z
# Is the matching polytope integral?

(Asked by: username_0 on 2020-07-20)

In this document <https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf>
they prove the integrality of the matching polytope using the integrality of the perfect matching polytope.

The only part I don't understand is on page 4-5, when they claim that $\tilde x(\tilde \delta(U)) \geq \tilde x(\tilde \delta(X' \setminus W')) + \tilde x(\tilde \delta(W \setminus X))$. I don't understand why this doesn't hold with equality, since the values on copied edges in the duplicated graph are identical.

Can someone clarify this proof? Is it a mistake?

**Tags:** graph-theory, optimization, linear-programming, matching, integer-programming
> **Comments:**
> **username_1**: It is my notes that are based on Schrijver's book. You can of course look at Schrijver's book. I don't recall the details now but even if it is an equality the proof goes through, right?  
> **username_0**: Yes, the proof would go through if it were an equality. In Schrijver's book on pg. 440, he proves the integrality of the matching polytope and states this inequality without proof. So the evidence points to it being an inequality.  
> **username_0**: I've tried to follow your proof but I can't understand what $\delta(E[A, W \setminus X])$ means. How you can take the delta of a set of edges?  
> **username_1**: It is a typo. There should not be a $\delta$ in $\delta(E[A,W\setminus X])$ - it should simply be $E[A,W\setminus X]$ which is the set of edges with one end point in $A$ and the other in $W \setminus X$.  
> **username_0**: Thank you for clarifying that  

---

## 0 answers

