VIETNAM NATIONAL UNIVERSITY
UNIVERSITY OF SCIENCE
FACULTY OF MATHEMATICS, MECHANICS AND INFORMATICS
Hoang Duc Trung
ODD-DISTANCE GRAPHS
Undergraduate Thesis
Advanced Undergraduate Program in Mathematics
Hanoi - 2012
VIETNAM NATIONAL UNIVERSITY
UNIVERSITY OF SCIENCE
FACULTY OF MATHEMATICS, MECHANICS AND INFORMATICS
Hoang Duc Trung
ODD-DISTANCE GRAPHS
Undergraduate Thesis
Advanced Undergraduate Program in Mathematics
Thesis Advisor : Prof.Dr. Moshe Rosenfeld
Hanoi - 2012
Acknowledgments
My first thanks go to my thesis supervisor Prof.Moshe Rosenfeld, who inspired
my development as a student of Mathematics. I have enjoyed more Mathematics
after long discussions and patient working with my thesis supervisor.
I am deeply grateful to the Professors in the Faculty of Mathematics, Me-
chanics and Informatics , especially Ass.Prof Vu Hoang Linh and Ass.Prof. Le
Minh Ha , who accepted and encouraged me to work with Prof. Moshe Rosenfeld.
Last but not least, I would like to thank my math friends in advanced and
honor programs.
Hoang Duc Trung
Ha Noi, Novemver, 2012
ii
Contents
Acknowledgments ii

Contents iii
Introduction 1
1 Background And Motivation 2
1.1 Introductions to graph theory . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Graph basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Graph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.3 Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.4 The Unit distance graph . . . . . . . . . . . . . . . . . . . . . 8
1.1.5 The odd distance graph . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Two four color problems in the plane . . . . . . . . . . . . . . . . . . 10
1.2.1 The original four color problem . . . . . . . . . . . . . . . . . 10
1.2.2 The alternative four color problem in the plane . . . . . . . . 11
1.3 The Probabilistic Method . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.1 Random Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.2 Expectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.3 Graph of high girth and high chromatic number . . . . . . . 16
2 The integral distance problems 18
2.1 The Erd
¨
os-Anning Problems . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Counting unit distances . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 The odd distance graph 22
3.1 Subgraphs of odd distance graphs . . . . . . . . . . . . . . . . . . . . 22
3.1.1 2-colorable graphs . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.2 3-colorable graphs . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.3 4-colorable graphs . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Subgraphs of odd distance graph in higher dimensions . . . . . . . 27
3.2.1 Results in 3-dimensional space . . . . . . . . . . . . . . . . . 27
iii
CONTENTS

3.2.2 Results in n-dimensional space . . . . . . . . . . . . . . . . . 29
3.3 Chromatic number of the odd distance graph . . . . . . . . . . . . . 30
3.3.1 The chromatic number of G
od d
(Q
2
) . . . . . . . . . . . . . . 32
Conclusion 34
4 References 35
Appendix A 36
Appendix B 40
Bibliography 41
iv
Introduction
In this thesis, we study the odd-distance graph and related graphs.
The first chapter covers the basic concepts of graph theory. We also introduce
two famous infinite graphs: the unit-distance graph and the odd-distance graph.
To clarify the motivation, we trace their history, development and related con-
jectures.
The second chapter introduces the integral distance problem in the plane,
that first appeared in the paper of Paul Erdos in 1946. Many other researchers
investigated many related problems. This activity still goes on these days.
Chapter 3 covers the odd distance graphs and its investigations from mathe-
maticians in recent years. We try to work not only in the Euclidean two dimen-
sional space but also Euclidean n-dimensional space or space of rational points.
1
CHAPTER 1
Background And Motivation
1.1 Introductions to graph theory
The paper written by Leonhard Euler on the Seven Bridges of Konigsberg and

