7 Flows on networks, vertex and edge connectivity 7.1 Max-flow min-cut theorem 7.3 Menger’s theorem

7.2 Vertex and edge connectivity

We say that a graph is $k$ -vertex (resp. $k$ -edge) connected if $|V|>k$ and $G-S$ is connected for any $S\subset V$ (resp. $|V|>1$ and $S\subset E$ ) with $|S|<k$ . Define $\kappa(G)$ (resp. $\lambda(G)$ ) is the largest $k$ such that $G$ is $k$ -vertex (resp. $k$ -edge) connected. We assume that $G=\emptyset$ is disconnected and so $G$ is $0$ -vertex or $0$ -edge connected iff $G\neq\emptyset$ . More easily, $G$ is $1$ -vertex or $1$ -edge connected iff $G$ is connected. Also, by the above convention $\lambda(K_{1})=\kappa(K_{1})=0$ .

Exercise 7.16.

Compute $\lambda(G),\kappa(G)$ for the well-known graphs such as complete graph, path graph, cycle graph, trees, Cayley graph, petersen graph et al.

Theorem 7.17 (Whitney (1932a)).

Let $G\neq\emptyset$ . Then $\kappa(G)\leq\lambda(G)\leq\delta(G)$ .

Proof.

Removing edges on the vertex with minimum degree proves the first inequality. By definition $\kappa(G)\leq n-1$ where $n=|V|$ . Let $[S,S^{c}]:=E\cap(S\times S^{c})$ be the smallest edge-cut i.e., $\lambda(G)=|[S,S^{c}]|$ (see Exercise 7.19 as to why the smallest edge-cut will be of this form). Assume that $S,S^{c}\neq\emptyset$ i.e., $G$ is connected. We will show that $\kappa(G)\leq|[S,S^{c}]|$ .

If $E\cap(S\times S^{c})=(S\times S^{c})$ (i.e., every vertex in $S$ is adjacent to every vertex in $S^{c}$ ), then $|[S,S^{c}]|=|S||S^{c}|=|S|(n-|S|)\geq n-1\geq\kappa(G)$ .

Else choose $x\in S,y\notin S$ such that $x\nsim y$ . Define $T:=\{z\in S^{c}:z\sim x\}\cup\{z\in S-\{x\}:N(z)\cap S^{c}\neq\emptyset\}$ . Every $x-y$ path has to pass through a vertex in $T$ . In other words, there is no $x-y$ path in $G-T$ . Thus, we have that $\kappa(G)\leq|T|$ . Now we complete the proof by showing that $|T|\leq[S,S^{c}]$ . For this observe, it suffices to observe that

\{(x,z):z\in N(x)\cap S^{c}\}\cup\{(z,z^{\prime}):z\in S-\{x\},N(z)\cap S^{c}% \neq\emptyset\}\subset E\cap(S\times S^{c}),

and the LHS has cardinality at least $|T|$ . In other words, we have selected all the edges from $x$ to $S^{c}$ and for all other $z\in S-\{x\}$ , we have selected one edge each to get at least $|T|$ edges. ∎