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.