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ě).

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze