Teorema lui Balinski

Eliminarea oricăror două vârfuri (galbene) nu poate deconecta un poliedru tridimensional: se poate alege un al treilea vârf (verde) și o funcție liniară netrivială a cărei valoare zero (planul albastru) trece prin aceste trei vârfuri, permițând conexiuni de la vârful ales la maximul și minimul funcției și de la orice alt vârf la acel maxim sau minim

În combinatorica poliedrică^⁠(d), o ramură a matematicii, teorema lui Balinski este o afirmație din punct de vedere al teoriei grafurilor despre structura poliedrelor convexe tridimensionale și politopurilor convexe din dimensiuni superioare. Se afirmă că, dacă se formează un graf neorientat din vârfurile și muchiile unui poliedru convex sau politop d-dimensional convex (scheletul său^⁠(d)), atunci graful rezultat este cel puțin d-conex: eliminarea oricărui vârf d − 1 lasă un subgraf conex. De exemplu, pentru un poliedru tridimensional, chiar dacă două dintre vârfurile sale (împreună cu muchiile lor incidente) sunt îndepărtate, pentru orice pereche de vârfuri va exista totuși un drum pe vârfuri și muchii, care leagă perechea.

Teorema lui Balinski este numită astfel după matematicianul Michel Balinski, care a publicat demonstrația ei în 1961, deși cazul tridimensional datează din prima parte a secolului al XX-lea și de la descoperirea teoremei lui Steinitz^⁠(d) că grafurile poliedrelor tridimensionale sunt chiar grafurile planare 3-conexe.

Demonstrația lui Balinski

Balinski demonstrează rezultatul pe baza corectitudinii algoritmului simplex pentru găsirea minimului sau maximului unei funcții liniare pe un politop convex (problema programării liniare). Metoda simplex începe de la un vârf arbitrar al politopului și se deplasează în mod repetat la un vârf adiacent care îmbunătățește valoarea funcției; când nu se poate face nicio îmbunătățire, a fost atinsă valoarea optimă a funcției (maximă sau minimă, în funcție de criteriul de optimizare).

Dacă S este o mulțime de vârfuri, mai mică decât d, de eliminat din graful politopului, Balinski adaugă încă un vârf v₀ la S și găsește o funcție liniară ƒ care are valoarea zero pe mulțimea augmentată, dar nu este identică cu zero pe întreg spațiul. Apoi, orice vârf rămas la care ƒ este nenegativ (inclusiv v₀) poate fi conectat prin pași de tip simplex la vârful cu valoarea maximă a lui ƒ, iar orice vârf rămas la care ƒ este nepozitiv (incluzând din nou v₀) poate fi conectat similar la vârful cu valoarea minimă a lui ƒ. Prin urmare, întregul graf rămas este conex.