On the Connectivity of Unit Distance Graphs

Michael Reid Department of Mathematics University of California Berkeley, CA 94720

August 17, 1996

Abstract. For a number field K ⊆ ℝ, consider the graph G(K^{d}), whose vertices are elements of K^{d}, with an edge between any two points at (Euclidean) distance 1. We show that G(K^{2}) is not connected while G(K^{d}) is connected for d ≥ 5. We also give necessary and sufficient conditions for the connectedness of G(K^{3}) and G(K^{4}).

1 Introduction

For a field K ⊆ ℝ, let G(K^{d}) denote the graph with vertex set K^{d}, with an edge between two points if and only if their Euclidean distance is 1. We may sometimes refer to this graph simply as K^{d}. A well-known and still unsolved problem [4] asks for the chromatic number of the graph G(ℝ^{2}). De Bruijn and Erdös [3] show (using the Axiom of Choice) that the problem of n-coloring a graph is equivalent to that of n-coloring all its finite subgraphs. Furthermore, Benda and Perles [2] show that any finite subgraph of G(ℝ^{2}) may be realized as a subgraph of G(K^{2}) for some suitably chosen real number field (which depends on the finite subgraph).

Fischer [5] introduces the concept of an additive coloring (see Definition 1.1). These seem to be the easiest kinds of colorings to describe, although generally they require many colors. In fact, for any integer N, we can find a real quadratic field K such that G(K^{2}) has no additive coloring with fewer than N colors. For this reason, we restrict our attention to the question of the existence of an additive coloring, without regard to the number of colors it actually uses.

Woodall [11] shows that G(ℚ^{2}) is two-colorable. This result is generalized by Johnson [8], who shows that G(ℚ(\sqrt{n})^{2}) is two-colorable for positive squarefree integers n ≡ 1 or 2 mod 4. Fischer [5] shows that G(ℚ(\sqrt{n})^{2}) is three-colorable for positive squarefree integers n ≡ 0 or 1 mod 3. In each of these cases, the coloring exhibited arises from an additive coloring.

The existence of an additive coloring of G(K^{d}) is mutually exclusive with the condition that the graph is connected. This is shown in Propositions 2.3 and 3.4. The question of connectivity of these graphs is the main focus of this paper. This is a natural approach, since the colorability of a graph is a measure of its connectivity.

Benda and Perles [2] show that G(ℚ^{2}), G(ℚ^{3}) and G(ℚ^{4}) are disconnected, while G(ℚ^{5}) is connected. Zaks [12] shows that G(ℚ(\sqrt{n})^{2}) is disconnected for squarefree positive integers n ≡ 1, 2, 3, 5 or 6 mod 8. He also shows that for a number field K, the graphs G(K^{d}) are connected for sufficiently large d. Fischer [6] shows that G(ℚ(\sqrt{n_{1}}, …, \sqrt{n_{d}})^{2}) is disconnected.

One usually considers a number field without regard to a fixed embedding into ℝ or ℂ. However, the vertices (x_{1}, …, x_{d}) and (y_{1}, …, y_{d}) are adjacent if and only if (x_{1} − y_{1})^{2} + ⋯ + (x_{d} − y_{d})^{2} = 1, so the graph G(K^{d}) is independent of any embedding. Using the above definition, we may define G(K^{d}) for any number field K. Indeed, we shall not make the hypothesis that K has a real embedding; its only purpose is to provide a geometric significance.

We shall use some standard number theory notation. If K is a number field, then O_{K} denotes the ring of integers (i.e. integral closure of ℤ) in K. By a prime of K, we mean a non-zero prime ideal of O_{K}; these are denoted by gothic letters: 𝔓, 𝔭. Also, O_{K,𝔭} denotes the localization of O_{K} at 𝔭, and k(𝔭) denotes the residue field at 𝔭. The 𝔭-adic valuation is denoted by v_{𝔭}, and K_{𝔭} denotes the completion of K with respect to this valuation. Finally, 𝔽_{q} denotes the finite field with q elements.

