Balinski's theorem

Removing any two vertices (yellow) cannot disconnect a three-dimensional polyhedron: one can choose a third vertex (green), and a nontrivial linear function whose zero set (blue) passes through these three vertices, allowing connections from the chosen vertex to the minimum and maximum of the function, and from any other vertex to the minimum or maximum.

In polyhedral combinatorics, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of three-dimensional convex polyhedra and higher-dimensional convex polytopes. It states that, if one forms an undirected graph from the vertices and edges of a convex d-dimensional convex polyhedron or polytope (its skeleton), then the resulting graph is at least d-vertex-connected: the removal of any d − 1 vertices leaves a connected subgraph. For instance, for a three-dimensional polyhedron, even if two of its vertices (together with their incident edges) are removed, for any pair of vertices there will still exist a path of vertices and edges connecting the pair.[1]

Balinski's theorem is named after mathematician Michel Balinski, who published its proof in 1961,[2] although the three-dimensional case dates back to the earlier part of the 20th century and the discovery of Steinitz's theorem that the graphs of three-dimensional polyhedra are exactly the three-connected planar graphs.[3]

Balinski's proof

Balinski proves the result based on the correctness of the simplex method for finding the minimum or maximum of a linear function on a convex polytope (the linear programming 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.

If S is a set of fewer than d vertices to be removed from the graph of the polytope, Balinski adds one more vertex v0 to S 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 v0) 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 v0) can be similarly connected to the vertex with the minimum value of ƒ. Therefore, the entire remaining graph is connected.

References

  1. ^ 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.
  2. ^ 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.
  3. ^ Steinitz, E. (1922), "Polyeder und Raumeinteilungen", Encyclopädie der mathematischen Wissenschaften, Band 3 (Geometries), pp. 1–139.

Read other articles:

Artemis Fowl (film)

