7.4 Exercises

Let $G$ be a graph and $S,T\subset V(G)$ such that $S\cap T=\mathrm{\varnothing }$. Formulate an appropriate notion of a vertex cut and prove a version of the vertex form of the Menger’s theorem for the following two scenarios.

1. (a)

   Consider the maximum number of disjoint paths from $S$ to $T$ such that the paths do not intersect even at $S$ and $T$.

2. (b)

   Consider the maximum number of disjoint paths from $S$ to $T$ such that the paths are allowed to intersect at $S$ or $T$.

Show that edge connectivity and vertex connectivity are equal if $\mathrm{\Delta }(G)\le 3$.

If $G$ is a connected graph and for every edge $e$, there are cycles $C_1$ and $C_2$ such that $E(C_1)\cap E(C_2)=\{e\}$ then $G$ is $3$-edge connected.

What is the vertex and edge connectivity of the Petersen graph ?

Let $F$ be a non-empty set of edges in $G$. Prove that $F$ is an edge-cut of the form $F=E\cap (S\times S^c)$ for some $S\subset V$ in $G$ iff $F$ contains an even number of edges from every cycle $C$.

If $G$ is a $k$-connected graph and a new graph $G^{\prime }$ is formed by adding a new vertex $y$ with at least $k$ neighbours in $G$, then $G^{\prime }$ is also $k$-connected.

Let $G$ be a graph with at least $3$ vertices. Show that $G$ is $2$-connected $\iff$ $G$ is connected and has no cut-vertex $\iff$ for all $x,y\in V(G)$ there exists a cycle through $x$ and $y$ $\iff$ $\delta (G)\ge 1$ and every pair of edges lies in a common cyle.

Consider a directed graph $G=(V,E)$ and $s,t\in V$. Further assume that there are no incoming edges at $s$ or no out-going edges at $t$. An elementary $s-t$ flow is a flow $f$ which is obtained by assigning a constant positive value $a$ to the edges on a simple directed $s-t$ path and $0$ to all other edges. Show that every flow is a sum of elementary flows and a flow of strength $0$.

Consider a directed graph $G=(V,E)$ and $s,t\in V$. Further assume that there are no incoming edges at $s$ or no out-going edges at $t$. If $f$ is an integral flow of strength $k$, show that there exist $k$ directed paths $p_1,\mathrm{\dots },p_k$ such that for all $e\in E$, $|\{p_i:e\in p_i\}|\le f(e).$

* (Generalized max-flow min-cut theorem :) Let $G=(V,E)$ be a directed graph, $s,t\in V$ and $c:(V-\{s,t\})\cup E\to [0,\mathrm{\infty })$ be a capacity constraint function. Then $f:E\to [0,\mathrm{\infty })$ is a $s-t$ flow satisfying capacity constraint $c$ if

1. (a)

   ${\sum }_{e:e^{-}=x}f(e)={\sum }_{e:e^{+}=x}f(e)$ for all $x\ne s,t.$ (conservation of flow / Kirchoff’s node law).

2. (b)

   For all $e\in E$, $f(e)\le c(e)$. (edge capacity constraint).

3. (c)

   ${\sum }_{e:e^{+}=x}f(e)\le c(x)$ for all $x\ne s,t.$ (vertex capacity constraint.)

4. (d)

   $|f|:={\sum }_{e:e^{-}=s}f(e)-{\sum }_{e:e^{+}=s}f(e)\ge 0$. (flow strength is non-negative.)

A subset $S\subset V\cup E$ is an $s-t$ cut if every path from $s$ to $t$ passes through either a vertex or an edge in $S$. Further capcity of a cut is defined as $c(S):={\sum }_{v\in S}c(v)+{\sum }_{e\in S}c(e).$

Show that

* Can you state the defective version of Hall’s marriage theorem as a max flow-min cut theorem ?