Note that the connected components of G(K^{d}) are all translates of one another, so that the chromatic number of G(K^{d}) is the same as the chromatic number of any of its components. Let G_{0}(K^{d}) denote the connected component of the origin. This is certainly an additive group under componentwise addition. Fischer [5] makes the following definition.

1.1 Definition. An additive coloring of G_{0}(K^{d}) is a group homomorphism ϕ : G_{0}(K^{d}) → G to a finite additive group, which is also a coloring of G_{0}(K^{d}). By abuse of notation, we also call this an additive coloring of G(K^{d}).

1.2 Definition. The unit sphere, denoted S^{d−1}(K), is the set {(x_{1}, …, x_{d}) ∈ K^{d} |x_{1}^{2} +⋯+x_{d}^{2} = 1}. Note that, by definition, S^{d−1}(K) generates G_{0}(K^{d}) as an additive group.

1.3 Remark. (Fischer [5]) A group homomorphism ϕ : G_{0}(K^{d}) ⟶ G is a coloring if and only if the intersection S^{d−1}(K) ∩ ker ϕ is empty.

1.4 Remarks. If G(K^{d}) is connected, then G_{0}(K^{d}) = G(K^{d}) is divisible, so any homomorphism to a finite group is trivial. Thus G(K^{d}) has no additive coloring if it is connected. Also note that the connected components of G(K^{d}) are in one-to-one correspondence with the cosets of G_{0}(K^{d}). Since G(K^{d}) is divisible, so is the quotient G(K^{d})/G_{0}(K^{d}). In particular, this quotient is either trivial or infinite, so G(K^{d}) has infinitely many connected components if it is disconnected.

2 The case d = 2

For most of this section we assume that \sqrt{−1} ∉ K. We consider the possibility \sqrt{−1} ∈ K in Proposition 2.9.

Identify K^{2} with L = K(i) = K ⊕ Ki, where i^{2} = −1. By complex conjugation, we mean the non-trivial element of Gal(L/K), so \overline{i} = −i. Under this identification, we may describe S^{1}(K) as \{α ∈ L | α\overline{α} = 1\}. Thus S^{1}(K) is a subgroup of L^{∗} and G_{0}(K^{2}) is a subring of L. We denote this subring by B and let A = B ∩ K.

2.1 Remark. Elements of S^{1}(K) are units in B, so from Remark 1.3, a ring homomorphism ϕ : B → R is a coloring if and only if ϕ(B) ≠ 0.

2.2 Lemma. K [respectively L] is the field of fractions of A [respectively B].

Proof. If x ∈ K then z = (1 − x^{2} + 2xi)/(1 + x^{2}) ∈ S^{1}(K). Thus 4x/(1 + x^{2}) = i(\overline{z} − z) and 4/(1 + x^{2}) = z + \overline{z} + 2 are in A. Therefore K is the field of fractions of A. Since i ∈ B, its field of fractions is L. □

2.3 Proposition. The following conditions are equivalent.

i) S^{1}(K) is integral at some prime of L.

ii) B is integral at some prime of L.

iii) K^{2} has an additive coloring.

iv) K^{2} is not connected.

Proof. i) ⇔ ii) is trivial. ii) ⇒ iii). Suppose B is integral at 𝔭. Then the composition B ↪ O_{L,𝔭} → k(𝔭) is an additive coloring. iii) ⇒ iv) from Remark 1.4. iv) ⇒ ii). B is not a field so it has a non-zero prime ideal 𝔟. Let C be the integral closure of B. By the Cohen-Seidenberg “going up” theorem [1, Theorem 5.11, page 62], C has a prime ideal 𝔠 such that 𝔠∩B = 𝔟. Then 𝔠 ∩ O_{L} is a prime of L at which B is integral. □

2.4 Lemma. Let 𝔓 be a prime of L lying over the prime 𝔭 of K. Then the following conditions are equivalent:

i) 𝔭 either ramifies or is inert in L.

ii) 𝔓 = \overline{𝔓}.

iii) S^{1}(K) is integral at 𝔓.