published in 1736 is regarded as the first paper in the history of graph theory.
Figure 1.1: The seven bridges of Konigsberg
The problem was to find a walk through the city that would cross each bridge
once and only once. The islands could not be reached by any route other than
the bridges, and every bridge must be crossed exactly once. The walk need not
start and end at the same spot. Euler proved that the problem has no solution.
1.1.1 Graph basics
A graph G is an ordered pair (V(G), E(G)), consisting of a set V(G) of vertices
and a set E(G) of edges . A pair (u, v) is usually written simply as uv .
Graphs are dynamic data structures. They can grow (adding vertices and edges)
or shrink (deleting vertices and edges). When a vertex is deleted, all edges inci-
dent with it are also deleted. For example :
2
1.1. Introductions to graph theory
Example 1.1 V = {All the students at VNU }
E = {(x,y) — x and y attend the same class}
Example 1.2 V = {All cities in Vietnam }
E = {(x,y) — There is a direct flight from x to y}
We use the term graph for G(V, E) if the edges (x, y) are unordered pairs.
If the edges of G( V, E) are ordered pairs (oriented) we call G(V, E) a digraph
(directed graph).
The degree of a vertex x ∈ V(G) , denoted by d
G
(v) is the number of edges adja-
cent to v in G .
A graph G is r-regular if all vertices have degree r.
Figure 1.2: A 5-regular graph
A graph G is labelled if the vertices are assigned unique names.
Paths,walks
An edge of form (x, x ) is called a loop.

If a graph G contains the edges (x, y) more than once ,we say that it has parallel
edges.
A loop-less graph without parallel edges is a simple graph .
A walk in a graph is a sequence (v
0
, E
1
, v
1
, E
2
, , v
k−1
, E
k
, v
k
) such that E
i
=
(v
i−1
, v
i
). The length of a walk is the number of edges it contains .
A walk in G(V, E) in which all vertices are distinct is a path .
A walk (v
0
, E
1

, v
1
, E
2
, , v
k−1
, E
k
, v
k
) in which v
1
= v
k
is a closed walk .
A closed walk in which v
i
̸= v
j
, for i ̸= j, 0 ≤ i, j < k is called a cycle .
3
1.1. Introductions to graph theory
Subgraphs, Tree
A graph H(V
1
, E
1
) is a subgraph of G(V, E) if V
1
⊂ V and E

1
⊂ E.
A graph H( V
1
, E
1
) is an induced subgraph of G(V, E) if (x, y) ∈ E
1
if and only if
(x, y) ∈ E
A subgraph H(V
1
, E
1
) of G(V, E) is a spanning subgraph of G if V
1
= V.
A graph G = G (V, E) is connected if between any pair of vertces there is a path.
A connected graph without cycles is called a tree.
Figure 1.3: Example of induced and spanning subgraphs
Figure 1.4: A labeled tree with 6 vertices and 5 edges.
4
1.1. Introductions to graph theory
1.1.2 Graph Coloring
Assigning labels to vertices or edges of graphs is a fundamental tool in many
applications, proofs and algorithms on graphs. We call this procedure coloring .
In various applications we use different rules for coloring.
Definition. The chromatic number of a graph G , denoted by χ(G), is the
smallest number of colors needed to color the vertice so that vertices connected
by an edge are assigned different colors.

Example 1.3 The chromatic numbers of Petersen graph is 3.
Figure 1.5: χ(Petersengraph) is 3.
Example 1.4 The chromatic numbers of Clebsch graph is 4.
Figure 1.6: χ(Clebschgraph) is 4.
Definition The chromatic index of a graph G , denoted by χ
1
(G), is the small-
est number of colors need to color the edges so that if two edges share a vertex
they are assigned different colors.
5
1.1. Introductions to graph theory
Figure 1.7: A proper coloring of the edges of a 4-regular graph by 5 colors.
1.1.3 Planar graphs
A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn
on the plane in such a way that its edges intersect only at their endpoints. In
other words, it can be drawn in such a way that no edges cross each other. Such
a drawing is called a plane graph or planar embedding of the graph. Here are
some examples of planar graph.
Example 1.5 The Butterfly graph is planar.
Figure 1.8: The Butterfly graph
Example 1.6 The complete graph K
4
is planar.
Figure 1.9: The complete graph K4
We also give some examples of nonplanar graphs :
6
1.1. Introductions to graph theory
Example 1.7 The complete graph K
5
is not planar.

