Wiki
Wiki

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 L={a1,…,ak}⊂RnL=\{a_1,\ldots,a_k\}\subset\mathbb R^n. If a finite graph with a unit-distance realization in Rn\mathbb R^n has chromatic number greater than kk, then every red-blue coloring of Rn\mathbb R^n has a red unit pair or a blue translate of LL.

Full proof

Assume a coloring avoids a red unit pair and every blue translate of LL. For each realized graph vertex vv, choose an index i(v)i(v) for which v+ai(v)v+a_{i(v)} is red; one exists because v+Lv+L is not all blue.

This is a proper kk-coloring of the graph. Indeed, if adjacent vertices v,wv,w had the same index ii, then v+ai,w+aiv+a_i,w+a_i would be red points at distance ∣v−w∣=1|v-w|=1, a contradiction. Thus the graph has chromatic number at most kk, 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 LL, 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.