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.

  • $\begingroup$ Is the condition that your graph have no red triangles? Green triangles are ok? $\endgroup$ – TravisJ Apr 12 '15 at 0:47
  • $\begingroup$ 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. $\endgroup$ – JMoravitz Apr 12 '15 at 2:09
  • $\begingroup$ 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? $\endgroup$ – 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.

  • $\begingroup$ Very nice! $\quad$ $\endgroup$ – Brian M. Scott Apr 12 '15 at 16:35
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Apr 12 '15 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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