Figure 1.10: The complete graph K5
Example 1.8 The graph K
3,3
is not planar.
Figure 1.11: The K
3,3
graph
A very famous theorem related to planar graphs is Euler’s theorem. It is a con-
nection about number of vertices, edges and faces in a finite, connected planar
graph.
Theorem 1.9 (Euler’s Theorem) If a finite, connected, planar graph is drawn
in the plane without any edge intersections, and v is the number of vertices, e
is the number of edges and f is the number of faces (regions bounded by edges,
including the outer, infinitely large region), then : v − e + f = 2
Example 1.10 In K
4
we have v = 4, e = 6 and f = 4.
Palanarity being such a fundamental property, the problem of deciding whether
a given graph is planar is clearly of great importance. A major step towards
this goal is provided by the following characterization of planar graphs, due to
Kuratowski (1930).
Any graph derived from a graph G by a sequence of edge subdivisions is called
a subdivision of G or a G − subdivision. Subdivisions of K
5
and K
3,3
are shown in
the following figure.
7
1.1. Introductions to graph theory

Figure 1.12: (a) A subdivision of K
5
, (b) a subdivision of K
3,3
Theorem 1.11 (Kuratowski’s Theorem) A graph is planar if and only if it con-
tains no subdivision of either K
5
or K
3,3
A subdivision of K
5
or K
3,3
is consequently called a Kuratowski subdivision. For
an alternative proof of Kuratowski’s theorem, we can see [17].
1.1.4 The Unit distance graph
In mathematics, and particularly geometric graph theory, a unit distance graph
is a graph formed from a collection of points in the Euclidean plane by connecting
two points by an edge whenever the distance between the two points is exactly
one. Edges of unit distance graphs sometimes cross each other, so they are not
always planar; a unit distance graph without crossings is called a ”matchstick
graph”.
Example 1.12 The Petersen graph is a unit distance graph: it can be drawn in
the plane with each edge having unit length.
Figure 1.13: Petersen graph
One of the most famous problems in discrete mathematics asks about the
chromatic number of unit distance graph , known as Hadwiger-Nelson Problem.
8
1.1. Introductions to graph theory
Problem 1.13 How many colors are needed to color the plane so that no two

points at unit distance are the same color?
The Hadwiger-Nelson problem concerns the chromatic number of unit dis-
tance graphs. It is known that there exist unit distance graphs requiring four
colors in any proper coloring, and that all such graphs can be colored with at
most seven colors. Surprisingly, the correct value may actually depend on the
choice of axioms for set theory (Shelah and Soifer 2003) (see [12]) .
Another important open problem concerning unit distance graphs asks how
many edges they can have relative to their number of vertices.
1.1.5 The odd distance graph
The odd distance graph G
od d
is the infinite graph whose vertices are the points
of the Euclidean plane R
2
, two vertices connected by an edge if their distance
is an odd integer. The ”birth” of this graph happened in a conversation between
M.Rosenfeld and P. Erd
¨
os in 1994 at conference on Graph Theory, Combinatorics
and Computation in Boca Raton, Florida. This graph is interesting since no 4
points in R
2
can have all 6 distances odd integers. M.Rosenfeld asked : ”what is
the chromatic number of G
od d
? ” . Erd
¨
os added: ”How many distances among n
points in the plane can be odd integers ?”. Thus started the pursuit of unveiling
the mysteries of G

od d
, whose ”close cousin ,” the unit-distance graph, has been
haunting mathematicians since its introduction in 1950.
Here is an example of a subgraph of G
od d
:
Figure 1.14: A subgraph of G
od d
In the above figure , we note that ∠DOA = ∠DOC =
2π
3
and ∆AOB, ∆BOC
are equi-triangular. So, using the laws of cosine, if we put OD = 3 and OA = 5 ,
9
1.2. Two four color problems in the plane
we have AD
2
= OD
2
+ OA
2
−2OA.OD.cos∠DOA = 3
2
+ 5
2
−2.3.5.cos120
o
= 49 .
That gives AD = 7
1.2 Two four color problems in the plane

