Matematické Fórum

Podobnou(defakto stejnou) ulohu jsme take meli(teda jestli je most most hrana, kterou kdyz odebereme tak se nam graf rozpadne na dve komponenty?

Resil jsem to takto. Z definice souvislosti grafu vime, ze z kazdeho do kazdeho(to jsem to rekl pekne...)bodu musi vest cesta. Jestlize je graf 2k regularni musi z kazdeho bodu do kazdeho bodu vest minimalne dve cesty. Tedy kdyz odebereme jakou koli hranu souvislost grafu zustane zachovana. Stale existuje alespon jedna cesta.

↑ Kondr:

No ja jsem si myslel, ze kdyz tam vedou minimalne dve, tak to prost nema most... Kdyz odeberu jakoukoli hranu, tak ta souvislost zusane neporusena. Takhle to tedy nestaci?

↑ Kondr:

Uzel je to same jako vrchol? Tak z kazdeho vrcholu vychazeji minimalne dve hrany. Tudiz do kazdeho vrcholu muzeme prijit dvema cestami. Je to moje myslenka. Netvrdim ze je dobre.

↑ Kondr:

Ale graf jiz nebude 2k regularni ne?

↑ Kondr:

Ja myslim ze kdyz je graf 2k regulrani pak moje tvrzeni plati. Proc si myslis/myslite ze ne?

Kondr má pravdu. Pokud máme 2k regulární graf, tak nemusí mezi KAŽDÝMI dvěma vrcholy vést dvě cesty. Například dvě kopie grafu je 2k-regulární graf a není souvislý.
Navíc, prokud bychom v zadání změnili 2k-regulární na (2k-1)-regulární, tak takový graf už most obsahovat může! Nejmenší triviální příklad je . Nejmenší netriviální příklad (souvislý 3-regulární graf) je na deseti vrcholech. Ponechám případným zájemcům, ať si jej zkusí najít.

Pro spor předpokládejme, že graf obsahuje most. Když ho odstraníme, rozpadne se graf na dvě části. Na libovolnou z nich aplikujeme princip sudosti a máme kýžený spor.