Red-blue alternating paths

Question

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.

Update 2015.06.26 As there is renewed interest, let me add that here is the since then published paper: http://arxiv.org/abs/1104.0642 and last year the claim for which they needed this lemma was solved in another way by Gyarfas: http://www.degruyter.com/view/j/dmgt.2014.34.issue-1/dmgt.1735/dmgt.1735.xml.

Answer 1

I think even the stronger lemma is true where all paths will be edges:

Let $G$ be a simple graph, $V_k=\{v_1,\dots,v_k\}$ a subset of vertices and we have $deg(v_i)\geq i$ for all $i=1,\dots,k$. Then there is a matching which covers $V_k$.

PROOF:

If there is no edge between vertices from $V_k$ (so $V_k$ is stable) then we can consider only the edges between $V_k$ and $V\setminus V_k$ (the induced bipartite graph between $V_k$ and $V\setminus V_k$). The degree of the vertices from $V_k$ in this bipartite graph will be the same as in the original graph, so the condition still holds. From this it follows that $V_k$ satisfies the condition of Hall's marriage theorem thus there is a matching covering $V_k$. Indeed, let $X\subseteq V_k$, and let $v_l\in X$ be the vertex with the highest index in $X$. Then $|X|\leq l$. On the other hand all the neighbors of $v_l$ are in the neighborhood of $X$ so $deg(v_l)\leq |N(X)|$. Combining these two observation with our condition of $deg(v_l)\geq l$ we get that $|X|\leq |N(X)|$

If there is an edge $(v_iv_j)$, where $v_i,v_j\in V_k$, then let's choose such an edge where the sum of indexes $i+j$ is the smallest possible and suppose that $i<j$. Let's delete $v_i$ and $v_j$ from the graph. All the other vertices from $V_k$ can have their degree decrease with at most 2. If the degree of $v_l$ decreases by 1 then $v_l$ is a neighbor of $v_i$ or $v_j$ and because of $i+j$ being minimal we have $i<l$. If the degree of $v_l$ decreases by 2 then $v_l$ is a neighbor of both $v_i$ and $v_j$, and again, using that $i+j$ is minimal we have $i<j<l$. This means that by adjusting the indexes for the remaining vertices in $V_k$ in the natural way ($v_l$ remains $v_l$ if $l<i$, is renamed to $v_{l-1}$ if $i<l<j$ and is renamed to $v_{l-2}$ if $j<l$), the $V_{k-2}$ we got like this satisfies the degree condition $deg(v_i)\geq i$ for all index $i$. By induction we are done in this case.