Matematické Fórum

Zdravím,

zadání zní: Dokažte, že každý souvislý graf na n>=3 vrcholech, obsahuje dva vrcholy u a v takové, že grafy G - u , G - v,  G - u a v jsou souvislé.

Můj postup byl, matematickou indukcí, dle počtu vrcholů. Pro n=3 tvrzení platí, neboť existují pouze dva takové grafy a to K3 a P3, u kterých je to zřejmé. Dále pro n > 3 jsem si rozdělil na případy, kdy neobsahuje kružnici, tedy je to strom (nebo les) a zde existují dva vrcholy stupně jedna (listy), které pokud z grafu odebereme, dostáváme opět graf souvislý.

Potřeboval bych tedy poradit, jak ukázat, že graf, který obsahuje alespoň jednu kružnici na n>3 je souvislý po odebrání těchto vrcholů.

A ještě by mne zajímalo, proč maximální počet hran grafu na n vrcholech s c komponentami je:

Děkuji za odpověď.