1.2.1 The original four color problem
The conjecture was first proposed in 1852 when Francis Guthrie, while trying to
color the map of counties of England, noticed that only four different colors were
needed. Francis inquired with Frederick, Francis’s brother, regarding it, who
then took it to De Morgan, mathematics professor in University College Lon-
don. The problem stated that given any separation of a plane into contiguous
regions producing a figure called a map, no more than four colors are required to
color the regions of the map so that no two adjacent regions have the same color.
The following figure indicate a four-coloring of a map of the states of the United
States.
Figure 1.15: A four-coloring of United States
In order to translate the Four-Color Problem into the language of graph the-
ory, we need the notion of a face coloring of a plane . A k-face coloring of a plane
graph is an assignment of k colors to its faces. The coloring is proper if no two
adjacent faces are assigned the same color . A plane graph is k-face-colorable
if it has a proper k-face coloring. For example , the figure 1.16 shows a proper
4-face- coloring of the triangular prism :
Figure 1.16: A 4-face-coloring of the triangular prism
10
1.2. Two four color problems in the plane
Conjecture 1.14 (The Four-Color Conjecture) Every plane graph without cut
edges is 4-face-colorable
”The four color theorem was proved in 1976 by Kenneth Appel and Wolfgang
Haken. It was the first major theorem to be proved using a computer. Appel and
Haken’s approach started by showing that there is a particular set of 1,936 maps,
each of which cannot be part of a smallest-size counterexample to the four color
theorem. Appel and Haken used a special-purpose computer program to confirm
that each of these maps had this property. Additionally, any map (regardless of
whether it is a counterexample or not) must have a portion that looks like one
of these 1,936 maps. Showing this required hundreds of pages of hand analysis.

Appel and Haken concluded that no smallest counterexamples exists because
any must contain, yet not contain, one of these 1,936 maps. This contradiction
means that there are no counterexamples at all and that the theorem is therefore
true.” (wikipedia)
Figure 1.17: Kenneth Ira Appel and Wolfgang in the 1970s
1.2.2 The alternative four color problem in the plane
In 1950, Edward Nelson , a student at the University of Chicago, formulated
the alternative four-color problem: What is the minimum number of colors for
coloring the points of the plane so that points at unit distance apart recieve
distinct colors. Nelson himself showed that at least four colors are needed
Theorem 1.15 The number of colors for coloring the points of the plane so that
points at unit distance apart recieve distinct colors is at least 4.
11
1.2. Two four color problems in the plane
PROOF Place on the given 3-colored plane what we now call The Moser Spindle.
Every edge in the spindle has length 1.
Figure 1.18: The Moser Spindle
Assume that the seven vertices of the spindle do not contain a monochromatic
unit distance segment. Call the colors used to color the plane red, white, and
blue. Let the point A be the red, then B and C must be one white and one blue.
Therefore, D is red. Similarly E and F must be white and one blue, so G is
red. We found a monochromatic segment DG of length 1 in contradiction to our
assumption.
Soon after learning about the problem form Ed Nelson, John Isbell proved
that the plane can be colored by seven colors. The upper bound of seven on the
chromatic number follows from the existence of a ”tessellation” of the plane by
regular hexagons, with diameter slightly less than one, that can be assigned
seven colors in a repeating pattern to form a 7-coloring of the plane
Figure 1.19: A seven-coloring of the plane, and a four-chromatic unit distance
graph in the plane

.
12
1.3. The Probabilistic Method
The answer to the alternative four color problem is unknown, but has been
narrowed down to one of the numbers 4, 5, 6 or 7. The correct value may actually
depend on the choice of axioms for set theory (Shelah and Soifer 2003) (see[12]).
1.3 The Probabilistic Method
1.3.1 Random Graphs
A (finite) probabilistic space (Ω , P) consists of a finite set Ω, called the sample
space, and a probability function P : Ω → [0, 1] satisfying
∑
ω⊂Ω
P(ω) = 1. We
may regard the set G
n
of all labeled graphs on n vertices (or, equivalently, the set
of all spanning subgraph of K
n
) as the sample space of a finite probability space
(G
n
, P). The result of selecting an element G of this sample space according to
the probability function P is called a random graph .
The simplest example of such a probability space arises when all graphs G ⊂ G
n
have the same probability of being chosen. Because |G
n
| = 2
N
where N =

