Balinskys teorem är ett påstående om grafstrukturen för en polyeder med dimension 3 och högre. Satsen säger att om en oriktad graf bildas från hörnen och kanterna på en konvex d -dimensionell polyeder (dess skelett ), så är den resulterande grafen åtminstone vertex - d -ansluten - vilket tar bort alla uppsättningar av d − 1 hörn lämnar en ansluten subgraf. Till exempel, för en 3D-polyeder, om du tar bort två hörn (tillsammans med deras infallande kanter), för vilket par av hörn som helst finns det en väg som förbinder detta par [1] .
Balinskys sats är uppkallad efter matematikern Michel Balinsky , som publicerade beviset 1961 [2] , även om beviset för det tredimensionella fallet härrör från tidigt 1900-tal ( Steinitzs teorem att graferna för tredimensionella polytoper är exakt trekopplade plana grafer [3] ).
Balinsky bevisade sitt resultat baserat på riktigheten av simplexmetoden för att hitta minimum eller maximum av en linjär funktion på en konvex polyeder (ett linjärt programmeringsproblem ) . Simplexmetoden startar vid ett godtyckligt hörn av polyedern och flyttas iterativt till en intilliggande vertex med en förbättring i värde. Om de inte hittade en förbättring nådde de det optimala värdet av funktionen.
Om en uppsättning med mindre än d hörn från grafen för polyedern tas bort från S , adderar Balinsky en vertex v 0 av polyedern S till denna mängd och hittar en linjär funktion ƒ som har ett nollvärde på den utökade mängden, men är inte identiskt noll på hela utrymmet. Sedan kan varje återstående vertex där ƒ är icke-negativ (inklusive v 0 ) kopplas samman med stegen i simplexmetoden till vertexet som har det maximala värdet av funktionen ƒ, medan varje återstående vertex där ƒ inte är positiv (igen, inklusive v 0 ) kan på liknande sätt kopplas till den vertex där minimivärdet på ƒ nås. Därmed är hela den återstående grafen sammankopplad.