Legyen tehát H és H’ két maximális összefüggő részhalmaz. Ha diszjunktak, kész vagyunk. Ha van közös pontjuk, akkor ebből a közös pontból mind H, mind H’ minden pontja elérhető úttal, tehát H és H’ egyesítésének minden pontja is elérhető belőle úttal, vagyis egyesítésük is összefüggő részhalmaz (összefüggő részgráfot feszít). De H és H’ tartalmazásra maximális összefüggő részhalmazok voltak, s ez csak úgy lehet, ha H=H’.
A feladat többi állítása nyilvánvaló következménye a feladat most bizonyított első állításának.
| TARTALOMJEGYZÉK |