Der Begriff "Maximal zusammenhängender Teilgraph \(U\) von \(G\)" bedeutet:
1. Der Teilgraph \(U\) ist zusammenhängend
2. Für jeden Knoten \(v\in G\setminus U\) ist der Teilgraph \(U\cup\{v\}\) nicht zusammenhängend
In deutsch: Maximal bedeutet, dass du keinen weiteren Knoten hinzufügen kannst, ohne Zusammenhang zu zerstören.
Intuitiv kannst du dir Zusammenhang so vorstellen: Ein ungerichteter Graph ist aufteilbar in zusammenhängende "Inseln", zwischen denen es keine Kante gibt. Dieser Fakt ist äquivalent zu der Aussage, dass die Relation \((x\cong y \iff \text{Es existiert ein x-y-Weg})\) eine Äquivalenzrelation ist. Diese Inseln sind die Zusammenhangskomponenten, quasi die Äquivalenzklassen des Quotienten \(G/\cong\).