(
n
2
)
,
the probability function in this case is :
P(G) = 2
−N
for all G ∈ G
n
. A more refined probability space on the set G
n
may be obtained by
fixing a real number p between 0 and 1 and choosing each edge with probability
p, these choices again being independent of one another. Because 1 − p is the
probability that any particular edge is not choosen, the resulting probability
function P is given by
P(G) = p
m
(1 − p)
N−m
for each G ∈ G
n
where m = e(G). This space is denoted by G
n,p
. For example,
G
3,p
has as sample space the 2
(

3
2
)
spanning subgraphs of K
3
shown in the follow-
ing figure with the probability function indicated.
Note that the smaller the value of p, the higher the probability of obtaining a
sparse graph. We are interested in computing or estimating the probability that
a random graph has a particular property.
To each graph property, such as connectedness, Hamiltonian, bipartite, pla-
nar there corresponds a subset of G
n
, namely those members of G
n
, which
have the given property. The probability that a random graph has this par-
ticular property is then just the sum of the probabiliies of these graph. For
instance, the probability that a random graph in G
3,p
is connected is equal to
3p
2
(1 − p) + p
3
= p
2
(3 − 2p) , the probability that it is bipartite is (1 − p)
3
+

13
1.3. The Probabilistic Method
Figure 1.20: The probability space G
3,p
3(1 − p)
2
p + 3(1 − p)p
2
= (1 − p)(1 + p + p
2
), and the probability that it is both
connected and bipartite is 3p
2
(1 − p).
In a probability space (Ω, P), any subset A of Ω is referred to as an event, and
the probability of the event A is defined by :
P(A) =
∑
ω∈A
P(ω)
Events A and B in a probability space (Ω, P) are indepenndent if P(A ∩ B) =
P(A)P(B); otherwise, they are dependent. More generally, events A
i
, i ∈ I, are
(mutually) indepenndent if, for any subset S of I,
P(∩
i∈S
A
i
) =

∏
i∈S
P(A
i
)
For example, if A is the event ’G is connected’ and B is the event ’G is bipartite’
in the space G
3,p
, then (unless p = 0 or p = 1)
P(A)P(B) = p
2
(3 −2p)(1 − p)(1 + p + p
2
) ̸= 3p
2
(1 − p) = P(A ∩ B)
Thus these two events are dependent. In other words, the knowledge that G is
bipartite has a bearing on the probability of it being connected.
Much of graph theory is concerned with the study of basis parameters, such as
the connectivity, the clique number, or the stability number. As we have seen
the values of these parameters provide much information about a graph and its
properties. In the context of random graphs, functions such as these are known
as random variables, because they depend on which graph happens to be se-
lected. More generally, a random variable on a probability space (Ω, P) is any
14
1.3. The Probabilistic Method
real-valued function defined on the sample space Ω. In the combinatorial con-
text, random variables are frequently integer-valued. Here is a typical example
.
Let S be a set of vertices of a random graph G ∈ G

n,p
. We may associate with S a
random variable X
s
defined by :
X
S
(G)



1 if S is a independent set of G
0 otherwise
The random variable X
s
is an example of what is known as an indicator random
variable, because it indicates whether the set S is an independent set of G. More
generally, each event A in a probability space (Ω, P) has an associated indicator
random variable X
A
, defined by:
X
A
(ω)



1 if ω ∈ A
0 otherwise
(In the preceding example, A is simply the event that S is an independent set).

Thus to each event there corresponds a random variable. Conversely, with each
random variable X and each real number t, we may associate the event
ω ∈ Ω : X(ω) = t
The event is denoted for short by X = t. Analogously, one may define four related
events : X < t, X ≤ t, X ≥ t and X > t.
Random variable X
i
, i ∈ I, are (mutually) independent if the events X
i
= t
i
, i ∈ I,
are independent for all real numbers t
i
. Random variables are dependent if they
are not independent.
1.3.2 Expectation
The average value, or mean, of a random variable X is called its expectation, and
denoted by E(X)). Thus
E(X) =
∑
ω∈Ω
X(ω)P(ω)
Expectation is a linear function. In other words, for random variables X and Y,
and real numbers r and s,
E(rX + sY) = rE(X) + sE(Y)
This property is referred to as linearity of expectation. Secondly, if X
A
is an
indicator random variable,

