Dvě nespárovatelné hrany

Úloha číslo: 3263

Nalezněte kubický graf bez mostů, který obsahuje dvě nesousední hrany neležící ve společném párování.

  • Nápověda

    Prozkoumejte párování malého úplného grafu a také možné operace s tímto grafem.

  • Řešení

    Úplný graf \( K_4 \) má jednoznačný rozklad na perfektní párování. Vezměte dvě kopie \( K_4 \), v každém zvolte hranu, odstraňte tyto dvě a poté přidejte hrany mezi vrcholy stupně dva, abyste dostali souvislý graf.

    Nově přidané hrany lze rozšířit na párování jednoznačně, takže je snadné vybrat jednu z nich a vhodnou hranu ze zbytku, viz obrázek.

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