Duální grafy bez smyček a násobných hran
Úloha číslo: 4118
Charakterizujte souvislé rovinné grafy, které splňují, že:
Varianta
Duální graf jejich libovolného rovinného nakreslení nemá žádnou smyčku.
Řešení
Smyčka v duálním grafu odpovídá hraně ležící na hranici pouze jedné stěny neboli mostu. Nemá-li mít duální graf smyčku, musí být hranově dvousouvislý.
Varianta
Duální graf jejich libovolného rovinného nakreslení nemá žádnou smyčku ani dvojici násobných hran.
Řešení
Dvojice násobných hran odpovídá dvěma stěnám, které sdílejí alespoň dvě hrany. Nemá-li mít duální graf smyčku ani násobnou hranu, musí být hranově třísouvislý.
