The Affirmative Action Problem

The Affirmative Action problem has been posed by Donald Newman [Zeitz, p. 23]:

Consider a graph whose nodes are colored in one of two colors: black or white. The white node is called integrated if it has at least as many black as white neighbors, and similarly for the black node. A coloring of a graph is said to be integrated if each of the nodes is integrated. Prove that a graph without loops admits an integrated coloring.

The applet below starts with a configuration of 20 nodes. The nodes (and edges) can be removed one at a time (Remove last) or all at once (Clear). You can create new nodes by starting to drag anywhere in the applet. Clicking inside a node changes its color.

At present, among all browsers, only Firefox displays Java applet and that after issuing a warning and asking for confirmation. If that is too much for you, you can download the applet converted into an application that does not run in browser. You'll still need a Java installation, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM.

(Instead of the applet you can download and run locally an application that is performing exactly the same job.)

The proof is due to Jim Propp.

Call an edge balanced if it joins two differently colored nodes. The proof elaborates on the one-liner:

Maximize the number of balanced edges!

Since the number of nodes is finite, so is the number of possible color assignments. Hence, there are colorings with the maximal number of balanced edges. Any such coloring is bound to be integrated.

To see why this is so, consider a non integrated node. Without loss of generality, we may assume it colored white. The fact the the node is not integrated can be rephrased in terms of the incident edges. The edges joining the node to the black neighbors are balanced, those joining it to the white neighbors are not. We conclude, that, among the edges incident to the non integrated node, there are fewer balanced than unbalanced edges. Changing the color of such a node, makes its incident balanced edges unbalanced, and vice versa. The operation therefore increases the total number of balanced edges.

Now, we see that the existence of a non integrated node in a coloring with a maximal number of balanced edges leads to a contradiction. Thus we conclude that, in such colorings, all nodes are necessarily integrated.

References

P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999

70767661