ein Graph, in dem für je zwei Ecken x und y ein Weg von x nach y existiert.

Zwei Ecken x und y eines Graphen G nennt man zusammenhängend, wenn es in G einen Weg von x nach y gibt. Dies definiert auf der Eckenmenge E(G) eine Äquivalenzrelation. Jeder von einer Äquivalenzklasse induzierte Teilgraph heißt Zusammenhangskomponente oder kurz Komponente von G.

Sind G₁, G₂,…,G_η die Komponenten von G, so ist G die Vereinigung der Graphen G₁, G₂,…,G_η (Vereinigung von Graphen), also \begin{eqnarray}G={G}_{1}\,\cup \,{G}_{2}\,\cup \cdots \,\cup {G}_{\eta }.\end{eqnarray} Besteht G nur aus einer einzigen Zusammenhangskomponente, so heißt der Graph zusammenhängend.

Die Anzahl der Komponenten eines Graphen G bezeichnen wir mit η(G). Die beiden Ecken u und v mögen in der gleichen Komponente eines Graphen G liegen. Ist S ⊂ E(G) eine Eckenmenge, die weder u noch v enthält, so nennt man S eine u und v trennende Eckenmenge, wenn die Ecken u und v im Teilgraphen G − S zu verschiedenen Komponenten gehören. In dem Fall, daß S nur aus einer Ecke besteht, spricht man auch von einer trennenden Ecke oder Artikulation.

Gleichermaßen heißt eine Kantenmenge J ⊆ K(G) eine u und v trennende Kantenmenge, wenn die Ecken u und v im Faktor G −J zu verschiedenen Komponenten gehören. Enthält J nur eine Kante k, so nennt man k auch Brücke oder trennende Kante. Es ist nicht schwer zu sehen, daß eine Kante eines Graphen G genau dann eine Brücke ist, wenn sie zu keinem Kreis von G gehört.

Für eine beliebige Kante k eines Graphen G lassen sich leicht die Ungleichungen \begin{eqnarray}\eta (G)\,\le \,\eta (G-k)\,\le \,\eta (G)+1\end{eqnarray} nachweisen. Daher ist k genau dann eine Brücke im Graphen G, wenn η (G − k) = η(G) + 1 gilt.