Matematické Fórum

↑ ajucha:

Daný dotaz jsi již položila (a je tam i zodpovězen) v sekci střední škola. Nezakládej, prosím, duplicitní témata. Ideálně ho nech tady a tam ho smaž - zaprvé, je to spíš vysokoškolská látka, zadruhé, tam jsi dotaz vložila do jednoho tématu zároveň s dalšími třemi, což je rovněž proti pravidlům fóra.

Přepíšu sem tedy svou odpověď a budu doufat, že tam ten konkrétní dotaz z toho tématu smažeš:

Zde lze postupovat třeba tak, že nejprve ukážeme, že má-li graf všechny vrcholy sudého (nenulového - kdyby některé vrcholy měly nulový stupeň, vůbec je nemusíme v grafu uvažovat, vzhledem k tomu, že chceme dokázat tvrzení o hranách grafu) stupně, pak tam určitě vždy najdeme alespoň jednu kružnici. No a pak stačí nahlédnout, jak bude vypadat graf po odebrání takové kružnice.

↑ ajucha:

To je přesěn ta myšlenka. : )) A důvod, proč to funguje, je, že po odebrání kružnice snížím některým vrcholům stupeň právě o dva, a ostatním nezměním stupeň vůbec - tedy pokud nevynuluju stupně všem vrcholům, zase dostanu nějaký graf, který bude mít u všech vrcholů stupně nenulové sudé (pokud některým vrcholům snížím v průběhu procesu stupeň na nulu, zase je zkrátka neuvažuju, jako výše), tedy zase určitě najdu kružnici.

Zbývá tedy provést důkaz toho, že graf s pouze sudými stupni vrcholu obsahuje nějakou kružnici (to už je však celkem jednoduché).