Artemis FowlSutradaraKenneth BranaghProduser Kenneth Branagh Judy Hofflund Skenario Conor McPherson Hamish McColl BerdasarkanArtemis Fowloleh Eoin ColferPemeran Ferdia Shaw Lara McDonnell Josh Gad Tamara Smart Nonso Anozie Colin Farrell Judi Dench Penata musikPatrick DoyleSinematograferHaris ZambarloukosPenyuntingMatthew TuckerPerusahaanproduksi Walt Disney Pictures TriBeCa Productions Marzano Films DistributorWalt Disney Studios Motion PicturesTanggal rilis 12 Juni 2020 (2020-06-1...

 

Montevideo Convention

1933 pan-American treaty on statehood Montevideo ConventionConvention on the Rights and Duties of StatesRatifications and signatories of the treaty   Parties   Signatories   Other Organization of American States membersSignedDecember 26, 1933LocationMontevideo, UruguayEffectiveDecember 26, 1934Signatories20[1]Parties17[1] (as of November 2021)DepositaryPan American UnionLanguagesEnglish, French, Spanish and PortugueseFull text Montevideo Conventio...

 

Tejay van Garderen

American cyclist Tejay van GarderenVan Garderen at the 2013 Paris–NicePersonal informationFull nameTejay van GarderenBorn (1988-08-12) August 12, 1988 (age 35)Tacoma, Washington, U.S.Height1.86 m (6 ft 1 in)[1]Weight72 kg (159 lb; 11 st 5 lb)[1]Team informationCurrent teamEF Education–EasyPostDisciplineRoadRoleRider (retired)Directeur sportifRider typeClimberTime trialistAmateur teams2004–2005Rio Grande (Fort Collins...

IC Group

Danish clothing company IC GroupCompany typeLimited companyIndustryFashionFounded2001HeadquartersCopenhagen, DenmarkKey peopleMads Ryder (CEO)ProductsClothingRevenueDKK 2.5 billion (2013/14)[1]Net incomeDKK 221 million (2013/14)[1]Websitewww.icgroup.net IC Group is a clothing company based in Copenhagen, Denmark. Isabell Kristensen store, 33 Beauchamp Place, London (2016) History IC Group was founded as IC Companys in 2001 through the merger of InWear Group A/S and Carli Gry I...

 

Template talk:Thai-cuisine-stub

Stub sorting This template is maintained by WikiProject Stub sorting, an attempt to bring some sort of order to Wikipedia. If you would like to participate, you can choose to improve/expand the articles containing this stub notice, or visit the project page, where you can join the project and see a list of open tasks.Stub sortingWikipedia:WikiProject Stub sortingTemplate:WikiProject Stub sortingStub sorting articles Food and drink Template‑class Food portalThis template is within the scope ...

 

Renkus-Heinz

American sound equipment manufacturer Renkus-HeinzHeadquarters in Foothill Ranch, CaliforniaIndustryAudio electronicsFounded1979FoundersHarro K. Heinz, Algis RenkusHeadquartersFoothill Ranch, California, United StatesKey peoplePresident Harro K. Heinz, CEOProductsLoudspeakersWebsiterenkus-heinz.com Renkus-Heinz is a California-based manufacturer of loudspeakers and related professional sound reinforcement equipment specializing in steerable loudspeaker technology. Based in Foothill Ranch, Cal...

Lasse Hallström

Pour les articles homonymes, voir Hallström. Lasse Hallström Lasse Hallström en 2011. Données clés Nom de naissance Lars Sven Hallström Naissance 2 juin 1946 (77 ans)Stockholm (Suède) Nationalité suédoise Profession RéalisateurScénaristeProducteur Films notables Les Recettes du bonheurGilbert GrapeLe ChocolatCasanovaMes vies de chien modifier Lars Sven Hallström, dit Lasse Hallström (né le 2 juin 1946 à Stockholm, en Suède) est un réalisateur, scénariste et producteur ...

 

Franciszek Karpiński

Franciszek Karpiński Franciszek Karpiński (4 October 1741 – 16 September 1825) was the leading sentimental Polish poet of the Age of Enlightenment. He is particularly remembered for his religious works later rendered as hymns and carols.[1] He is also considered one of the most original Polish writers of the early partitions.[2] In his native Poland he was cherished during the Polish Romantic Period of the early 19th century.[3] Life Karpiński was born in 1741...

 

Khawaja Asif

Defence Minister of Pakistan Khawaja Muhammad Asifخواجہ محمد آصفAsif in 2015Minister of DefenceIncumbentAssumed office 19 April 2022PresidentArif AlviPrime MinisterShehbaz SharifPreceded byPervez KhattakSucceeded byAnwar Ali Haider (caretaker)In office27 November 2013 – 28 July 2017PresidentMamnoon HussainPrime MinisterNawaz SharifPreceded byNaveed QamarSucceeded byKhurram Dastgir Khan33rd Minister of Foreign AffairsIn office4 August 2017 – 26 April 2018P...

مراكز السيطرة على الأمراض والوقاية منها

  مراكز السيطرة على الأمراض والوقاية منها (بالإنجليزية: Centers for Disease Control and Prevention)‏[1][2]  مراكز السيطرة على الأمراض والوقاية منها   تفاصيل الوكالة الحكومية البلد الولايات المتحدة  تأسست 1 يوليو 1946؛ منذ 77 سنة (1946-07-01) المركز أتلانتا، جورجيا، الولايا�...

 

Ponders End

Human settlement in EnglandPonders EndTower blocks at Alma RoadThe Harvester Navigation Inn, seen from the towpath of the River Lee NavigationPonders EndLocation within Greater LondonPopulation15,664 (2011 Census)OS grid referenceTQ 353 959London boroughEnfieldCeremonial countyGreater LondonRegionLondonCountryEnglandSovereign stateUnited KingdomPost townENFIELDPostcode districtEN1, EN3Dialling code020PoliceMetropolitanFireLondonAmbulanceLondon UK ...

 

Death of Diana, Princess of Wales

1997 fatal car crash involving Diana, Princess of Wales Death of Diana, Princess of WalesEast entrance to the Pont de l'Alma tunnel, where Diana, Princess of Wales, was fatally injured.Date31 August 1997 (1997-08-31)LocationPont de l'Alma, Paris, France[a]Coordinates48°51′51.7″N 2°18′06.8″E / 48.864361°N 2.301889°E / 48.864361; 2.301889[1]TypeCar crashDeath caused by dangerous drivingDeathsDiana, Princess of WalesDodi FayedHen...

Pahlavi dynasty

Iranian royal dynasty (1925–1979) This article is about the Iranian royal dynasty. For the country under its rule, see Pahlavi Iran. PahlaviRoyal houseArms of dominion of the Shahs, and therefore coat of arms, of Pahlavi Iran from 1932. The emblem of the dynasty is the mountain and sun in the blue circle in the middle.CountryImperial State of IranPlace of originMazandaranFounded15 December 1925 (1925-12-15)FounderReza ShahCurrent headReza PahlaviFinal rulerMohammad Reza Pahla...

 

Alexander Bezborodko

Russian statesman (1747–1799) In this name that follows Eastern Slavic naming customs, the patronymic is Andreyevich and the family name is Bezborodko. Portrait of Bezborodko by Johann Baptist von Lampi the Elder (c. 1800) Prince Alexander Andreyevich Bezborodko (Russian: Александр Андреевич Безбородко; 25 March [O.S. 14 March] 1747 – 6 April 1799) was the chancellor of the Russian Empire from 1797 to 1799,[1] an...

 

Carcharhinus

Come leggere il tassoboxCarcharhinusSqualo pinna nera del reef (Carcharhinus melanopterus)Classificazione scientificaDominioEukaryota RegnoAnimalia PhylumChordata ClasseChondrichthyes OrdineCarcharhiniformes FamigliaCarcharhinidae GenereCarcharhinusBlainville, 1816 Specie 36 (vedi testo) Carcharhinus Blainville, 1816 è il genere più numeroso degli squali requiem (Carcharhinidae). Comprende oltre 30 specie diffuse nei mari tropicali e temperati di tutto il mondo, nonché, in alcuni casi, anc...

Luigi Mannelli (pallanuotista)

Questa voce sull'argomento pallanuotisti italiani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Luigi MannelliNazionalità Italia Altezza185 cm Peso96 kg Pallanuoto Palmarès  Olimpiadi OroRoma 1960Pallanuoto 1 I due numeri indicano le presenze e le reti segnate, per le sole partite di campionato.Il simbolo → indica un trasferimento in prestito. Statistiche aggiornate al 23 gennaio 2009 Modifica dati su Wikidata · Manuale Luigi...

 

何紹基

何紹基（1799年—1873年），字子貞，號東洲，別號東洲居士，晚號蝯叟，湖南道州（今道縣）人，道光十六年進士出身[1]，晚清詩人、畫家、書法家。 生平 早年 何紹基早年是阮元、程恩澤門生，頗得師長器重欣賞[1]。 參與科舉 道光十五年（1835年），何紹基考中乙未恩科鄉試第一（解元）。翌年（道光十六年；1836年），又考中丙申恩科殿試，獲得第二甲賜進士�...

 

Італійський фронт Першої світової війни

Італійський фронт Першої світової війни Перша світова війна Італійський фронт Першої світової війниІталійський фронт Першої світової війни Дата: 23 травня 1915 — 4 листопада 1918 Місце: Північний схід Королівства Італія Результат: перемога Антанти, розпад Австро-Угорщин...

Babak Khorramdin

9th-century Iranian revolutionary leader For the director and writer, see Babak Khorramdin (director). Babak KhorramdinPersian: بابک خرمدینStatue of Babak Khorramdin in Babek city, Nakhchivan Autonomous Republic of Azerbaijan RepublicBorn795 or 798Ardabil, Abbasid Caliphate (present-day Iran)Diedprobably 7 January 838 (age 40 or 43)[1]Samarra, Abbasid Caliphate (present-day Iraq)Years active23 yearsKnown forLeader of the Khorram-DinānOpponentAbbasid CaliphateSpous...

 

U.S. National Championships 1967

U.S. National Championships 1967Sport Tennis Data30 agosto - 10 settembre Edizione87ª CategoriaGrande Slam (ITF) LocalitàNew York e Chestnut Hill, USA CampioniSingolare maschile John Newcombe Singolare femminile Billie Jean King Doppio maschile John Newcombe / Tony Roche Doppio femminile Rosie Casals / Billie Jean King Doppio misto Billie Jean King / Owen Davidson 1966 1968 Gli U.S. National Championships 1967 (conosciuti oggi come US Open) sono stati l'87ª edizione degli U.S. National Cha...