The dwarves of the Black Forest live in houses that are each painted either red or blue. Some dwarves are friends, and some aren’t. Every so often, a dwarf will think about repainting his house. To decide whether to repaint, he looks at the colors of his friends’ houses. If his house is red, but more of his friends live in blue houses than in red houses, then he will paint his own house blue. On the other hand, if his house is blue, but more of his friends live in red houses than in blue houses, then he will paint his own house red. Prove that after some point in time, no dwarf ever paints his house again.
Here is my attempt: This problem can be modeled by a graph. The vertices of the graph represent the houses and there is an edge between two vertices if the dwarves of the houses represented by the vertices are friend with each other. The problem then translate to coloring the vertices with two colors. If the graph has no cycle then it is a tree, then we can look at the leaves of the tree and color them and go one layer up and color the nodes according to how many children node has the majority of colors and so on. However, what happen when there is cycle in the graph?