Collection of Maths Problems

Fan theorem

Task number: 3970

• Variant

  A graph \( G \) is \( k \)-connected if and only if for each vertex \( v \) and any set \( A \in \binom{V(G)}{k}\) there are \(k\) paths between \( v \) and the vertices of the set \( A \) which are vertex disjoint except for the vertex \( v \).

  (These paths form a ‘fan’ in the graph \( G \).)

• Solution

  For the forward implication, we prove the reverse statement:

  If \( G \) is not vertex \( k \)-connnected, then it has a vertex cut \( S \) of a size at most \( k-1 \) separating some vertices \( u \) and \( v \). Choose \( A \) to include \( S \) and \( u \). Then there is no fan between \( v \) and \( A \).

  Opposite implication:

  Let the vertices of \( u, v \) be given. We first show that \( in \) has degree at least \( k \): Otherwise, when \( A \) would consist of \( u \) together with all its neighbors \( N(u) \), a fan does not exist.

  It is therefore possible to select \( A \subseteq N (u) \) of size \( k \). The existence of a fan between \( v \) and \( A \) yields \( k \) paths between \( u \) and \( v \), i.e. \( G \) is \( k \)-connnected.

• Variant

  A graph \( G \) is \( k \)-connected if and only for every two sets of vertices \( A, B \in \binom{V (G)}{k} \) (not necessarily disjoint) there are \( k \) vertex disjoint paths, each has one end vertex in \( A \) and the other in \( B \).

• Solution

  As in the previous variant, for the forward implication we derive from any cut \( S \) separating \( u \) and \( v \) sets \( A \supset S \cup \{ u \} \) and \( B \supset S \cup \{v \} \).

  For the opposite implication, we first show that both \( u \) and \( v \) have a degree of at least \( k \) and then we choose \( A \subseteq N (u) , B \subseteq N (v) \).