Matematické Fórum

XMagda · 18. 11. 2012 20:54

Moc prosím o pomoc s tímto příkladem: Dokažte:pokud cesty P,P* mají společné koncové body, potom lze z jejich hran vybrat kružnici, jejíž délka nepřesahuje součet délek cest P´,P*.
Nějak nevím jak mám na tento příklad vytvořit důkaz. Předem děkuji za pomoc.

petrkovar · 18. 11. 2012 23:31

Řekl bych, že zadání buď není kompletní, nebo tvrzení v obecnosti neplatí.
Pokud bude cesta $P$ obsahovat pouze hranu $uv$ a cesta $P'$ pouze hranu $vu$ , tak z jejich hran kružnici nevybereme.
Pokud však víme, že cesty $P$ a $P'$ jsou různé, tak existuje nějaké hrana $xy$ , která se vyskytuje v uzavřeném sledu $S$ sestaveném z cest $P$ a $P'$ pouze jednou.
Dále máte ve svém učebním textu jistě větu, která říká, že z každého $uv$ -sledu lze vybrat $uv$ -cestu. Když z uzavřeného sledu $S$ vynecháme hranu $xy$ , tak dostaneme $xy$ -sled.
Dál už je to snadné...