Dvě hrany v párování

Úloha číslo: 3264

Nalezněte kubický graf \(G\) bez mostů různý od \(K_4\), který obsahuje dvě hrany \(e\) a \(f\) takové, že G nemá párování obsahující \(e\) a neobsahující \(f\).

Jinými slovy, každé párování obsahuje obě hrany nebo žádnou.

  • Nápověda

    Zvažte, jak by ovlivnilo párování, kdyby graf obsahoval trojúhelník.

  • Ř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ě, viz obrázek.

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