# Pairing Vertices by Edge Color

We have a graph $G$ with an even number of vertices. Every pair of vertices is connected by either a green or red edge.

If every vertex is connected to at least one other vertex by a green edge, can we always pair up the vertices with green edges? If not give a counterexample and describe all graphs satisfying the above conditions that cannot have their vertices paired in such a way.

I'm having a hard time constructing a counterexample which leads me to think that we can always pair the vertices in such a fashion, but then proving it is not going well -- any help would be appreciated. I don't know of the source for this problem, I got it from my lecture notes from a combinatorics course.

• Is the condition that your graph have no red triangles? Green triangles are ok? – TravisJ Apr 12 '15 at 0:47
• Yes, @bof, that's better, and saves me from trying to complete my induction argument, which makes sense now why I was having difficulty with it (since the claim was false). The difficulty in completing induction was trying to prove that there would always exist a $u$ and $v$ connected via a green edge that when deleted left the remaining graph with the same conditions (in particular every vertex has at least one green edge). In the $K_{3,3}$ case, no such pair exist as you will always leave the remaining vertex in its partition alone without a green edge. – JMoravitz Apr 12 '15 at 2:09
• So, the question remains, which graphs cannot: We can see then that @bof's counterexample extends to red monochromatic $K_{2k+1, 2k+1}$ with nonedges colored green and added back in, but do there exist any others? – JMoravitz Apr 12 '15 at 2:12

Consider a complete graph with an even number of vertices, with each edge colored red or green, in such a way that there are no red triangles, each vertex is incident with at least one green edge, and there is no perfect matching consisting of green edges.

Let $V$ be the vertex set. Let $M$ be a maximal green matching, and let $W$ be the set of vertices covered by the matching $M$.

Of course $|W|$ is even; since $|V|$ is even, it follows that $|V\setminus W|$ is even. Now $|V\setminus W|\gt0$ because $M$ is not a perfect matching, but $|V\setminus W|\lt3$ because all vertices in $V\setminus W$ are joined by red edges (by maximality of $M$) and there are no red triangles, so $|V\setminus W|=2$. That is, there are exactly two vertices of $V$ which are not covered by the maximal matching $M$; call them $a$ and $b$. The edge $ab$ must be red, by maximality of $M$.

Now consider any vertex $w\in W$ and let $w'$ be the vertex matched with $w$ in the matching $M$. Since there are no red triangles, each of the vertices $w,w'$ must be joined by a green edge to at least one of the unmatched vertices $a,b$. However, if one of $w,w'$ were joined by green edges to both of the unmatched vertices, then we could get a green perfect matching by replacing the edge $ww'$ with green edges joining $w$ to one of the unmatched vertices and $w'$ to the other. We can conclude that each vertex in $W$ is joined by a red edge to one of the unmatched vertices $a,b$ and by a green edge to the other.

Partition $W$ into two disjoint sets $S$ and $T$, where: $$S=\{w\in W:wa\text{ is green, }wb\text{ is red}\};$$ $$T=\{w\in W:wa\text{ is red, }wb\text{ is green}\}.$$ $S$ and $T$ are nonempty sets, since each of the vertices $a$ and $b$ is incident with at least one green edge.

Let $A=\{a\}\cup S$ and $B=\{b\}\cup T$. Since all vertices in $A$ are joined by red edges to $b$, and since there are no red triangles, all edges between vertices in $A$ must be green. Likewise, all edges between vertices in $B$ must be green. Since $\{A,B\}$ is a partition of $V$, $|A|$ and $|B|$ must have the same parity. If they were both even, we would obviously have a green perfect matching; therefore, $|A|$ and $|B|$ are both odd. Finally, all edges between $A$ and $B$ must be red; if there were a green edge joining a vertex of $A$ to a vertex of $B$, we could use it to get a green perfect matching.

We have shown that any counterexample to the problem statement must be obtained by partitioning the vertex set $V$ into two disjoint subsets $A$ and $B$, each of odd cardinality greater than $1$, and coloring all edges between $A$ and $B$ red, all other edges green. Conversely, it's clear that any such coloring is a counterexample.

• Very nice! $\quad$ – Brian M. Scott Apr 12 '15 at 16:35
• @Jimmy: Suppose that $u,v\in A$ are joined by a red edge. Then $u,v$, and $b$ are vertices of a red triangle, since the edges $ub$ and $vb$ are red. – Brian M. Scott Apr 12 '15 at 18:54