E(X
A
) = P(X
A
= 1)
15
1.3. The Probabilistic Method
We note that the identity E(XY) = E(X)E(Y) does not hold in general , although
it is valid when X and Y are independent random variables.
1.3.3 Graph of high girth and high chromatic number
We return to the notion of a chromatic number χ(G). Observe that if a graph
does not contain any cycles, X(G) ≤ 2 because every component is a tree that can
be colored easily by 2 colors. More generally, consider graphs of girth l, which
means that the length of the shortest cycle is l. If l is large, this means that
starting from any vertex, the graph looks like a forest within distance l/2 + 1.
One might expect that such graphs can be allso colored using small number of
colors, since locally they can be colored using 2 colors. However, this is far from
being true, as shown by a classical application of the probabilistic method.
Theorem 1.16 For any k and l, there is a graph of chromatic number > k and
girth > l
PROOF We start by generating a random graph G
n,p
, where each edge appears
independently with probability p. We fix a value λ ⊂ (0,
1
l
) and we set p =
n
λ−1
. Let X be the number of cycles of length at most l in G

n,p
. The number of
potential cycles of length j is certainly atmost n
j
, and each of them appears with
probability p
j
,therefore :
E[X] ≤
l
∑
j=3
n
j
p
j
=
l
∑
j=3
n
λj
≤
n
λl
1 −n
−λ
Because λl < 1, this is less than
n
4

for n sufficiently large . By Markov’s inequal-
ity, Pr[X ≥
n
2
] ≤
1
2
. Note that we are not able to prove that there are no short
cycles in G
n,p
, but we will deal with this later .
Now let us consider the chromatic number of G
n,p
. Rather than the chromatic
number χ(G) itself, we analyze the independence number α(G) ,i.e. the size of
the largest independent set in G . Since every color class forms an independent
set , it’s easy to see that χ(G) ≥ |V(G)|/α(G). We set a = ⌈
3
p
lnn⌉ and consider
the event that there is an independent set of size a. By the union bound ,we get :
Pr[α(G) ≥ a] ≤

n
a

(1 − p)
(
a
2

)
≤ n
a
e
−pa(a−1)/2
≤ n
a
n
−3(a−1)/2
→ 0
For n sufficiently large ,this probability is less than 1/2. Hence, again by the
union bound , we get
Pr[X ≥ n/2 or α(G) ≥ a] < 1
16
1.3. The Probabilistic Method
Therefore there is a graph where the number of short cycles is X < n/2 and the
independence number α(G) < a. We can just delete one vertex from each short
cycle arbitrarily, and we obtain a graph G
′
on at least n/2 vertices which has no
cycles of length at most l, and α(G
′
) < a. The chromatic number of this graph is
:
χ(G
′
) ≥
|V(G
′
)|

α(G
′
)
≥
n/2
3n
1−λ
ln(n)
=
n
λ
6ln(n)
By taking n sufficiently large , we get χ(G
′
) > k.
17
CHAPTER 2
The integral distance problems
A planar point set S is called an integral set if all the distances between the ele-
ments of S are integers. There are several results and conjectures about integral
set .
2.1 The Erd
¨
os-Anning Problems
The first result about integral sets of points was published in 1945 . It is the fol-
lowing theorem of Anning and Erd
¨
os (see [3]). They proved that we can not find
infinite integral set P
1

, P
2
, in the plane . The first solution of Anning and Erd
¨
os
in [3] seem to be complicated .A few months later, Erd
¨
os gave a simpler proof
that we will consider in the following. Interestingly, this proof is rediscovered by
Tran Nhat Tan, a student in K12-math honor program.
Theorem 2.1 If H is an infinite integral set in the plane, then the points of H lie
on one line.
PROOF If A, B, C are three points not all on a line and k=max(AB, AC), then
there are at most 4(k + 1)
2
points P such that PA −PB and PB −PC are integral
. For |PA − PB| is at most AB and therefore assumes on of the values 0,1, ,k,
that is , P lies on one of k + 1 hyperbolas . Similarly, P lies on one of the k + 1
hyperbolas determined by B and C . These (distinct) hyperbolas intersect in at
most 4(k + 1)
2
points. That is a contradiction. This completes the proof.
We can not have an infinite integral point not all on one line. However, we
always can find an integral point set of n points for each given n.
Theorem 2.2 For any n we can find n points no three on a line in the plane such
that their distances are all integral.
18
2.2. Counting unit distances
PROOF Firstly, for all n we only prove that we can find a set of n points in the
plane such that all the distances between two points are rational. We consider

