Connectivity and the theorems of Menger

Definition 4..1 (Notation for subgraphs)  

If $G$ graph and $S \subseteq V(G)$ then $G-S$ is the induced subgraph with edges in $S$ deleted. Given $F \subseteq E(G)$ then $G-F$ is the spanning subgraph obtained by deleting edges in $F$.

Definition 4..2 ($k$ connected)  

A graph is $k$ connected if $\vert G\vert > k$ and $G-S$ is connected for any $S \subset V(G)$ with $\vert S\vert < k$.

Observation 4..3  

The only $k$ connected graph with $k+1$ vertices is the complete graph $K_{k+1}$.

Definition 4..4 (Connectivity)  

The connectivity of $G$ or $\kappa(G) = \max \{ k : G$is$k-$connected$\}$.

Definition 4..5 (Local connectivity)  

If $a,b \in V(G)$ distinct and $ab \notin E(G)$ the local connectivity $\kappa(a,b;G) = \min \{ k : \exists S \subseteq V(G) \setminus \{ a,b \} : \vert S\vert = k : G - S$ has no $a-b$ path $\}$, the minimum number vertices separating $a$ and $b$.

Observation 4..6  

If $G$ is not complete then $\kappa(G) = \min_{a,b} \{ \kappa(a, b; G) \}$, which is the same as $\min_{a,b : ab,ba \notin E(G)} \{ \kappa(a, b; G) \}$.

If $G$ is complete then $\min_{a,b} \{ \kappa(a, b; G) \}$ does not have a value, but $\kappa(K_n) = n-1$.

Definition 4..7 ($k$-edge connected)  

A graph $G$ is $k$-edge connected if $G-F$ is connected for all $F \subseteq E(G)$ with $\vert F\vert < k$.

Definition 4..8 (Edge connectivity $\lambda(G)$)  

The edge connectivity of $G$ is $\lambda(G) = \max \{ k : G$ is $k$ edge connected$\}$.

Definition 4..9   If $a,b \in V(G)$ distinct then the local edge connectivity is $\lambda(a,b; G) = \min \{ k: \exists F \subseteq E(G) : \vert F\vert = k, G - F$ has no $a-b$ path $\}$. Note that $\lambda(G) = \min_{a,b} \lambda(a,b;G)$.

Definition 4..10 (Independent paths)   Two $a-b$ paths are independent if their only common vertices are $a,b$.

Theorem 4..11 (Menger)  

Vertex form. Let $a,b \in V(G)$ distinct. $ab \notin E(G)$ then $\kappa(a,b;G) =$ maximum number of pairwise independent $a-b$ paths.

Edge form. $a,b \in V(G)$ distinct. Then $\lambda(a,b;G) =$ maximum number of edge disjoint $a-b$ paths.

Proof. Vertex form. Replace all edges $uv \in E(G)$ with two directed edges and give each vertex capacity 1. Apply vertex form of max-flow min-cut to get an integer flow from $a-b$, $\kappa(a,b;G)$ since each vertex has capacity $1$ or 0.

Edge form. Do the same thing but use the edge form of max-flow min-cut.

$\qedsymbol$

Definition 4..12 (Line graph)  

The line graph $L(G)$ is the graph with a vertex $v_e$ for each $e \in E(G)$ and an edge $v_e v_f$ whenever $e$ and $f$ have a common end vertex in $G$.

Observation 4..13   The edge form can be deduced from the vertex from, using the line graph.

Observation 4..14   Given a set $P$ of independent $a-b$ paths then certainly $\vert P\vert \le \kappa (a,b;G)$, but it is not necessarily possible to add paths to $P$ to form $\kappa(a,b;G)$ independent paths.

Observation 4..15   There is a multiple source - sink version of Menger's theorem.

Lemma 4..16  

Assume $ab \in E(G)$ and let $G' = G - ab$. Then $\kappa(a,b;G') \ge \kappa(G) - 1$.

Proof. Let $k = \kappa(a,b;G')$. Choose $S \subseteq V(G) \setminus \{ a,b \}$ with $\vert S\vert=k$ and $G' - S$ disconnected. Let $x$ and $y$ be vertices in different components of $G' - S$, so that $\vert\{x,y\} \cap \{ a,b \}\vert$ is minimal. Then either

1. $a \ne x,y$ so $G - (S \bigcup {a})$ is disconnected; or
2. $b \ne x,y$ so $G - (S \bigcup {b})$ is disconnected; or

3. $\{ x,y \} = \{ a,b \}$ so $V(G) = S \bigcup \{ a,b \}$, so $\vert G\vert \le k+2$.

All cases imply that $\kappa(G) \le k+1$.

$\qedsymbol$

Corollary 4..17  

A graph is $k$-connected iff any two vertices are joined by at least $k$ independent paths.

Proof. If $G$ is not a complete graph, $\kappa(G) = \min \kappa(a,b;G)$. Apply Menger's theorem.

$K_n$ is $k$-connected iff $n \ge k+1$, so true for a complete graph.

$\qedsymbol$

Corollary 4..18  

A graph is $k$-edge-connected iff any two vertices are joined by at least $k$ edge disjoint paths.