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ě.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze