# Disjoint paths between four vertices

Consider the following property of an undirected graph: For any four distinct vertices $$a,b,c,d$$, there is a path from $$a$$ to $$b$$ and a path from $$c$$ to $$d$$ such that the two paths do not share any vertex.

Is there a name for this property, or has it been studied? It looks related to vertex connectivity but not quite the same. Also it seems that any graph satisfying this property must have vertex connectivity at least $$2$$.

• Wouldn't the vertex connectivity have to be at least $3$? If the graph $G$ can be disconnected by removing two vertices $a,b$, and if $c,d$ are in different components of $G-a-b$
– bof
Apr 5 '19 at 9:43

The property that you are describing is called $$2$$-linked. More generally, we say that a graph is $$k$$-linked if it has at least $$2k$$ vertices and for all distinct vertices $$s_1, \dots s_k, t_1, \dots, t_k$$ there are $$k$$-vertex disjoint paths connecting $$s_i$$ to $$t_i$$ for all $$i \in [k]$$. Note that every $$k$$-linked graph is $$k$$-connected. The converse is not true. For example, a cycle is $$2$$-connected but is not $$2$$-linked.
However, it is a classic theorem that there is a function $$f(k)$$ such that every $$f(k)$$-connected graph is $$k$$-linked. The current best bound for $$f(k)$$ is due to Thomas and Wollan, where they prove that every $$10k$$-connected graph is $$k$$-linked. The paper is titled An improved linear edge bound for graph linkages, and is available here.
• Thanks! Is there a better known bound for $f(k)$ than $20$ in the case $k=2$? It doesn't seem to be in the paper. Apr 5 '19 at 11:06
• Yes, $7$-connected implies $2$-linked. Actually $7$-connected implies that for every set of $4$ vertices $a,b,c,d$ there is a cycle containing $a,b,c,d$ (in that order). This is stronger than $2$-linked. See arxiv.org/abs/1808.05124 Apr 5 '19 at 11:11
• Thanks again. One more question: Is it known that $6$-connected does not imply $2$-linked? The paper mentions that $7$ is tight for the cycle property, but since the path property is weaker this is unclear. Apr 5 '19 at 11:32
• Actually, the definition I used for $k$-linked is equivalent to the version where $s_1, \dots, s_k, t_1, \dots, t_k$ are not necessarily distinct, but the paths are required to be internally-disjoint. With this definition, $k$-linked implies $k$-ordered. So, $6$-connected does not imply $2$-linked. Apr 5 '19 at 11:59