Proof: Recall that $\sigma (X)$ denotes the surplus of the cut defined by $X$.

Let $c,D$ satisfy the cut condition. We denote by $s,t$ the two vertices of degree $m$, and $U=\{u_1,\dots ,u_m\}$ the vertices of degree $2$ in $G$. By assumption $\delta (U,\{s,t\})=\mathrm{\varnothing }$. We may also assume that $\delta (u_i)$ is tight for any $u_i$, otherwise we increase the capacity on the edge $st$ and decrease it on ${\delta }_G(u_i)$. Then simplify the instance by removing parallel edges in $G$ and $H$.

Proof: $H[U]$ is bipartite, with parts $X\cup Y=U$. Let $xy$ be a demand with $x\in X$, $y\in Y$. We would like to do one of the following operation without violating the cut-condition:

• decrease $c$ and $d$ by $1$ along the cycle $xsy$,
• decrease $c$ and $d$ by $1$ along the cycle $xty$.

If the first one can't be done, there is a central tight cut $S$containing $s$ but not $x$ and $y$. If the second one can't be done there is a central tight cut $T$ containing $x$ and $y$ but not $t$.

We partition $X\cup Y$ into parts $A$ to $H$ as in the next figure, where $S$ is the red set, $T$ the blue set. For instance $A=X\cap S\cap T$, $H=Y\cap T\setminus X$, and $x\in G$, $y\in H$.

Let $S^{\prime }=\{s\}\cup A\cup B\cup C\cup G$ and $T^{\prime }=\{s\}\cup A\cup B\cup D\cup H$. Then, by counting (and remembering that $X,Y$ is a bipartition for $H[U]$ and $U$ is independant in $G$):

$$0=\sigma (S)+\sigma (T)=\sigma (S^{\prime })+\sigma (T^{\prime })-\sigma (C,D)-\sigma (G,H)+\sigma (C,G)+\sigma (D,H)$$

Because $\sigma (S^{\prime })\ge 0$ and $\sigma (T^{\prime })\ge 0$ (cut condition):

$$0\le \sigma (S^{\prime })+\sigma (T^{\prime })=\sigma (C,D)+\sigma (G,H)=-D({\delta }_H[C,D]\cup {\delta }_H[G,H])<0$$

The last inequality comes from the existence of the demand $xy$. This is a contradiction, hence one of the two operations can be carried out. Also, these operations preserves the integrality of the surplus function, hence at least $1/2$ of the demand can be moved this way at each step. By induction upon the total demand, we reduce the instance to an instance with demand only between $st$, where the cut condition is sufficient.

Suppose $D_{st}>0$. Then, as $\delta (\{u\})$ is tight for any $u\in U$, the instance is not feasible, hence $H[U]$ is not bipartite. We get an odd cycle in $H[U]$ and so an odd-spindle minor in $G+H$.

Suppose now that $D_{st}=0$. Then we try to choose for any demand edge $uv$, how much of $D_{uv}$ is routed along the path $usv$, with respect to using exactly all of the capacities of ${\delta }_G(s)-\{st\}$. This is a capacitated fractional $b$-matching problem on vertices $U+z$ and edges $H[U]\cup \{zu,u\in U\}$ with $b(v)=c(sv)$, and where $z$ is an dummy vertex with $b(z)=c(st)$ and $z$ is adjacent to every node (including itself) in $U$ with infinite capacity. If a solution exists then we easily deduce a solution to the routing problem. Otherwise we know that there exists three sets $S\ni z$, $N$ and $W$ partitioning $U\cup \{z\}$, with:

$$2D({\delta }_H[N])+D({\delta }_H[N,W])<c({\delta }_G(N,\{s\}))-c({\delta }_G(S,\{s\}))$$

Because each vertex in $N$ defines a tight set we also have:

$$2D({\delta }_H[N])+D({\delta }_H[N,S])+D({\delta }_H[N,W])=c({\delta }_G(N,\{s\}))+c({\delta }_G(N,\{t\}))$$

