Given an undirected graph I'd like to color each node either black or red such that at most half of every node's neighbors have the same color as the node itself. As a first step, I'd like to show that this is always possible.
I believe this problem is the essence of the math quiz #2 in Communications of the ACM 02/2011 where I found it, so you might consider this a homework-like question. The quiz deals with partitions but I found it more natural to formulate the problem as a graph-coloring problem.
Coming from computer science with some math interest I'm not sure how to approach this and would be glad about some hints. One observation is that any node of degree 1 forces its neighbor to be of the opposite color. This could lead to a constructive proof (or a greedy algorithm) that provides a coloring. However, an existence proof would be also interesting.
Best Answer
Hint: Start with a random colouring and try to increase the number of edges which have differently coloured endpoints.
Spoiler: