Balinského věta je tvrzení o grafové struktuře mnohostěnu dimenze 3 a vyšší. Věta říká, že pokud je neorientovaný graf vytvořen z vrcholů a hran konvexního d - rozměrného mnohostěnu (jeho kostry ), pak je výsledný graf alespoň vrcholově - d -souvislý - odstraňuje libovolnou množinu d − 1 vertices opouští připojený podgraf. Například pro 3D mnohostěn, pokud odstraníte dva vrcholy (spolu s jejich dopadajícími hranami), pro každý pár vrcholů existuje cesta spojující tento pár [1] .
Balinského teorém je pojmenován podle matematika Michela Balinského , který důkaz publikoval v roce 1961 [2] , ačkoli důkaz trojrozměrného případu pochází z počátku 20. století ( Steinitzova věta, že grafy trojrozměrných polytopy jsou přesně trojsouvislé rovinné grafy [3] ).
Balinsky dokázal svůj výsledek založený na správnosti simplexní metody pro nalezení minima nebo maxima lineární funkce na konvexním mnohostěnu ( úloha lineárního programování ). Simplexová metoda začíná na libovolném vrcholu mnohostěnu a iterativně se přesouvá do sousedního vrcholu se zlepšením hodnoty. Pokud nenalezli zlepšení, dosáhli optimální hodnoty funkce.
Pokud je z grafu mnohostěnu odstraněna z S množina méně než d vrcholů, Balinsky do této množiny přidá vrchol v 0 mnohostěnu S a najde lineární funkci ƒ, která má na rozšířené množině nulovou hodnotu, ale je ne shodně nulová na celém prostoru. Potom jakýkoli zbývající vrchol, ve kterém je ƒ nezáporné (včetně v 0 ), lze pomocí kroků simplexové metody připojit k vrcholu, který má maximální hodnotu funkce ƒ, zatímco jakýkoli zbývající vrchol, ve kterém ƒ není kladný (opět, včetně v 0 ) lze obdobně připojit k vrcholu, ve kterém je dosaženo minimální hodnoty ƒ. Tím je celý zbývající graf propojen.