Matematické Fórum

slender · 07. 02. 2016 14:16

Zdravím,
snažím se dokázat pomocí eulerova vzorce následující tvrzení:

Každý rovinný graf obsahuje alespoň jeden vrchol stupně nejvýše 5.

Napadlo mě to řešit nějakým způsobem indukcí podle počtu vrcholů, ale nějak jsem se v tom zamotal. Mohl by mi někdo prosím poradit, jak to začít řešit?

Pro jistotu přikládám

Eulerův vzorec Zobrazit/skrýt!

byk7 · 07. 02. 2016 14:31

Jako důsledek Eulerova vztahu je tvrzení

$G=(V,E)$ je rovinný graf, pak $|E|\le3|V|-6$ .

Pro spor předpokládejme, že všechny vrcholy jsou stupně alespoň 6, pak
$|E|=\frac12\sum_{v\in V}\deg(v)\ge\frac12\cdot|V|\cdot6=3|V|>3|V|-6$
spor, proto existuje alespoň jeden vrchol stupně nejvýše pět.

slender · 07. 02. 2016 15:03

↑ byk7: Díky... Asi jsem jen trochu natvrdlej, ale jak dostanu z eulerovy formule tu nerovnost, kterou jsi tam použil?

byk7 · 07. 02. 2016 19:02

Nechce se mi psát, takže...
//forum.matweb.cz/upload3/img/2016-02/68107_graf.png
(snad je značení jasné.)

slender · 08. 02. 2016 17:39

↑ byk7: Díky moc. :)

Matematické Fórum

#1 07. 02. 2016 14:16

Důkaz pomocí eulerovy formule (existence vrcholu stupně nejvýše 5)

#2 07. 02. 2016 14:31

Re: Důkaz pomocí eulerovy formule (existence vrcholu stupně nejvýše 5)

#3 07. 02. 2016 15:03

Re: Důkaz pomocí eulerovy formule (existence vrcholu stupně nejvýše 5)

#4 07. 02. 2016 19:02

Re: Důkaz pomocí eulerovy formule (existence vrcholu stupně nejvýše 5)

#5 08. 02. 2016 17:39

Re: Důkaz pomocí eulerovy formule (existence vrcholu stupně nejvýše 5)

Zápatí