Connectivity

Cut vertex (Artikulationsknoten): removing vertex disconnects the graph. Cut edge (Brücke): analogous

k-connected: must remove at least $k$ vertices to disconnect graph k-edge-connected: analogous

vertex connectivity $\le$ edge connectivity (disconnect by removing some edges $⟹$ disconnect by removing always one incident vertex) $\le$ minimum degree (node can be isolated and graph disconnected by removing incident edges)

Menger Theorem

$u$-$v$-vertex separator: set of vertices that, when removed, result in $u$ and $v$ being disconnected $u$-$v$-edge separator: analogous

Theorem

• Every $u$-$v$-vertex separator has size at least $k$ (must remove $k$ vertices) $⟺$ there are at least $k$ internally vertex disjunct $u$-$v$ paths
• Every $u$-$v$-edge separator has size at least $k$ (must remove $k$ edges) $⟺$ there are at least $k$ internally vertex disjunct $u$-$v$ paths

Tarjan’s Algorithm

• Calculate DFS numbers
• Set low number of each node to lowest number reachable when using arbitrarily many tree edges and exactly one non-tree edge.

Same low number $⟺$ same strongly connected component (lie on same cycle) Direct successor has higher low number $⟺$ node cut vertex (not possible to get back to node from successor)

Lowest number to get back to, i.e. largest cycle that it lies on.