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.
 A: 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.
