Stěny v rovinnosti
Úloha číslo: 4108
Ukažte, že v maximálním (co do počtu hran) 2-souvislém rovinném grafu bez trojúhelníků je každá stěna ohraničena buď čtyřcyklem nebo pěticyklem.
Řešení
Pokud by se v grafu vyskytla stěna velikosti \(k\ge 6\), lze ji rozdělit tětivou na stěnu velikosti 4 a stěnu velikosti \(k-2\).
Je třeba dát pozor na to, aby tato úhlopříčka nevytvořila smyčku ani násobnou hranu. Potom by takový případ nastal, stačí se po stěně posunout na sousední vrcholy (u artikulace), případně tak, aby konce tětivy byly mimo most.
