Menger's Theorem for planar triangulations

Question

I was reading the paper "Planar separators" by Alon, Seymour and Thomas (available on the first author's webpage). They consider a planar triangulation, that is, a maximally planar graph $G$ drawn in the plane so that the boundary of every face is a triangle. They construct a cycle $C$ on vertices $v_0, \ldots , v_{2k-1}$ such that when $D$ denotes the subgraph of $G$ induced by $C$ and the vertices on the inside of $G$ (in the fixed drawing), $C$ is geodesic in $D$: For any two vertices of $C$, their distance in $D$ is the same as in $C$. Then they say

There are $k+1$ vertex-disjoint paths of $D$ between $\{ v_0, \ldots, v_k \}$ and $\{ v_k, \ldots, v_{2k-1}, v_0 \}$. For otherwise, by a well-known form of Menger's Theorem for planar triangulations, there is a path of $D$ between $v_0$ and $v_k$ with $\leq k$ vertices.

What's more, they take these paths $P_0, \ldots, P_{k}$ so that $P_i$ joins $v_i$ to $v_{2k-i}$.

Unfortunately, I do not know the mentioned "form of Menger's Theorem for planar triangulations" and do not see how to derive it, given that it appears to include the notion of distances and provides a linkage from each $v_i$ to $v_{2k-i}$. A search on google has also not been successful.

Does anybody know the statement they refer to? Has it appeared somewhere explicitly? If not, can someone indicate how to prove it?

Answer 1

The standard version of Menger's theorem says that in any finite graph, the maximum number of vertex-independent paths between two vertices $a$ and $b$ is the same as the size of the smallest vertex cut separating $a$ and $b$. (Two paths are vertex-independent if they share no vertices except for their endpoints.)

Add two vertices $a$ and $b$ to your graph $D$ and connect $a$ to $v_0,\ldots, v_k$ and connect $b$ to $v_k,\ldots,v_{2k-1},v_0$, to get a new graph $D^+$, with a triangulated planar drawing. If we know that every vertex cut separating $a$ and $b$ has size at least $k+1$, we get by Menger's theorem a collection of $k+1$ vertex-independent paths from $a$ to $b$. Clearly, each of these paths should start by going from $a$ to $v_i$ (for some $i\in\{0,1,\ldots,k\}$) and end by going from $v_j$ (for some $j\in\{k,\ldots,2k-1,0\}$) to $b$. The planar drawing ensures that the path starting with $v_i$ ends with $v_j$ with $j=2k-i$ (where $2k=0$), hence you get your desired paths $P_0,\ldots,P_k$.

Let $\Lambda$ be a minimal vertex cut separating $a$ and $b$, so that $a$ and $b$ are in distinct connected components of $D^+\setminus\Lambda$. Clearly, $\Lambda$ must contain $v_0$ and $v_k$. By planarity, there is a Jordan curve $\gamma$ surrounding the component of $a$ in $D^+\setminus\Lambda$, separating it from the rest of the graph $D^+$. Let $e_1,e_2,\ldots,e_m$ be the edges from $D^+$ that are cut by $\gamma$, ordered according to $\gamma$, and such that $e_1$ is connected to $v_0$ and $e_m$ is connected to $v_k$. In particular, each $e_\ell$ has one endpoint in the component of $a$ in $D^+\setminus\Lambda$ and the other endpoint in $\Lambda$. Since the drawing of $D^+$ is triangulated, the edges $e_\ell$ and $e_{\ell+1}$ must be incident to each other and form a triangle with another edge in $D^+$. It follows that $\Lambda$ induces a path from $v_0$ to $v_k$. Since $C$ is geodesic in $D$, we know that there is no path in $D$ between $v_0$ and $v_k$ having less than $k+1$ vertices, so $\Lambda$ must contain at least $k+1$ vertices.