Mňamózní trojúhelníky
Úloha číslo: 4558
Mějme rovinné nakreslení grafu \(G\), v němž jsou všechny stěny trojúhelníky. Předpokládejme navíc, že na každém vrcholu leží buď dort, zmrzlina, nebo lízátko. O stěně řekneme, že je mňamózní, pokud na jejích vrcholech najdeme všechny tři dobroty (tj. každou právě jednou). Ukažte, že mňamózních stěn je sudý počet.
Nápověda
Prozkoumejte, jak spolu mohou sousedit stěny přes hrany, na jejichž koncích je jiná dobrota.Řešení
Podívejme se na podgraf duálu indukovaný hranami, jimž v původním grafu odpovídají hrany, na jejichž koncích jsou různé dobroty.
Vrcholy duálu mohou mít stupeň 3, ty odpovídají mňamózním trojúhelníkům. Ostatní trojúhelníky odpovídají v duálu buď vrcholům stupně 0 (na všech stejná dobrota) nebo stupně 2 (jedna dobrota dvakrát a druhá jednou).
Protože podle principu sudosti má každý graf sudý počet vrcholů lichého stupně, má tento graf sudý počet vrcholů stupně 3. Původní graf měl tudíž sudý počet mňamózních stěn.
