Prove there are k independent A-B paths between two disjoint sets

Question

This is an exercise in chapter 1 of Extremal Graph Theory by Bela Bollobas. This question is based on a theorem in G.A.Dirac's paper Extensions of Menger's Theorem. Link to the paper

Question in the book:

Let $A$=$\{a_1,...,a_p\}$ and $B$=$\{b_1,...,b_q\}$ be disjoint sets of vertices of $G$ such that

$\kappa(a_i,b_j)\geq k$ for all $i,j$, $1\leq i \leq p$, $1\leq j \leq q$.

Let $\lambda_1,...\lambda_p$ and $\mu_1,...,\mu_q$ be nonnegative integers, such that $\sum_{1}^{p}\lambda_i=k=\sum_{1}^{q}\mu_j$

Now the question asks the reader to deduce from Menger that there exists $k$ independent $A-B$ paths such that $\lambda_i$ of those paths start at $a_i$ and $\mu_j$ of those paths start at $b_j$.

My approach:

I tried inducting on $k$. The base case $k=1$ is trivial. Assume there exist such paths for $k=n-1$, then for the inductive step, what I wish to show is that we can add an appropriate path (e.g. path between $a_i$ and $b_j$)so that we can add $1$ to any $\lambda_i$ and $\mu_j$. But I could not deduce a contradiction that there must exist such new paths.

I also tried to explore the first intersection $v$ of one of the $k-1$ paths, say path $a_m,...,b_n$ and a path $a_i,...,b_j$ so that we can add $1$ to $\lambda_i$, while subtracting $1$ from $\lambda_m$ by adding the path $a_i,.,v,.,b_n$. But that doesn't provide any useful insights.

Since I am only a beginner in graph theory, it might be that I was missing something obvious here or I was on the wrong track. Could someone please provide any hints? Thanks very much!

Answer 1

While I haven't looked at the paper, I don't think either of these are the right approach.

I would try `modifying' the graph $G$ by adding two new vertices $a^*$ and $b^*$ in such a way that $\kappa(a^*, b^*) \geq k$, and so that if our new graph has $k$ independent $a^*-b^*$ paths, then $G$ must have the right numbers $\lambda_i$ and $\mu_i$ of paths between the desired vertices.

If you want to see this principle in action, in a simpler setting, look up a proof of the 'Fan Lemma'. It uses exactly this idea to turn Menger's Theorem into a statement about a whole set of vertices.

For a much more explicit hint, hover over the box below. It gives a construction that I think should work:

Create a new graph $G^*$ from $G$ as follows. Make duplicates of the vertices of $A$ and $B$ so that there are at least $\lambda_i$ copies of each vertex $a_i$, and $\mu_i$ copies of each vertex $b_i$, with exactly the same neighbourhoods as the originals. (For example: if $\lambda_1 = 3$, then $G^*$ will have 3 vertices, all called $a_1$, all with exactly the same neighbours, and if $\mu_2 = 0$ or $\mu_2 = 1$, then leave $b_2$ in $G^*$, but don't duplicate it). Now add vertices $a^*$ and $b^*$, and make $a^*$ adjacent to $\lambda_i$ of the copies of each vertex $a_i$, and make $b^*$ adjacent to $\mu_i$ copies of each $b_i$. In particular, both $a^*$ and $b^*$ have exactly $k$ neighbours. Notice that if you can get $k$ independent $a^*-b^*$ paths in $G^*$, then by just deleting $a^*$ and $b^*$ and `merging' the copies of the vertices you made, you get exactly the $k$ paths you want! By Menger's theorem, all you need to do is prove that $\kappa(a^*, b^*) =k$.