10 Zusammenhang von Graphen
Bemerkung
We will see in this section that a graph is k-connected if any two of its vertices can be joined by k independent paths.
Definition
- Knotenzusammenhangszahl \[ \kappa(G) = \max \{ \kappa \mid \forall X \subseteq V : |X| < \kappa \implies G - X \text{ zshgd} \} \]
- Kantenzusammenhangszahl \[ \lambda(G) = \max \{ \lambda \mid \forall F \subseteq E : |F| < \lambda \implies G - F \text{ zshgd} \} \]
Bemerkung
- Jeder Graph ist 0-Knoten/-Kantenzusammenhängend.
- \(\lambda(G) = 0 \eq \kappa(G) = 0 \eq G\) is disconnected.
- \(G\) is zusammenhängend \(\eq\) \(\exists l \in \N\) : \(G\) ist \(l\)-zusammenhängend.
- \(\kappa(G) = 1 \eq G\) eine Artikulation besitzt.
- \(\lambda(G) = 1 \eq G\) eine Brücke besitzt.
The structure of 2-connected graphs
Bemerkung
- A connected component is a maximal (not maximum!) connected graph.
- A biconnected component / 2-connected component is a maximal biconnected subgraph.
- A block is a biconnected component or bridge or a single point.
- Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph
Klassifikation der 2-zusammenhängenden Graphen
The structure of 3-connected graphs
Method of reducing 3-connected graphs to K4, by contracting edges. 
Fortsetzung des Beweises
Klassifikation der 3-zusammenhängenden Graphen
Satz von Menger
