Fan theorem

Task number: 3970

Prove the following generalization of Menger’s theorem:

  • 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 \).)

  • 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 \).

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email