Ein nicht-leerer Graph ist zusammenhängend, wenn es zwischen je zwei beliebigen Knoten einen Pfad gibt.
Eine Zusammenhangskomponente von ist ein maximaler, zusammenhängender Untergraph. Jeder Graph ist die disjunkte Vereinigung seiner Zusammenhangskomponenten.