the circle of radius
1
2
, x
2
+ y
2
=
1
4
. Since all the primes p of form 4k + 1 can be
represented as p = a
2
+ b
2
for a, b be positive integers, we take p
1
.p
2
, be the
sequence of primes of the form 4k + 1 . Then we have :
p
2
i
= a
2
i
+ b
2
i

, a
i
̸= 0, b
i
̸= 0
Consider the point (x
i
, y
i
) (on the circle) whose distance from (−
1
2
, 0) is
b
i
p
i
. For
i = 1, 2, , we consider the sequence of points (−
1
2
, 0) , (
1
2
, 0), (x
i
, y
i
). We prove
that any two distances are rational . Suppose this has been proved for all i < j.

We then prove that the distance from (x
j
, y
j
) to (x
i
, y
i
) is rational .Consider the
4-concyclic points (−
1
2
, 0) , (
1
2
, 0), (x
i
, y
i
) and (x
j
, y
j
) . Since 5 distances are clearly
rational , using Ptolemy’s theorem (see Appendix ) the distance from (x
j
, y
j
) to
(x

i
, y
i
) is rational . Thus enlarging the radius of the circle we obtain n points
with integral distance distances.
Remark 1 This is Erd
¨
os proof that was published in [3].
2.2 Counting unit distances
Paul Erd
¨
os (1946) proposed the problem of estimating how many pairs of
points in a set of n points could be at unit distance from each other. In graph the-
oretic terms, how dense can a unit distance graph be? The hypercube graph (see
Appendix) provides a lower bound on the number of unit distances proportional
to n log n. By considering points in a square grid with carefully chosen spacing,
Erdos found an improved lower bound of the form n
1+c/ log log n
.
We denote the maximum number of times a given distance r can occur among
n points of a plane by the function g(n, r) .We have the following theorem :
Theorem 2.3
n
1+c/ log log n
< g(n, r) < n
3
2
PROOF We assume that there are x
i
points at distance r from P

i
, clearly g(n, r)
= max
1
2
∑
n
i=1
x
i
. We suppose that x
1
≥ x
2
≥ ≥ x
n
. Hence :
∑
j
i=1
(x
i
−2i + 2) ≤ n for j = 1, 2, , n (1)
Put [n
1
2
] = a ,n
1
2
− a =  , 0 ≤  < 1 . Then from (1) we have :

x
1
+ x
2
+ + x
a
≤ n + 2
(
a
2
)
= 2n −2n
1
2
+ 
2
−n
1
2
+  < 2n −2n
1
2
(2)
for n ≥ 4. Thus :
19
2.2. Counting unit distances
x
a
<
1

a
(2n −2n
1
2
) = 2n
1
2
(3)
From (2) and (3) we have :
∑
n
i=1
x
i
< 2n −2n
1
2
+ (n − a)2n
1
2
= 2n
3
2
g(n, r) < n
3
2
By considering the set of points (x, y) , 0 ≤ x, y ≤ a, we easily obtain :
g(n, r) > n
1+c/ log log n
In here, we use the well known theorems about the number of solutions of

u
2
+ v
2
= m (see [18]). This completes the proof.
Remark 2 This is Erd
¨
os’s proof that was published in [8].
Remark 3 In the above theorem , taking r = 1 , we have an upper bound on the
number of unit distances
Remark 4 Interestingly, we have the best known upper bound for this problem,
due to Joel Spencer, Endre Szemerdi, and William Trotter (1984), is proportional
to n
4
3
. To prove this theorem, we need to use ” the probabilistic method” .
Theorem 2.4 g(n, 1) < 5n
4
3
PROOF We need to prove the following lemma ,called ”the crossing lemma”
Lemma 2.5 Let G be a simple graph with m ≥ 4n where m and n are the number
of edges and vertices. Then
cr( G) ≥
1
64
m
3
n
2
In here cr(G) ,the crossing number of graph G, is the least number of crossings

in a plane embedding of G
Proof Consider a planar embedding
˜
G of G with cr(G) crossings. let S be
a random subset V obtained by choosing each vertex of G independently with
probability p :=
4n
m
, and set H := G[S] and
˜
H :=
˜
G[S]
Define random variables X, Y, Z on Ω, the probability space as follows : X is
the number of vertices, Y the number of edges, and Z the number of crossings
of
˜
H . The trivial bound noted above, when applied to H , yields the inequality
20