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.

Obtížnost: Obtížná úloha
Úloha na dokazování, ověřování
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze