Chromatický index rovinných kubických grafů
Úloha číslo: 3282
Dokažte, že každý rovinný kubický graf bez mostů je Vizingovy třídy I.
Nápověda
Nejprve obarvěte stěny a teprve z tohoto obarvení odvoďte obarvení hran.
Řešení
Mějme rovinný kubický graf bez mostů \(G\). Chceme mu obravit hrany pomocí tří barev \(a,b,c\). Podle věty o 4 barvách nejprve obarvíme stěny \(G\) pomocí barev 1,2,3 a 4. Protože graf \(G\) nemá mosty, odděluje každá hrana různé stěny.
Hrana dostane barvu podle toho, jaké mají barvy přilehlé stěny. Barva \(a\) odpovídá dvěma možným dvojicím barev stěn \((1{,}2),(3{,}4)\); barva \(b\) dvojicím \((1{,}3), (2{,}4)\) a barva \(c\) dvojicím \((1{,}4), (2{,}3)\).
Každé dvě sousední hrany mají právě jednu stěnu společnou a tudíž různé barvy.