Matematické Fórum

geovektor1

Ahojte, mam dalsiu vetu z oblasti teorie grafov, ktoru neviem dokazat. Znenie:
Nech $G$ je suvisly graf. Ak hrana $h$ patri do nejakej kruznice, tak po jej vynechani z $G$ dostaneme znova suvisly graf. Pomoze mi niekto z dokazom?

byk7 · 08. 04. 2015 14:40

To by mělo být jasné, ne? Pokud v kružnici vynecháš hranu, zůstane ti cesta a ta je souvislá.

geovektor1 · 08. 04. 2015 14:41

To mi aj jasne je ale ako to riadne dokazat mi uz tak jasne nie je.

byk7 · 08. 04. 2015 14:46

Proč by to neměl být důkaz?

geovektor1 · 08. 04. 2015 14:46

Povedat ze je to trivialne je dokaz? To ked poviem docentovi ze je to trivialne tak mi povie ze chce vidiet dokaz. :D

byk7 · 08. 04. 2015 14:50

Já říkám, že vynecháním hrany z kružnice ti zůstane cesta, což je souvislý graf. Je to triviální a je to důkaz.

geovektor1 · 08. 04. 2015 14:51

no tak ok, ak je to dokaz tak potom fajn. A da sa to aj zapisat nejako symbolicky?

byk7 · 08. 04. 2015 15:08

Určitě ano.

Nechť $C$ je kružnice na $m$ vrcholech (a $m$ hranách) v grafu $G$ . Vynecháním hrany $e$ z $C$ nám zůstane cesta $P$ na $m$ vrcholech a $m-1$ hranách. Cesta je ale souvislý graf, proto i $G\backslash\{e\}$ je souvislý.