Prove that we can color the edges of every graph G with two colors
(red and blue) such that, for every vertex v, the number of red edges
touching v and the number of blue edges touch v differ by at most 2.
For this question, at first I thought I could use induction. But I realize that for G(k+1), all the edges previously in G(k) might now have a different set of colors, which makes this problem more complicated, and we thus can't add one more edge to the graph and just use a different color.
I have no idea how to prove this. I really appreciate the help!
Best Answer
We use induction on the number of edges.
Suppose $G$ contains a cycle $C$ of even length. By the inductive hypothesis, the graph $G-E(C)$, which has fewer edges than $G$, admits a good coloring. By coloring the edges of $C$ alternately red and blue, we get a good coloring of $G$.
Suppose $G$ contains two distinct vertices $u$ and $v$, each of degree less than $3$, which are connected by a path $P$. By the inductive hypothesis, the graph $G-E(P)$ admits a good coloring. By coloring the edges of $P$ alternately red and blue, we get a good coloring of $G$, since we don't have to worry about balancing the colors at the endpoints $u$ and $v$.
Finally, suppose $G$ contains no even cycles, and no connected component of $G$ contains more than one vertex of degree less than $3$. By the lemma stated below, each connected component of $G$ is a single vertex; i.e., $G$ has no edges. This is the base case, and the good coloring is trivial.
Lemma. If a graph with more than one vertex has no even cycles, then it has at least two vertices of degree less than $3$.
Proof. See my answer to this question.