At time t=0 each node of a graph is initially colored white or black. At times t=1,2,3,... all the nodes are simultaneously given a color according to the following rule: if node X has more white neighbors than black ones, then node X becomes white; if node X has more black neighbors than white ones, then node X becomes black; otherwise node X doesn't change color.
Prove: after a final number of steps the graph reaches a stable state or a period of length 2.
Stable state example:
Period 2 example: