Souvislost rovinných grafů
Úloha číslo: 3829
Pro jaké největší \(k\) existuje rovinný vrcholově \(k\)-souvislý graf?
Řešení
Každý rovinný graf má vrchol stupně nejvýše 5. Hranová souvislost je shora omezena 5 a tedy i vrcholová.
Hledáme-li 5-souvislý rovinný graf, musí mít i minimální stupeň 5. Zvolíme-li např. dvacetistěn, lze rozborem tří případů (podle vzdálenosti vrcholů) ukázat, že mezi každými dvěma vrcholy vede 5 vrcholově disjunktních cest.
Alternativně lze ukázat neexistenci řezů délky 4. Protože graf dvacetistěnu je rovinná triangulace, je každý minimální řez (vzhledem k inkluzi) i cyklem. Tento cyklus vnímaný jako Jordanova křivka by měl oddělovat vrcholy případných komponent. Rozborem případů lze ukázat, že žádný takový vhodný čtyřcyklus neexistuje.
Odpověď
Hledané \(k\) je rovno 5, neboli existují rovinné 5-souvislé grafy, nikoli však 6-souvislé (hranově i vrcholově).