Matematické Fórum

Zdravím, potřeboval bych od vás pomoci s formální stránkou důkazu následující úlohy.

Dokažte, že pro každou kostru K grafu G a hranu e ∈ Eg\EK existují dvě hrany kostry e',e'' ∈ Ek takové, že K\e' U e i K\e'' U e jsou opět kostry grafu G. Dokažte také, že graf K \ (e' U e'') je již nutně nesouvislý.
nebo tady

Pro jednoduchost předpokládejme, že graf G je souvislý a není kostrou.
Moje myšlenka: Pokud z grafu G odstraníme kostru, zbudou nám jen ty hrany, které byli součástí kružnice. Nazvěme jednu z těchto hran e. Jelikož je tato hrana součástí kružnice, musí existovat ještě minimálně další dvě hrany, které jsou také její součástí, tedy e' a e'' (z definice - kružnice má minimálně 3 hrany). Tyto hrany jsou zjevně součástí kostry. Nyní ke kostře K hranu e přidám. Stane se to, že kostra nebude kostrou. Takový graf bude sice souvislý, ale bude obsahovat kružnici což odporuje definici kostry. Ovšem po odejmutí jakékoliv hrany z kružnice (např e' nebo e''), kružnici poruším, a při tom zachovám souvislost grafu - stane se tedy kostrou.

K tomu, že graf K bude po odstranění e' a e'' nesouvislý, jenom to, že je snad jasné, že když z kostry odeberu hranu tak vznikne nesouvislý graf .

Jde mi hlavně o formální stránku takového důkazu, děkuji za příspěvky.