A 2–colouring problem in the rational plane

A 2-colouring-problem in the rational plane

The rational plane consists by definition of all the points in the real Euclidean plane with two rational Cartesian coordinates. This note is devoted to a proof of the following theorem.

Theorem 2 Two colours suffice to colour the points of the rational plane such that any two points at distance 1 form a bichrome pair.

for any graph holds that the two statements:

• there exists a 2-coloring for the vertices of the graph, such that each edge connects two vertices of different colour, and
• each cyclic path in the graph consists of an even number of edges,

are equivalent. The proof of this equivalence is left to the reader. Here we follow Trans van der Sommen in using this equivalence by rephrasing Theorem 0 as

Theorem 1 Consider the graph whose vertices are the points of the rational plane and whose edges are the pairs of points 1 apart. Its cyclic paths are of even length.

We are now going to study pairs of rational points that are distance 1 apart. Let their $x$ -coordinates differ by ${\delta x}$ and their $y$ -coordinates by ${\delta y}$ . Because of the mutual distance we have

$$ (\delta x) ^ {2} + (\delta y ^ {2}) = 1. $$

Because ${S}{x}$ and ${S}{y}$ are differences between rational coordinates,they are rational themselves, i.e. there are integers $a,b,c,d$ such that - with $\Downarrow$ denoting the greatest common divisor-

$$ S x = a / c, a \downarrow c = 1, \delta y = b / d, b \downarrow d = 1 $$

Eliminating ${\delta x}$ and ${\delta y}$ yields

$$ a ^ {2} \cdot d ^ {2} + b ^ {2} \cdot c ^ {2} = c ^ {2} \cdot d ^ {2}, $$

which tells us that $a$ and $d$ is divisible by $c$ ; $a$ and $c$ being relatively prime, we conclude that $d$ is divisible by $c$ , i.e., $c \nmid d = c$ . Similarly, we deduce $c \downarrow d = c$ , i.e., $c = d$ . Eliminating $d$ we conclude

$$ \begin{array}{l} \delta x = a / c \quad \delta y = b / c \ a ^ {2} + b ^ {2} = c ^ {2} \ a \downarrow c = 1 b \downarrow c = 1 \ \end{array} $$

Because a shared factor of a and $b$ is shared by C as well, we conclude

and because for all $n$ , ${n}^{2} \equiv 4 \in { 0,1}$ ,

we conclude for each "basic Pythagorean triple"

even.a $\neq$ even.b odd.c

The above can be derived using the addition law (mod 2) for integers

$$ p = p ^ {\prime} + p ^ {\prime \prime} \Rightarrow (\mathrm {e v e n .} p \equiv \mathrm {e v e n .} p ^ {\prime} \equiv \mathrm {e v e n .} p ^ {\prime \prime}) $$

Since we are dealing with rationals, it is very

nice that the above addition law can be

extended to rationals with odd denominator, viz.

$$ \begin{array}{l} o d d. (q \cdot q ^ {\prime} \cdot q ^ {\prime \prime}) \wedge p / q = p ^ {\prime} / q ^ {\prime} + p ^ {\prime \prime} / q ^ {\prime \prime} \ \Rightarrow (e v e n, p \equiv e v e n ^ {\prime}, p ^ {\prime} \equiv e v e n, p ^ {\prime \prime}) \ \end{array} $$

Proof We observe

$$ \begin{array}{l} e v e n. p ^ {\prime} \equiv e v e n. p ^ {\prime \prime} \ = {\text {o d d .} (9 \cdot 9 ^ {\prime} \cdot 9 ^ {\prime \prime}) } \ e v e n. (p ^ {\prime} \cdot q \cdot q ^ {\prime \prime}) \equiv e v e n. (p ^ {\prime \prime} \cdot q \cdot q ^ {\prime}) \ = {p \cdot 9 ^ {1} \cdot 9 ^ {n} \equiv p ^ {\prime} \cdot 9 \cdot 9 ^ {n} + p ^ {\prime \prime} \cdot 9 \cdot 9 ^ {\prime} a n d t h e \ a d d i t i o n l a w f o r i n t e g e r s \ e v e n. (p \cdot q ^ {1} \cdot q ^ {n}) \ = {\text {o d d .} (q ^ {\prime} \cdot q ^ {\prime \prime}) } \ e v e n. p \ \end{array} $$

(End of Proof.)

The applicability of the extended addition law is only constrained by odd. $\left( {{q}^{\prime }{q}^{\prime \prime }}\right)$ : for $q$ we can take ${q}^{\prime }{q}^{\prime \prime }$ (or perhaps one of its divisors), i.e. we can satisfy odd. $q$ .

Consider now a path of k edges, with $\Delta x$ as the difference of the x-coordinates of its endpoints and $\Delta y$ as the difference of their y-coordinates. We then have -with some notational liberty $\Delta x = \sum_{\text{path}} \delta x$ and $\Delta y = \sum_{\text{path}} \delta y$ ;

adding them yields

$$ \Delta x + \Delta y = \sum_ {\mathrm {p a t h}} \frac {a + b}{c} $$

Because all $k$ summands are rational and their denominators are odd, we can

write

$$ \sum_ {\mathrm {p a t h}} \frac {a + b}{c} = p / q \qquad \mathrm {w i t h} \quad \mathrm {o d d}. q $$

Because on account of even. $a \neq$ even. $b$ all $k$ numerators are odd, we can now derive with the rational extension of the addition law and mathematical induction over $k$

$$ e v e n. p \equiv e v e n. k $$

Because for a cyclic path ${\Delta x} + {\Delta y} = 0$ , and ${\Delta x} + {\Delta y} = p/q$ ,we conclude for a cyclic path $p = 0$ ,and hence even. $k$ ,quod erat demonstrandum.

The above argument emerged at the session of the ETAC of 7 September 1999, when I happened

to be in the Netherlands. The discussion was driven by the note FvdS28 "Kladje voor de ETAC. Kleuringsprobleem $Q^{2}$ " by Frans van der Sommen. The advantage of his introduction of Theorem 1 is that the colours have disappeared from the picture by the time the consequences of rationality are explored. He had started that exploration, in which he quickly stressed the central role of rational numbers with an odd denominator (which he called "oddlers").

Austin, 21 September 1999

prof. dr Edsger W. Dgksta Department of Computer Sciences The University of Texas at Austin Austin, TX 78712-1188 USA