Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Source: original paper, printed pp. 535–536, the observation after the large-grid counterexample.
Statement
Let . If a finite graph with a unit-distance realization in has chromatic number greater than , then every red-blue coloring of has a red unit pair or a blue translate of .
Full proof
Assume a coloring avoids a red unit pair and every blue translate of . For each realized graph vertex , choose an index for which is red; one exists because is not all blue.
This is a proper -coloring of the graph. Indeed, if adjacent vertices had the same index , then would be red points at distance , a contradiction. Thus the graph has chromatic number at most , proving the contrapositive.
It is enough that every graph edge be realized at distance one; extra unit distances between nonadjacent vertices do not invalidate the proof. Applied with a unit square , this says that a planar avoiding coloring would force every finite planar unit-distance graph to be four-colorable. The observation alone is not a proof of the square theorem in Problem 214.