Okamura-Seymour

Version & licenses
Creative Commons License

A short and elementary proof of Okamura-Seymour theorem

Guyslain

I present here a simple proof of the famous Okamura-Seymour theorem. Some of the ideas come from different sources, in particular from Lex Schrijver and from András Sebő. Still I am not aware of a proof as natural (at least to me) as this one. I like the fact that we don't need to assume in the first place that all the demands are crossed, quite the opposite: we are just simplifying the graph, using only two basic operations, splitting-off and unknotting demands on the boundary. Moreover the use of the planarity assumption is made central, and the proof can be done almost completely by picture.

Theorem 1: (Okamura , Seymour [1]) Let $G,H$ be a instance of the Edge-Disjoint-Paths problem, with

  • $G$ a planar graph, given with an embedding,
  • $G+H$ Eulerian ($\delta_{G+H}(u)$ is even for each $u$),
  • the terminals $V(H)$ lies on the boundary of the outer face of (the embedding of) $G$,
  • the cut condition is satisfied.

Then $G,H$ has a solution: there is a family $(P_h)_{h \in E(H)}$ of edge-disjoint paths, where $P_h$ has the same endpoints as $h$.

Proof: We assume as usual that the terminals have degree one, while every other vertex as degree 4 (to see this, subdivide each demand edge into three edges, with the middle one in $H$ and the two others in $G$. Then for the non-terminal, replace them by a large enough grid. This preserves the assumptions of the theorem).

We introduce a notion of planar splitting-off: given a non-terminal vertex $v$ with incident edges $e_1$ to $e_4$ occuring in that order around $v$ (say clockwise). If there is not a tight cut $\delta(C)$ with $e_1, e_2 \in \delta(C)$, then we can split-off $v$ by replacing $e_1,e_2$ by a single edge between the two extremities other than $v$, and similarly for $e_3$, $e_4$, without breaking the cut condition.

Hence, we assume that such a configuration does not exists: for any two consecutive edges around a vertex, there is a tight cut containing them. Now, any path $P$ in a solution would have to check this straightness property: for any vertex on $P$, $P$ uses two opposite edges of that vertex. Indeed, a path in the solution crosses a tight cut at most once, hence cannot use two consecutive edges around a vertex. We say that a path is straight if it checks the straightness property.

If the theorem is correct, it means that the set of straight paths with extremities at the terminals should be our solution. This suggests to us the following claim (obvious when assuming the theorem):

Lemma 2: Any straight path intersects at most once any other straight path.

Proof: Suppose that the straight paths $P$ and $Q$ intersect each other at least twice. Take a connected component $C^\ast$ of $G^\ast \setminus E^\ast(P \cup Q)$ and two consecutive intersections $u$ and $v$ on the border of this component. Denote $C$ the cycle in $P \cup Q$ delimiting $C^\ast$. We choose $P$, $Q$ and $C$ such that the number $\left|V^\ast(C^\ast)\right|$ of faces inside $C$ is minimal. Denote by $V_C$ the set of vertices of $C$ or inside the interior of $C$

Picture of P and Q and C.

For any two consecutive edges around $u$ there is a tight cut containing them, therefore we can find a cut $\delta(X)$ intersecting $C$ twice on $P$ or $Q$, say $Q$.

Consider the cut $\delta(X')$, with $X' = X \setminus V_C$. This is the cut depicted with a dashed red line on the figure. Because there is no terminal in $V_C$, $\left|\delta_G(X)\right| \geq \left|\delta_G(X')\right|$ (or the cut condition would be violated by $X'$. Hence $\left|\delta_G(X') \setminus \delta_G(X) \right| \geq \left| \delta_G(X) \setminus \delta_G(X')\right|$: now because $Q$ intersects twice the second set, there must be a straight path that intersect twice the first one (each path intersects each cut, here $\delta(V_C \cap X)$, an even number of times). This gives the path $Q'$ depicted in blue in this figure:

Picture of P and Q and C.

Now, $Q$ and $Q'$ contradicts the minimality assumption on $C$.

We use this to prove that there exist two terminals adjacent to a common vertex. Start from any terminal $t_0$, with adjacent vertex $v_0$ of degree 4, and denote $P_0$ the straight path with endpoint $t_0$. Consider the straight path $P_1$ that intersects $P_0$ at $V_0$, and take one of its endpoint $t_1$, with adjacent vertex $v_1$. This defines, taking $i=1$, a connected set of faces $S_i$ delimited by $P_{i-1}$ between $t_{i-1}$ and $v_{i-1}$, then by $P_i$ from $v_{i-1}$ to $t_i$, and by the outer face.

If $v_0 = v_1$ we are done. Otherwise let $P_i$ (for i=2) be the straight path intersecting $P_{i-1}$ at $v_{i-1}$. $P_i$ cannot intersect twice $P_{i-1}$, hence must have an extremity $t_{i}$ on the side of $P_{i-1}$ which contains $t_{i-2}$. Also $P_i$ cannot intersect $P_{i-2}$, hence the set $S_{i}$ defined as above is strictly contained in $S_{i-1}$.

By iterating on $i$, because $S_i$ is decreasing at each step of the construction, we eventually find $t_i$ and $t_{i-1}$ adjacent to a common vertex. The process is illustrated below, with the red arc materializing the boundary of the graph:

Finding a "cherry" .

We are done with the technical part, whose goal was to prove the existence of this special vertex adjacent to two terminals. Now consider this vertex $v$ and take a tight cut, as in the left picture of the next figure:

Unknotting.

Such a cut exists otherwise we would split-off. Because the two dashed variants of this red cut must not violate the cut condition, we deduce that the terminal $t_A$ associated to $s_A$ must be on the right (according to the picture) of the cut, and $t_B$ on the left. Now, we exchange the position of $s_A$ and $s_B$, this preserves the cut condition, the Eulerian condition, the planarity and the fact that terminals are on the outer boundary. Moreover, any cut separating $s_A$ from $s_B$ has its excess increased by $2$. Hence we may split-off the common neighbor of $s_A$ and $s_B$. By induction on the number of vertices of degree 4, we reduce the problem to a graph with max degree 2, and this is a trivial case.

To sum up, an Okamura-Seymour instance can be solved by successive splitting-off and unknotting of straight paths. The only technical part of this proof is to show the existence of this special vertex, and there might be a simpler argument for that.

1.Haruko Okamura, Paul D. Seymour: Multicommodity flows in planar graphs.
Journal of Combinatorial Theory, Series B, 31, 75 -- 81.
Elsevier, (1981).