Subtracting it from the inequality, we get:

$$\epsilon =D({\delta }_H[N,S])-c({\delta }_G(S,\{s\}))-c({\delta }_G(N,\{t\}))>0$$

Consider the instance $G^{\prime },H^{\prime }$ obtained from $G[\{s,t\}\cup W],H[W]$ by adding a demand edge $st$ with $D_{st}=\epsilon$. If there is a cut $X\ni t$ with negative excess in $G^{\prime },H^{\prime }$, then $X\cup S$ is a cut with negative excess in $G,H$, contradiction. But the instance is not feasible: $\delta (w)$ is tight for each $w\in W$ so the demand $st$ cannot be routed through $W$. Hence by induction $G^{\prime },H^{\prime }$ contains an odd-spindle as a minor, from which we get that $G,H$ contains an odd-spindle too, using a demand edge in ${\delta }_H[S,N]$.

Proof: By contradiction.

Use the centrality of the cut to get the red paths, this gives a $K_4$ minor.

Proof: Any path between the inner nodes of two distinct $(u,v)$ paths would give a $K_4$.

Proof: $V\setminus (R\setminus L)$ is connected as $V\setminus R$ and $L$ are connected and intersect in $l$. It remains to prove that $R\setminus L$ is connected. By contradiction.

First case : suppose $r^{\prime }$ is disconnected from $r$, with $r^{\prime }$ in the component of $v$ in $G[V\setminus \{l,r\}]$. Then take the red path by centrality of $R$, the blue path by centrality of $B$, the green path by centrality of $L$ (to get to $V\setminus (R\cup L)$) and $R$ (then to $u$ or $v$). $x,l,l^{\prime },r$ give a $K_4$.

Second case : suppose $r^{\prime }$ is disconnected from $r$, with $r^{\prime }$ not in the component of $u$ or $v$ in $G[V\setminus \{l,r\}]$. Then again take the red and blue path, then the green to $V\setminus (R\cup L)$, then use the centrality of $L$ and $R$ to complete the green path to somewhere (in $L\setminus R$) between $l^{\prime }$ and $l$ and somewhere (in $R\setminus L$) between $l^{\prime }$ and $r$. this gives a $K_4$.

Proof: By contradiction. We immediately get a $K_4$.

Proof: By recursion, using the previous lemma.

Proof: By contradiction. Let $u,v$ be a maximal pair such that there are $m_1$ and $m_2$ with $u,v⪯m_1,m2$ but $m_1$ and $m_2$ are not comparable. Then there is a $K_4$.

Proof: By contradiction. Take four maximal consecutive directive paths on a simple cycle $C$. Get $v$ as $a\vee b$ and $u$ as $c\wedge d$. If $e\ne v$ we get a $K_4$, hence $a,b⪯e=v$. Repeat on all the possible way to choose the four blue paths, we eventually get that $a=b=e$, this contradicts the simplicity of $C$.

We prove the second statement. if $\{u,v\}=\{s,t\}$ it is a $2$-cut. Else there are directed paths from $s$ to $u$, from $s$ to $t$ and from $v$ to $t$. Together they define a third disjoint $(u,v)$-path. Hence $\{u,v\}$ is a $2$-cut.

Proof: If all the demand edges are fully compliant we are done. Hence we can assume that there is a demand edge $uv$ that is not fully compliant, but only compliant. Our goal is to replace $uv$ by two demand edges $uw,wv$ such that the new instance is still compliant, satisfies the cut condition and is somehow simpler.

Because $uv$ is compliant there is a directed $(s,t)$-path $P$ going through $s,u,v,t$ in that order. Because $u,v$ is not fully compliant there is two cut $l,r$ separating $u$ from $v$, and three disjoint $(r,l)$-paths. We may choose one of them to contain an $s^{\prime }{t}^{\prime }$ path $Q$. We may assume that $r$ is on $P$ between $u$ and $v$. $l$ must be in the same component as $u$ and $v$ in $G\setminus \{s,t\}$, because one of the three $(l,r)$-paths does not contain $s$ or $t$ (and $\{s,t\}$ is a $2$-cut). $l,r$ separates $u$ from $v$, hence $l$ is on $P$, between $s$ and $u$ or between $v$ and $t$. Let's say $P$ goes through $s,l,u,r,v,t$ in that order.

