Man spricht von einem zusammenhängenden Graph ,
wenn zu je zwei
verschiedenen Knoten
in
ein Weg existiert, der
mit
verbindet.
Ist
nicht zusammenhängend, dann zerfällt
in Komponenten , d.h. in
zusammenhängende induzierte Untergraphen mit maximaler Knotenzahl.
,
wenn zu je zwei
verschiedenen Knoten 
in 
mit 
verbindet.
Ist 
