Zmenšení souvislého grafu

Úloha číslo: 4103

Dokažte, že každý souvislý graf na \(n\ge 3\) vrcholech obsahuje dva vrcholy \(u\) a \(v\) takové, že všechny tři grafy \(G\setminus\{u\}\), \(G\setminus\{v\}\) a \(G\setminus\{u,v\}\) jsou souvislé.

  • Hint

    Zkuste pokud možno co nejvzdálenější vrcholy.

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