Proof. i) ⇒ ii) is trivial. ii) ⇒ iii). For α ∈ S^{1}(K), we have 1 = α\overline{α}, so 0 = v_{𝔓}(1) = v_{𝔓}(α) + v_{𝔓}(\overline{α}) = 2v_{𝔓}(α). Thus S^{1}(K) is integral at 𝔓. iii) ⇒ i). Otherwise, 𝔭 splits in L as 𝔓\overline{𝔓}, (with 𝔓 ≠ \overline{𝔓}), since Gal(L/K) acts transitively on the primes of L lying over 𝔭. Now choose α ∈ 𝔓, α ∉ \overline{𝔓}. Then \overline{α}/α ∈ S^{1}(K) is not integral at 𝔓, a contradiction. □

2.5 Theorem. Suppose K is a number field with \sqrt{−1} ∉ K. Then infinitely many primes of K are inert in L = K(\sqrt{−1}). Thus the graph G(K^{2}) is not connected and hence admits an additive coloring.

Proof. Only finitely many primes of K ramify in L. Therefore, if all but finitely many primes of K split in L, then ζ_{L}(s) (the zeta function of L) differs from ζ_{K}^{2}(s) by only finitely many Euler factors. However, ζ_{F} (s) has a simple pole at s = 1, for any number field F [10, Theorem 42, page 188], a contradiction. The second assertion then follows. □

2.6 Example. K = ℚ. The rational prime 𝔭 = (2) ramifies in L as 𝔓^{2}, where 𝔓 = (1 + i), so B is integral at 𝔓. The composition B ↪ O_{L,𝔓} → k(𝔓) ≅ 𝔽_{2} is the additive 2-coloring. If p is a prime congruent to 1 mod 4, then we may write p^{2} = a^{2} + b^{2}, with a, b ≠ 0. Then (a ± bi)/p ∈ B, and it follows easily that 1/p ∈ B. Thus ℤ[\frac{1}{5}, \frac{1}{13}, \frac{1}{17}, …][i] ⊆ B. On the other hand, B is integral at 𝔓 and at all primes (p), where p is a rational prime congruent to 3 mod 4. Therefore A = ℤ[\frac{1}{5}, \frac{1}{13}, \frac{1}{17}, …] and B = A[i].

In general, the determination of A and B is more difficult, as they need not be integrally closed.

2.7 Example. K = ℚ(\sqrt{5}). Again, 𝔭 = (2) is prime and ramifies in L as 𝔓^{2}, where 𝔓 = (1 + i). Thus S^{1}(K) is integral at 𝔓, so we have an additive coloring B → k(𝔓) ≅ 𝔽_{4}. Since the residue field extension k(𝔓)/k(𝔭) is trivial, complex conjugation acts trivially on it, whence α ≡ \overline{α} mod 𝔓 for α ∈ S^{1}(K). Then 1 = α\overline{α} ≡ α^{2} mod 𝔓, so α ≡ 1 mod 𝔓. This shows that the image of the coloring B → k(𝔓) ≅ 𝔽_{4} is the subfield 𝔽_{2}. Also, neither A nor B is integrally closed. (In particular, (1 + \sqrt{5})/2 ∉ A.)

2.8 Remark. Theorem 2.5 does not necessarily hold for infinite algebraic extensions. In particular, let K = 𝔸 be the field of real algebraic numbers. Then L = K(i) is algebraically closed. Let β be an arbitrary element of K. For a sufficiently large positive integer N, the polynomial x^{2} − (β/N)x + 1 factors over L as (x − α)(x − \overline{α}), so β = N(α + \overline{α}) ∈ B. It follows that G(𝔸^{2}) is connected.

We now return to consider the possibility that −1 is a square in K.

2.9 Proposition. Suppose K is a number field containing i, where i^{2} = −1. Then G(K^{2}) is connected.

Proof. For any non-zero x ∈ K, we have

(x, 0) = 2 (\frac{4x^{2} + 9}{12x}, i\frac{4x^{2} − 9}{12x}) + 2 (\frac{4x^{2} + 9}{12x}, −i\frac{4x^{2} − 9}{12x}) − (\frac{x^{2} + 9}{6x}, i\frac{x^{2} − 9}{6x}) − (\frac{x^{2} + 9}{6x}, −i\frac{x^{2} − 9}{6x}) ,

so that (x, 0) ∈ G_{0}(K^{2}). It follows that G(K^{2}) is connected. □