We want to replace the demand edge $uv$ by two demand edges $ul,lv$ or $ur,rv$. Suppose this is not possible, and we will derive a contradiction. Then we get two central tight cuts $L$ and $R$ where:

• $L$ contains $l$ but not $r,u,v$,
• $R$ contains $r$ but not $l,u,v$.

$L$ and $R$ are central, so are $L\setminus R$ and $R\setminus L$ by Lemma 6. Consider $G\setminus (L△R)$ and its components $C_i$, $u$ and $v$ are in two distinct components (as $\{l,r\}$ separates them). Suppose some component $C_j$ has two vertices $x,y$ with $x\in L\cup R$ and $y\in$V \ setminus $L\cup R)$. $L$ and $R$ are connected, hence there are two paths from $x$, one to $L\setminus R$, one to $R\setminus L$. $V\setminus L$ and $V\setminus R$ are also connected, hence there are two paths from $y$ to $L\setminus R$ and from $y$ to $R\setminus L$. These four paths can be chosen node-disjoint. Moreover, there is an $(x,y)$-path in $C_j$ and a $(L\setminus R,R\setminus L)$-path avoiding $C_j$. This gives a $K_4$. Hence each $C_i$ is completely contained in either $L\cap R$ or $V\setminus (L\cup R)$.

As the cycle $C=P\cup Q$ intersects $\delta (R)$and $\delta (S)$ exactly twice each, we have:

• $R$ cannot contain $s$ nor $t$
• either $t$ is in the same component as $v$, or $s$ and $t$ are both in $L\setminus R$

1. Suppose first that $t$ is in the same component $C_v$ as $v$. Then take any demand edge $ab$, and consider a directed $(s,t)$-path $P^{\prime }$ containing $a$ and $b$ (because $ab$ is compliant). If $a$ and $b$ are in two distinct components, and distinct from the component $C_v$, then $P^{\prime }$ intersects at least 5 times $\delta (L\setminus R)$ and $\delta (R\setminus L)$, contradiction. Any demand between two components has one endpoint in $C_v$.

1. Suppose now that $s,t\in L\setminus R$. Take a component $C_i$ of $G[V\setminus (L△R)]$, and suppose that ${\delta }^{+}(C,R\setminus L)$ and ${\delta }^{-}(C,R\setminus L)$ are both non-empty, then there is $e^{+}$ and $e^{-}$ as evidence. $e^{+}$ is in some path $P^{+}$ starting from $s$ and $e^{-}$ is in some path $P^{-}$ ending at $t$ (by the acyclic orientation of $G$). Because $\delta (R\setminus L)$ and $\delta (L\setminus R)$ can be crossed at most twice by a cycle, the situation looks like the following picture:

   

   $P^{-}$ and $P^{+}$ are vertex-disjoint: otherwise we could make a directed path from $R\setminus L$ to itself through $C_i$. This path could then be extended into an $(s,t)$-path crossing $\delta (R\setminus L)$ four times, contradiction. $C_i$ is connected hence there is a path between a node $x$ of $V(P^{+}\cap C_i)$ and a node $y$ of $V(P^{-}\cap C_i)$, in $C_i$. Using another component $C_j$ (there are at least two components, and each of them is connected to $L\setminus R$ and $R\setminus L$ by centrality of these sets), and the connectedness of $L\setminus R$ and $R\setminus L$, we get a $K_4$.

   From this we conclude that every component $C_i$ has ${\delta }^{+}(C_i,R\setminus L)=\mathrm{\varnothing }$ (out-component) or ${\delta }^{-}(C_i,R\setminus L)=\mathrm{\varnothing }$ (in-component). Moreover any demand edge $ab$ between two components is contained in an $(s,t)$-path which crosses $\delta (L\setminus R)$ and $\delta (R\setminus L)$ exactly twice, hence $a$ is in an out-component and $b$ is in an in-component.

