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.