Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
Is the condition that $\deg(v_i)\geq i$ of special importance? It seems a bit surprising, is this sharp in some sense? –  Per Alexandersson Aug 7 at 19:53
@Per: Yes. Suppose both graphs are the same and the vertex set is $v_1, \ldots, v_k, u_1, \ldots, u_k$ and the edges are $v_iu_j$ if and only if $i\le j$. In this case the only solution is to take all $k$ single-edge paths $v_iu_i$. If you delete any of these edges, the statement becomes false. –  domotorp Aug 8 at 4:47
@Per: On the other hand, maybe it is enough to demand one degree less in, say, the blue graph. –  domotorp Aug 8 at 4:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.