3 The case d > 2

Throughout this section, K will denote an arbitrary number field, A_{d}(K) or simply A_{d} will denote the set {x ∈ K | (x, 0, …, 0) ∈ G_{0}(K^{d})} and O(d, K) the group of d-by-d orthogonal matrices over K. Note that the A of the previous section is just A_{2}. Although we no longer have a nice ring structure on K^{d}, we will soon see that A_{d} is in fact a ring. A few preliminary observations are in order.

3.1 Remarks. Note that if d ≤ e, then A_{d}(K) ⊆ A_{e}(K). Also note that G(K^{d}) is connected if and only if A_{d}(K) = K. Thus, if G(K^{d}) is connected, then so is G(K^{e}) for e ≥ d. Finally, note that G_{0}(K^{d}) is O(d, K)-stable, since it is generated by S^{d−1}(K), which is O(d, K)-stable.

3.2 Proposition. The group O(d, K) acts transitively on S^{d−1}(K).

Proof. [9, Proposition 4.7, page 19]. □

3.3 Corollary. A_{d}(K) is a subring of K whose field of fractions is K. In particular, G(K^{d}) is disconnected if and only if there is a prime of K at which A_{d}(K) is integral.

Proof. Let e⃗ = (1, 0, …, 0). We’ve defined A_{d} as {x ∈ K | x · e⃗ ∈ G_{0}(K^{d})}. From Proposition 3.2 this is the same as {x ∈ K | x · S^{d−1}(K) ⊆ G_{0}(K^{d})} = {x ∈ K | x · G_{0}(K^{d}) ⊆ G_{0}(K^{d})}, which is a subring of K. Its field of fractions is K, since A_{2}(K) ⊆ A_{d}(K) and the field of fractions of A_{2}(K) is K (from Lemma 2.2). The second statement follows as in the proof of Proposition 2.3, mutatis mutandis. □

3.4 Proposition. K^{d} has an additive coloring if and only if it is not connected.

Proof. We’ve already seen the “only if” part (Remark 1.4), so suppose that G(K^{d}) is not connected. Then from Corollary 3.3, A_{d} is integral at some prime 𝔭 of K. Let p be the rational prime over which 𝔭 lies. Then e⃗ = (1, 0, …, 0) ∈ S^{d−1}(K) is not p-divisible in G_{0}(K^{d}), so from Proposition 3.2, S^{d−1}(K) ∩ pG_{0}(K^{d}) = ∅. Thus G_{0}(K^{d}) → G_{0}(K^{d})/pG_{0}(K^{d}) is an additive coloring. □

3.5 Definition. If K is a field with valuation v, we say that S^{d−1}(K) is integral with respect to v if each v(x_{i}) ≥ 0 for every (x_{1}, …, x_{d}) ∈ S^{d−1}(K). If K is a number field and 𝔭 is a prime of K, we say that S^{d−1}(K) is integral at 𝔭 if it is integral with respect to v_{𝔭}. If K is a p -adic field with valuation v, we simply say that S^{d−1}(K) is integral if it is integral with respect to v.

We now focus our attention on the case d = 3. We state the following lemma in some generality, since we need it for p -adic fields as well as number fields.

3.6 Lemma. Let K be a field with valuation v. Suppose that S^{2}(K) is not integral with respect to v. Then for any C > 0, we may write 1 = x^{2} + y^{2} + z^{2} in K with v(x) < −C.

Proof. By hypothesis, we may write 1 = x_{0}^{2} + y_{0}^{2} + z_{0}^{2} with v(x_{0}) < 0. Let x_{1} = x_{0}^{2}. Then 1 − x_{1}^{2} = (1 − x_{0}^{2})(1 + x_{0}^{2}) = (y_{0}^{2} + z_{0}^{2})(1 + x_{0}^{2}) = y_{1}^{2} + z_{1}^{2}, for y_{1} = y_{0} − x_{0}z_{0} and z_{1} = z_{0} + x_{0}y_{0}. Since v(x_{1}) = 2v(x_{0}), by repeating this process, we may write 1 = x^{2} + y^{2} + z^{2} with v(x) arbitrarily negative. □

