Balinskyn lause on väite graafisesta rakenteesta monitahoisen dimensiolle 3 tai sitä korkeammalle. Lauseen mukaan jos konveksin d -ulotteisen monitahoisen (sen runko ) kärjeistä ja reunoista muodostetaan suuntaamaton graafi , niin tuloksena oleva graafi on vähintään kärkipiste - d -kytketty - poistaen minkä tahansa joukon d − 1 kärjet jättää yhdistetyn aligraafin. Jos esimerkiksi 3D-polyhedristä poistetaan kaksi kärkeä (yhdessä niiden tuloreunat), mille tahansa kärkiparille on polku, joka yhdistää tämän parin [1] .
Balinskyn lause on nimetty matemaatikko Michel Balinskyn mukaan, joka julkaisi todisteen vuonna 1961 [2] , vaikka kolmiulotteisen tapauksen todistus on peräisin 1900-luvun alusta ( Steinitzin lause, että kolmiulotteisen graafit polytoopit ovat täsmälleen kolmikytkettyjä tasograafisia [3] ).
Balinsky osoitti tuloksensa perustuen simpleksimenetelmän oikeellisuuteen lineaarisen funktion minimi- tai maksimiarvon löytämiseksi kuperalta polyhedriltä ( lineaarinen ohjelmointiongelma ). Simpleksimenetelmä alkaa monitahoisen mielivaltaisesta kärjestä ja siirtyy iteratiivisesti viereiseen kärkeen arvon parantuessa. Jos he eivät löytäneet parannusta, he saavuttivat funktion optimaalisen arvon.
Jos alle d kärjen joukko polyhedronin graafista poistetaan joukosta S , Balinsky lisää monitahoisen S kärjen v 0 tähän joukkoon ja löytää lineaarifunktion ƒ, jonka arvo on nolla laajennetussa joukossa, mutta on ei ole identtinen nolla koko tilassa. Sitten mikä tahansa jäljellä oleva kärkipiste, jossa ƒ on ei-negatiivinen (mukaan lukien v 0 ), voidaan yhdistää simpleksimenetelmän vaiheilla kärkeen, jolla on funktion ƒ maksimiarvo, kun taas mikä tahansa jäljellä oleva kärkipiste, jossa ƒ ei ole positiivinen (jälleen, mukaan lukien v 0 ) voidaan samalla tavalla yhdistää kärkeen, jossa ƒ:n minimiarvo saavutetaan. Siten koko jäljellä oleva graafi on yhdistetty.