21
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Is the condition that $\deg(v_i)\geq i$ of special importance? It seems a bit surprising, is this sharp in some sense? $\endgroup$ Aug 7, 2014 at 19:53
  • 1
    $\begingroup$ @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. $\endgroup$
    – domotorp
    Aug 8, 2014 at 4:47
  • $\begingroup$ @Per: On the other hand, maybe it is enough to demand one degree less in, say, the blue graph. $\endgroup$
    – domotorp
    Aug 8, 2014 at 4:48

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Unfortunately we also need that one endpoint of each path is outside $V_k$, your construction does not satisfy this, as both endpoints of the matching might be in $V_k$. $\endgroup$
    – domotorp
    Jun 23, 2015 at 17:57
  • $\begingroup$ Let me simplify the proof of David's theorem. On $i$-th step we choose an edge $v_iu_i$ from the vertex $v_i$ by the following algorithm. If $v_i$ is already covered, go to next step. If we may choose edge $v_iv_j$, do it with minimal possible $j$. If not, but we may choose edge $v_iu$, $u\notin V_k$, do it. What if we can't? It means that all edges to $v_i$ go to vertices $v_1,\dots,v_{i-1},u_1,\dots,u_{i-1}$. But if $u_j\notin \{v_1,\dots,v_{i-1}\}$, then $v_i$ has at most 1 neighbor in $\{v_j,u_j\}$ by our construction. Using this and $deg(v_i)\geq i$ we see that we really may proceed. $\endgroup$ Jun 23, 2015 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.