Hence, in both cases, the instance obtained by contracting each component into a single node, as well as $L\setminus R$ and $R\setminus L$ is a $K_{2,m}$ with $H[U]$ bipartite where $U$ is the set of vertices of degree $2$. Moreover the new instance satisfies the cut condition (we only did minor operations), but the cut induced by $\delta (L)$ and $\delta (R)$ in the contracted graph are tight and show that no routing may exists. This contradicts the simultaneous existence of $L$ and $R$.

Thus, the demand $uv$ can be pushed to either $r$ or $l$. Then the number of compliant but not fully compliant demand edges is decreased by one. By induction the instance is routable.

Proof: Orient $G$ with respect to some $2$-cut $st$. $G,H$ is not cut-sufficient, hence there is a non-compliant demand $uv$. We choose $uv$ such that $I_{uv}=\{w:u\wedge v⪯w⪯u\vee v\}$ is minimal.

By contradiction. Suppose ${\mathcal{P}}_{uv}$ is not covered by bubbles, there is a path $P$ that does not cross any bubble, and a central tight cut $C$ such that $|E(P)\cap {\delta }_G(C)|=3$ (more than $3$ would give a $K_4$). Define $a$, $b$, $S_u$ and $S_v$ as in the following picture:

$a$ and $b$ are chosen such that the two black paths are minimal. Then there are three-disjoint ($a$,$b$)-paths, $\{a,b\}$ is a $2$-cut. Moreover, by carefully choosing $P$ and $C$, we can ensure that any $(u,b)$-path inside $C$ crosses some tight cut twice more that $P$ (a shortcut by a violating $(u,b)$-paths would decrease the number of tight cuts crosses by $P$).

$S_u$ is the component of $G\setminus \{a,b\}$ containing $u$, and $S_v$ the component containing $v$. By symmetry we may assume $s$ and $t$ are not in $S_U$. We want to show the existence of a $2$-cut $\{x,y\}\subset S_u\cup \{a,b\}$ distinct from $\{a,b\}$, and two disjoint $(x,y)$-paths, not containing $a$ or $b$, with a demand between their inner nodes. We distinguish two cases:

1. Suppose there is a tight cut defined by some set $S$, $u,b\notin S$, that intersects every $(u,b)$-path in $C$, but not $P$ between $u$ and $b$. Take $S$ inclusion-wise minimal. $\{a,b\}$ being a $2$-cut, $S$ does not intersect $P$ at all. Let $U$ be the component of $G[C\setminus S]$ containing $u$, and $B=C\setminus (U\cup S)$. $C\setminus U$ cannot be a bubble covering $P$, hence $\sigma (C\setminus U)>0$. Then,

   $$\sigma (U)+\sigma (S)=\sigma (U\cup S)+2\sigma (U,S)\text{hence}\sigma (U)\ge 2\sigma (S,U)$$

   $$\sigma (U)+\sigma (C\setminus U)=\sigma (C)+2\sigma (U,C\setminus U)\text{hence}\sigma (U)<2\sigma (U,C\setminus U)$$

   From that we get $\sigma (S,U)<\sigma (U,C\setminus U)$ and then $\sigma (S\setminus C,U)<\sigma (B,U)\le 0$. Therefore there is a demand $pq$ with $p\in S\setminus C$ and $q\in U$. Then we prove that there is a path from $P$ to $S\cap C$ inside $S$: otherwise there would be a component $S^{\prime }$ of $S$ that does not intersect $C$. Therefore $S\setminus S^{\prime }$ would also cut all the $(u,b)$-paths inside $C$, and

   $$0=\sigma (S^{\prime }\cup (S\setminus S^{\prime }))=\sigma (S^{\prime })+\sigma (S\setminus S^{\prime })-2\sigma (S^{\prime },S\setminus S^{\prime })\ge 0$$

   Hence $\sigma (S\setminus S^{\prime })=0$, contradicting the minimality of $S$. Using also the centrality of $C$, we easily get to the following situation ($a$ may be equal to $y$):

   

   $\{x,y\}$ must be a $2$-cut because of the three disjoint $(x,y)$-paths, $u$ and $p$ must be in distinct components. Thus there must be an $(x,y)$-path containing $p$ (in the component of $u$), disjoint from the $(x,y)$-paths containing $q$.

