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.
