Suppose we have a graph where every edge is colored red or blue. We say that a path is *alternating* if the red and blue edges alternate in it. Our goal is to find many edge/vertex-disjoint alternating paths from a given vertex $s$ to another given vertex $t$. Has this problem been studied before?


Update: It DOES NOT seem to me ANYMORE that the following, Menger-type theorem is true, as pointed out by Ilya in the comments:


Lemma:
We say that a partition of the vertices into $S, T, R, B$ is a *colored cut* if $s\in S, t\in T$, there are no edges between $S$ and $T$ and, except for the edges between $R$ and $B$, the vertices of $R$ are only adjacent to red edges and the vertices of $B$ are only adjacent to blue edges. There are $k$ edge/vertex-disjoint paths from $s$ to $t$ if and only if after deleting any $k-1$ edges/vertices, there is no colored cut.


Update: Gyula Pap told me that if we consider the directed version and edge-disjoint paths, then doubling every vertex (to redin-blueout and bluein-redout) reduces the problem to the monochromatic Menger's theorem from which (if I see well) the above lemma follows. So now I am mainly interested in the vertex-disjoint version.



Red-blue alternating Menger's theorem
It seems that the problem of determining whether there exist $2$ vertex disjoint red-blue alternating paths joining vertices $s$ and $t$ is NP-complete. Thus, unless NP $=$ co-NP, there exist no efficient characterization of obstructions to existence of such paths, similar to the one you propose in the lemma.


Below is a reduction to the classical result of Fortune, Hopcroft and Wyllie that the DIRECTED $2$-LINKAGE problem is NP-complete. ( Given a digraph $D$ and four distinct vertices $u\_1,v\_1,u\_2,v\_2$; does $D$ contain a pair of vertex-disjoint paths $P\_1, P\_2$, so that $P\_i$ is a directed path from $u\_i$ to $v\_i$ for $i=1,2$?)


Given a digraph $D$, we replace every directed edge $e=xy$ of $D$ by a vertex $w\_e$ joined to $x$ by a red edge and to $y$ by a blue edge. Then we add vertex $s$ joined by a blue edge to 
$u\_1$ and by a red edge to $v\_2$, and a vertex $t$ joined by a blue edge to $u\_2$ and a red edge to $v\_1$. It is not hard to see that a pair of vertex disjoint paths from $s$ to $t$ in the new graph corresponds exactly to the $2$-linkage as described above.


