Talk:Matching polytope
Appearance
![]() | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
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 given by in that order along the path. Clearly this is a feasible solution but it is not possible to subtract an from the very last edge without violating . 81.221.145.119 (talk) 17:11, 21 November 2020 (UTC) Henrik Laxhuber
- 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)
- A fix could be to only modify those vertices reachable from 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 () 1 due to . 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