Talk:Matching polytope

The proof https://en.wikipedia.org/wiki/Matching_polytope#Proof_using_the_definition_of_extreme_points does not appear to be correct. Consider a path of 4 vertices with $x_{e}$ given by ${\frac {1}{2}},{\frac {1}{2}},0$ in that order along the path. Clearly this is a feasible solution but it is not possible to subtract an $\epsilon >0$ from the very last edge without violating $\mathbf {0} \leq \mathbf {x}$ . 81.221.145.119 (talk) 17:11, 21 November 2020 (UTC) Henrik Laxhuber[reply]

You are right, the proof is incomplete. I removed it until I (or someone else) finds a way to fix it. --Erel Segal (talk) 21:36, 21 November 2020 (UTC)[reply]

A fix could be to only modify those vertices reachable from

x_{e}

without going through an edge of integral weight. It should be possible to show that none of these edges are adjacent to an edge of weight (

x_{u}

) 1 due to

\mathbf {A_{G}x\leq 1}

. The idea carries over also to the bipartite vertex cover polytope, where it should be possible to show that none of the fractional vertices are adjacent to a vertex of zero weight. --81.221.145.119 (talk) 08:20, 22 November 2020 (UTC) Henrik Laxhuber[reply]