We next show that integrality of S^{2}(K) may be tested in the local field.

3.7 Proposition. Let 𝔭 be a prime of K and let K_{𝔭} be the completion of K at 𝔭. Then S^{2}(K) is integral at 𝔭 if and only if S^{2}(K_{𝔭}) is integral.

Proof. If S^{2}(K_{𝔭}) is integral, then certainly S^{2}(K) is integral at 𝔭. Conversely, suppose that S^{2}(K_{𝔭}) is not integral. Then from Lemma 3.6 we may write 1 = x^{2} + y^{2} + z^{2} in K_{𝔭} with v_{𝔭}(2x) < 0. Furthermore, one of v_{𝔭}(y), v_{𝔭}(z) must also be negative; suppose the former is. In K, choose approximations x_{0}, y_{0}, z_{0} to x, y, z, respectively, such that v_{𝔭}(x_{0}) = v_{𝔭}(x), v_{𝔭}(y_{0}) = v_{𝔭}(y), v_{𝔭}(z_{0}) = v_{𝔭}(z) and x_{0}^{2} + y_{0}^{2} + z_{0}^{2} = 1 + ϵ, where v_{𝔭}(ϵ) > 0. Then we have

(2x_{0}y_{0})^{2} + (2x_{0}z_{0})^{2} + (x_{0}^{2} − y_{0}^{2} − z_{0}^{2})^{2} = (x_{0}^{2} + y_{0}^{2} + z_{0}^{2})^{2} = (1 + ϵ)^{2}.

Now divide by (1 + ϵ)^{2} and note that v_{𝔭}(2x_{0}y_{0}/(1 + ϵ)) = v_{𝔭}(2x_{0}y_{0}) = v_{𝔭}(2xy) < 0. Thus S^{2}(K) is not integral at 𝔭. □

3.8 Proposition. Let 𝔭 be an odd prime of K. Then S^{2}(K) is not integral at 𝔭.

Proof. Let p be the odd rational prime over which 𝔭 lies. As x ranges over all integers, there are (p + 1)/2 different residue classes for 1 + x^{2} mod p. Similarly, −y^{2} takes values in (p + 1)/2 different residue classes. Thus, by the pigeonhole principle, there are integers x and y such that p divides 1 + x^{2} + y^{2}. Then

(\frac{1 − x^{2} − y^{2}}{1 + x^{2} + y^{2}} , \frac{2x}{1 + x^{2} + y^{2}} , \frac{2y}{1 + x^{2} + y^{2}} ) ∈ S^{2}(ℚ) ⊆ S^{2}(K).

Since p does not divide both 2x and 2y, this shows that S^{2}(K) is not integral at 𝔭. □

Therefore we need only consider even primes of K. These are handled by the following.

3.9 Proposition. Let K be a finite extension of ℚ_{2}. The following conditions are equivalent: i) S^{2}(K) is not integral. ii) We may write −1 = x^{2} + y^{2} in K. iii) [K : ℚ_{2}] is even.

Proof. i) ⇒ ii). From Lemma 3.6, we may write 1 = x^{2} + y^{2} + z^{2} in K with v(2x) < 0. Then we have −(1 − (1/x)^{2}) = (y/x)^{2} + (z/x)^{2}. Since v(2x) < 0, the series

(1 − \frac{1}{x^{2}} )^{1/2} = ∑_{n=0}^{∞}(−1)^{n}x^{−2n} ( n^{\frac{1}{2}} )

converges, so 1 − (1/x)^{2} is a square in K. Therefore, −1 is a sum of two squares in K. ii) ⇒ iii). Suppose to the contrary that [K : ℚ_{2}] is odd. By hypothesis, −1 is a norm from K(\sqrt{−1}) to K, so −1 = (−1)^{[K:ℚ_{2}]} is a norm from K(\sqrt{−1}) to ℚ_{2}. However, it is easy to check that −1 is not even a norm from ℚ_{2}(\sqrt{−1}) to ℚ_{2}. This contradiction shows that [K : ℚ_{2}] must be even. iii) ⇒ i). We distinguish two cases: K has even inertial degree over ℚ_{2}; K has even ramification degree over ℚ_{2}. In the first case, K contains the unique unramified quadratic extension of ℚ_{2}, which is just ℚ_{2}(ζ), where ζ is a primitive cube root of 1. Then we have 1 = (1/2)^{2} + (1 + ζ/2)^{2} + (1 + ζ^{2}/2)^{2}.

