Rovinné kubické grafy určené stěnami

Existuje kubický (tj. \(3\)-regulární) rovinný graf, který obsahuje:

Varianta
Právě 12 šestiúhelníkových stěn (a žádné další)?
Řešení
Ne, duál tohoto grafu by byl 6-regulární rovinný graf a žádný takový neexistuje.
Odpověď
Takový graf neexistuje.
Varianta
Právě 12 pětiúhelníkových stěn (a žádné další)?
Odpověď
Ano, takový graf existuje, je to graf jednoho z Platónských těles – dvanáctistěnu.
Varianta
Jednu dvacetiúhelníkovou stěnu a deset pětiúhelníkových stěn (a žádné další)?
Řešení
Z předepsaného počtu stěn by hledaný graf měl mít celkem \(\frac12(20+10{\cdot}5)=35\) hran.

Kubický graf má sudý počet vrcholů a celkem \(\frac32|V_G|\) hran, tedy počet hran je vždy násobek tří.

Protože 35 není beze zbytku dělitelné třemi, hledaný graf neexistuje.