A sufficient condition for graphs to be weakly \(k\)-linked (Q1180674): Difference between revisions

Let \(G=(V,E)\) be a finite, undirected, loopless graph with vertex set \(V\) and edge set \(E\). For a natural number \(k\), let \(g(k)\) be the smallest natural number so that the following holds: Let \(G\) be an \(n\)-edge- connected graph and let \(s_ 1,s_ 2,\dots,s_ k\), \(t_ 1,t_ 2,\dots,t_ k\) be vertices of \(G\). Then for every \(i\in \{1,2,\dots,k\}\) there exists a path \(P_ i\) from \(s_ i\) to \(t_ i\) so that \(P_ 1,P_ 2,\dots,P_ k\) are pairwise edge-disjoint. The author proves that: \[ g(k)\leq\begin{cases} k+1, & \text{ if } k\text{ is odd},\\ k+2, &\text{ if } k\text{ is even}.\end{cases} \] {}.