In the second case, let t be a uniformizing parameter and let v(2) = 2n. Then write 2 = αt^{2n}, with v(α) = 0. Let the residue field of K be 𝔽_{2^{r}}. The image of α in 𝔽_{2^{r}} has multiplicative order (dividing) 2^{r} − 1, so v(α^{2^{r}} + α) > 0. Let z = α^{2^{r−1}}t^{n}. Then z^{2} + 2 = (α^{2^{r}} + α)t^{2n}, so v(z^{2} + 2) > v(2). If z^{2} + 2 ≠ 0, we have

1 = (\frac{2}{z^{2} + 2})^{2} + (\frac{2z}{z^{2} + 2})^{2} + (\frac{z^{2}}{z^{2} + 2})^{2}

and v(2/(z^{2} + 2)) < 0. If z^{2} + 2 = 0, replace z by z(1 + ϵ) for some small ϵ and use the above. (Alternatively, write 1 = (3/4)^{2} + (3/4)^{2} + (z/4)^{2}.) □

Translating the criterion of Proposition 3.9 into the notion of the splitting of primes, we have proven the following.

3.10 Theorem. The graph G(K^{3}) is connected if and only if the rational prime (2) splits as 𝔓_{1}^{e_{1}} ⋯ 𝔓_{r}^{e_{r}}, with each e_{i}f_{i} even, where f_{i} is the degree of the residue field extension k(𝔓_{i})/𝔽_{2}. In particular, if [K : ℚ] is odd, then G(K^{3}) is not connected.

Proof. Note that e_{i}f_{i} is just the degree of the local extension K_{𝔓_{i}}/ℚ_{2}. The second statement follows since [K : ℚ] = ∑ e_{i}f_{i}. □

3.11 Theorem. The graph G(K^{4}) is connected if and only if G(K^{3}) is connected.

Proof. If G(K^{3}) is connected, then so is G(K^{4}). Conversely, suppose G(K^{4}) is connected and let 𝔭 be any prime of K. We must show that S^{2}(K) is not integral at 𝔭. Since K^{4} is connected, we have (x, y, z, w) ∈ S^{3}(K) with v_{𝔭}(2x) < 0. Also, 4x^{2} = 2(x^{2}+y^{2})+2(x^{2}+z^{2})−2(y^{2}+z^{2}), so not all three quantities 2(x^{2} + y^{2}), 2(x^{2} + z^{2}), 2(y^{2} + z^{2}) can be integral at 𝔭. Without losing generality, (we no longer need the fact that v_{𝔭}(2x) < 0), suppose that v_{𝔭}(2(x^{2} +y^{2})) < 0. Then (x^{2} +y^{2} −z^{2} −w^{2}, 2(xw −yz), 2(xz +yw)) ∈ S^{2}(K) and x^{2} + y^{2} − z^{2} − w^{2} = 2(x^{2} + y^{2}) − 1, so S^{2}(K) is not integral at 𝔭. □

3.12 Examples. S^{2}(ℚ) is integral at (2), so G(ℚ^{3}) (and thus also G(ℚ^{4})) is not connected. Let K = ℚ(\sqrt{2}). The rational prime 𝔭 = (2) ramifies in K as 𝔓^{2}, where 𝔓 = (\sqrt{2}). Thus S^{2}(K) is not integral at 𝔓, so G(K^{3}) is connected.

The case d > 4 is now very easy to treat.

3.13 Theorem. The graph G(K^{d}) is connected for all d > 4.

Proof. It suffices to show that G(K^{5}) is connected. Note that (1/2, 0, 0, 0, 0) = (1/4, 1/4, 1/4, 3/4, 1/2) + (1/4, −1/4, −1/4, −3/4, −1/2), so 1/2 ∈ A_{5}(K). Thus A_{5} is not integral at any prime, and therefore is all of K. □

