Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Balinski's theorem
open-in-new
<h2 id="balinskis-proof">Balinski's proof</h2> <p>Balinski proves the result based on the correctness of the <a href="/facts/Simplex_method/9fndF6cq">simplex method</a> for finding the minimum or maximum of a linear function on a convex polytope (the <a href="/facts/Linear_programming/GduXFQxT">linear programming</a> problem). The simplex method starts at an arbitrary vertex of the polytope and repeatedly moves towards an adjacent vertex that improves the function value; when no improvement can be made, the optimal function value has been reached. </p><p>If <i>S</i> is a set of fewer than <i>d</i> vertices to be removed from the graph of the polytope, Balinski adds one more vertex <i>v</i>0 to <i>S</i> and finds a linear function ƒ that has the value zero on the augmented set but is not identically zero on the whole space. Then, any remaining vertex at which ƒ is non-negative (including <i>v</i>0) can be connected by simplex steps to the vertex with the maximum value of ƒ, while any remaining vertex at which ƒ is non-positive (again including <i>v</i>0) can be similarly connected to the vertex with the minimum value of ƒ. Therefore, the entire remaining graph is connected. </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Ziegler, Günter M. (2007) [1995], "§3.5: Balinski's Theorem: The Graph is d-Connected", Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, p. 95–, ISBN 978-0-387-94365-7. <a href="978-0-387-94365-7" target="_blank">978-0-387-94365-7</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Balinski, M. L. (1961), "On the graph structure of convex polyhedra in n-space", Pacific Journal of Mathematics, 11 (2): 431–434, doi:10.2140/pjm.1961.11.431, MR 0126765. <a href="/wiki/Michel_Balinski" target="_blank">/wiki/Michel_Balinski</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Steinitz, E. (1922), "Polyeder und Raumeinteilungen", Encyclopädie der mathematischen Wissenschaften, Band 3 (Geometries), pp. 1–139. <a href="/wiki/Ernst_Steinitz" target="_blank">/wiki/Ernst_Steinitz</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>