2. Otherwise there is no single tight cut intersecting all the $(u,b)$-paths inside $C$. Choose a minimal family of sets defining central tight cuts that covers all such paths, without intersecting $P$ between $u$ and $b$. Then all these cuts are bubbles for $uv$. Moreover, no two of them are crossed: this would give a $K_4$, by using $P$. Also the union of them is not tight: this would give a single cut covering the $(u,b)$-paths inside $C$. Hence there must be a demand $pq$ between two of these sets. Take a $upb$ and a $uqb$ paths, using $P$ between $u$ and $b$ it is then easy to find $x,y$ with three disjoint $(x,y)$-paths, one through each of $x,y,u$.

Then in both cases $pq$ is not compliant, and $\{w:x⪯p\wedge q⪯w⪯p\vee q⪯y\}\subset \{w:a⪯w⪯b\}\subseteq I_{uv}$ (supposing wlog that $a⪯b$), contradicting the choice of $uv$.

Proof: Consider a demand $uv$ not covered by bubble. Let $F_{uv}$ be a minimal family of bubbles covering every $(u,v)$-paths. By centrality of the bubbles, $|F_{uv}|\ge 2$. We distinguish two cases:

1. $m=|F_{uv}|\ge 3$. We can assume that the bubbles are disjoint: associate to each bubble a path covered only by that bubble. If two bubbles are crossed, then we can find a path between their associated paths, and using the path associated to a third bubble we get a $K_4$. Similarly there is no edge in $G$ between two bubbles.

   Now contract each bubble into a single node, as well as the components of $u$ and $V$ in $G\setminus \bigcup _{B\in F_{uv}}B$. It is easy to check this operation gives a $K_{2,m}$, with each vertex of degree $2$ defining a tight cut, and a positive demand between the vertices of degree $m$. This instance also satisfies the cut condition but does not have a routing, hence there must be an odd-spindle minor.

1. $|F_{uv}|=2$, $F_{uv}=\{A,B\}$. Let $U$ be the component of $G\setminus \{A,B\}$ containing $u$, and $R$ the component containing $v$. Then:

   $$0\le \sigma (A\cup R)+\sigma (B\cup R)=\sigma (A\setminus B)+\sigma (B\setminus A)+2\sigma (U,R\cup (A\cap B))$$

   If $A\cap B=\mathrm{\varnothing }$, the RHS becomes $\sigma (A)+\sigma (B)+2\sigma (R,U)<0$, contradiction. Hence $A\cap B$ contains at least one vertex $x$. By centrality of $A$ and $B$ we can find two $(u,v)$-paths: $P_B$ disjoint from $A\setminus B$, and $P_A$ disjoint from $B\setminus A$, and a (minimal) path $Q_A$ from $x$ to $a\in V(P_A)$ inside $A$ and a (minimal) path $Q_B$ from $x$ to $b\in V(P_B)$ inside $B$. We deduce that there are three disjoint $(a,b)$-paths, $\{a,b\}$ is a $2$-cut. Applying Lemma 6, $A\setminus B$ and $B\setminus A$ are both central.

   Contract every edge not in $\delta (A)\cup \delta (B)$, this gives a $K_{2,m}$ that satisfies the cut condition. But the cuts induced by $A$ and $B$ shows that this instance is not feasible: there is an odd-spindle again.

This concludes the proof of Theorem 1.