4 Further Questions

We pose here several questions for further investigation, keeping in mind the goal of determining the chromatic number of ℝ^{2}.

4.1 Question. What do the connected components look like? Describe the rings A_{d}(K) and the connected components G_{0}(K^{d}) explicitly. This has been done in some cases by Fischer [6]. When are the rings A_{d}(K) integrally closed? Is G_{0}(K^{3}) always equal to (A_{3}(K))^{3}? The answer to the corresponding question is “no” for both G_{0}(K^{2}) and G_{0}(K^{4}).

4.2 Question. What types of colorings are there? Fischer [5] shows that a 2-coloring of G(K^{d}) necessarily arises from an additive coloring. What can be said about n-colorings for other values of n? Find a way to explicitly describe non-additive colorings.

4.3 Question. Can we reduce the problem to a smaller field? Benda and Perles [2] show that any finite subgraph of G(ℝ^{2}) may be found in G(𝔸^{2}), where 𝔸 is the field of real algebraic numbers. Is there a smaller subfield of ℝ with the same property? In particular, may we find all finite subgraphs in G(𝕂^{2}), where 𝕂 is the field of real constructible numbers?

For the sake of completeness, and also because [2] is not readily available, we include the following proof.

4.4 Theorem. (Benda, Perles [2]) Let G be a finite subgraph of G(ℝ^{2}). Then G is isomorphic to a finite subgraph of G(𝔸^{2}), where 𝔸 is the field of real algebraic numbers.

Proof. We may write a first order statement expressing the property that G(K^{2}) has a subgraph isomorphic to G. By Tarski’s theorem (see [7, page 340]), any such statement which holds for a given real closed field (e.g. ℝ) holds for all real closed fields, in particular 𝔸. □

5 Acknowledgments

It is a pleasure to thank Joseph A. Gallian, without whose encouragement this paper would not have been possible. Thanks also to the University of Minnesota, Duluth for its hospitality. The author was partially supported by a Department of Education Graduate Assistance in Areas of National Need Fellowship.

6 References

[1] M.F. Atiyah and I.G. MacDonald, Introduction to Commutative Algebra, Addison-Wesley, Reading, 1969. MR 39 #4129

[2] M. Benda and M. Perles, Colorings of metric spaces Geombinatorics 9 (2000), no. 3, 113–126. MR 2001b:52031

[3] N.G. de Bruijn and P. Erdös, A colour problem for infinite graphs and a problem in the theory of relations, Koninklijke Nederlandse Akademie van Wetenschappen 13 (1951) 371–373. MR 13,763g

[4] Paul Erdös, Some new problems and results in graph theory and other branches of combinatorial mathematics, Combinatorics and Graph Theory, Lecture Notes in Math. 885, Springer-Verlag, New York. MR 83k:05038

[5] Klaus G. Fischer, Additive k-colorable extensions of the rational plane, Discrete Mathematics 82 (1990) 181–195. MR 91m:05082

[6] Klaus G. Fischer, The connected components of the graph ℚ(\sqrt{N_{1}}, …, \sqrt{N_{d}})^{2}, Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Florida, 1989). Congressus Numerantium 72 (1990) 213–221. MR 91c:05116

[7] Nathan Jacobson, Basic Algebra I, Second Edition, W.H. Freeman and Company, New York, 1985. MR 86d:00001

[8] P.D. Johnson, Jr., Two-colorings of real quadratic extensions of ℚ^{2} that forbid many distances, Eighteenth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Florida, 1987). Congressus Numerantium 60 (1987) 51–58. MR 89f:11159

[9] T.Y. Lam, The Algebraic Theory of Quadratic Forms, Benjamin, Reading, 1973. MR 53 #277

[10] Daniel A. Marcus, Number Fields, Universitext, Springer-Verlag, New York, 1977. MR 56 #15601

[11] D.R. Woodall, Distances realized by sets covering the plane, Journal of Combinatorial Theory. Series A 14 (1973) 187–200. MR 46 #9868

[12] Joseph Zaks, On the connectedness of some geometric graphs, Journal of Combinatorial Theory. Series B 49 (1990) 143–150. MR 91d:05062