show/hide this revision's text 2 cleaned up formatting

Suppose we have two simple graphs on the same vertex set. We will call one of them red, the other blue. Suppose that for i=1,..,k $i=1,..,k$ we have $deg (v_i)\ge i$ in both graphs, where $V_k={v_1,\ldots,v_k}$ is a subset of the vertices. Is it always possible to find a family of vertex disjoint paths such that1,

  1. for i=1,.., k $i=1,.., k$ every $v_i$ is contained in a path,2,
  2. each path consists of vertices only from $V_k$ except for exactly one of its endpoints which must be outside of $V_k$,3,
  3. in each path the red and blue edges are alternating?

The claim is true if $k$ is small (<6). It is also true if the red graph and the blue graph are the same. This question was brought to my attention by a few friends who could use it in one of their papers in preparation.
show/hide this revision's text 1

Red-blue alternating paths

Suppose we have two simple graphs on the same vertex set. We will call one of them red, the other blue. Suppose that for i=1,..,k we have $deg (v_i)\ge i$ in both graphs, where $V_k={v_1,\ldots,v_k}$ is a subset of the vertices. Is it always possible to find a family of vertex disjoint paths such that 1, for i=1,.., k every $v_i$ is contained in a path, 2, each path consists of vertices only from $V_k$ except for exactly one of its endpoints which must be outside of $V_k$, 3, in each path the red and blue edges are alternating?

The claim is true if $k$ is small (<6). It is also true if the red graph and the blue graph are the same. This question was brought to my attention by a few friends who could use it in one of their papers in preparation.