Mader's Critical Cycle Theorem for k-Connected Graphs and its Consequences

of critical edges is incident to a vertex of degree $k$
(an edge $e$ is critical if $G-e$ is not $k$-connected).

Based on his theorem, Mader was able to answer several
key ``extremal questions'' on minimally $k$-connected graphs
(i.e., on $k$-connected graphs in which every edge is critical).
1) a minimally $k$-connected graph on $n >= 3k-2$ vertices has at most $k(n-k)$ edges;
2) a minimally $k$-connected graph has at least $n(k-1)/(2k-1)$ vertices of degree $k$.

Several approximation algorithms for finding min-cost $k$-connected subgraph
are also based (implicitly or explicitly) on Mader's Theorem.

In this talk we will present a proof of Mader's Critical Cycle Theorem,
and discuss some of its consequences.