Kostry grafu
Úloha číslo: 4081
Ukažte, že pro každou kostru \(K\) grafu \(G\) a hranu \(e\in E_G\setminus E_K\) existují dvě hrany kostry \(e’\) a \(e’’\) takové, že jak \((K\setminus e’) \cup e\) tak \((K\setminus e’’) \cup e\) jsou opět kostry grafu \(G\).
Řešení
Přidáním \(e\) do \(K\) vznikne cyklus délky alespoň tři. Za \(e’\) a \(e’’\) vezmeme dvě hrany tohoto cyklu rozdílné od \(e\).
Potom \(K\setminus e’ \cup e\) je souvislý, protože \(K\cup e\) byl souvislý a odstraněním hrany z cyklu se souvislost neporuší. Tento graf nemá cykly, protože \(K\cup e\) měl jediný cyklus a ten jsme přerušili odebráním \(e’\).
Pro \(e’’\) postupujeme obdobně.