Eulerian circuits. If a graph represents transportation
routes in a city or across a nation, for example, then
seeking Eulerian circuits for the graph can have impor-
tant practical use.
In 1857 W
ILLIAM
R
OWAN
H
AMILTON
explored the
issue of finding paths through graphs that do not nec-
essarily trace each edge, but instead visit each vertex in
the graph once, and only once. Today such a path is
called a Hamiltonian path, or a Hamiltonian circuit if
it is a path that returns to the starting vertex. Although
mathematicians have developed some theorems that
give conditions under which Hamiltonian paths will
exist, no one to this day knows a simple algorithm that
enables us to find them. Each graph must still be exam-
ined individually, and finding a Hamiltonian path—if
one exists—is usually a matter of inspired guessing.
Simple counting can lead to important results in
graph theory. For example, summing the degrees of all
the vertices in a graph counts the total numbers of ends
of edges. As every edge has two ends, we have:
In any graph, the sum of the degrees of all the
vertices equals twice the number of edges in
the graph.
In particular, the sum of all the degrees of vertices must
be an even number. Consequently, there cannot be an
odd number of odd numbers in this sum.
In any graph, the number of vertices of odd
degree is even.
This result has an amusing interpretation. Thinking
of edges in a graph as handshakes between people, we
have established the so-called
HANDSHAKE LEMMA
:
At any instant, the number of people on this
planet, living or deceased, who have partici-
pated in an odd number of handshakes is even.
A
POLYHEDRON
can be thought of as a graph drawn
on a
SPHERE
—each corner of the polyhedron is a ver-
tex, and each edge of the figure is an edge of the
graph. If a polyhedron consists of only ttriangular
faces, then 3tcounts the number of edges of the figure
twice (each triangle has three edges, and each edge
borders two triangles). Thus 3t = 2e, where eis the
number of edges. This shows that tmust be an even
number. We have:
It is impossible to cover a sphere with an odd
number of triangles.
Euler also went on to show that for any graph drawn
on a plane or a sphere (with no edges of the graph
intersecting):
v– e+ r= 2
where vis the number of vertices the graph possesses, e
its number of edges, and rthe number of regions
defined by the graph—including the large “outer”
region if the graph is drawn on a plane. This is called
E
ULER
’
S FORMULA
. If the graph is drawn instead on a
TORUS
, this formula is modified to read: v– e+ r= 0.
Graph theory is a discipline under intense contin-
ued study. Its many applications vary from the purely
theoretical to the very concrete and practical. Routing
problems, information-flow problems, and electronic
circuit design, for example, can all be effectively ana-
lyzed and refined through the study of this field.
See also E
ULERIAN PATH
/
CIRCUIT
; H
AMILTONIAN
PATH
/
CIRCUIT
;
THREE
-
UTILITIES PROBLEM
;
TOPOLOGY
;
TOURNAMENT
;
TRAVELING
-
SALESMAN PROBLEM
.
greatest common divisor (greatest common factor,
highest common factor) The largest
FACTOR
common
to a given set of integers is called the greatest common
divisor of those integers. For example, the numbers 72,
120, and 180 have factors 1, 2, 3, 4, 6, and 12 in com-
mon, with 12 being the greatest common divisor. We
write gcd(72, 120, 180) = 12.
One can find the greatest common divisor of two
or more integers simply by listing the factors of each
integer and identifying the largest factor they have in
common. Alternatively, if the prime decompositions of
the integers are known, then their greatest common
divisor can be determined as the product of the primes
they have in common. For example, noting that:
72 = 2 ×2 ×2 ×3×3
120 = 2 ×2 ×2 ×3×5
180 = 2 ×2 ×3 ×3×5
we see that these three numbers share, as prime factors,
two 2s and one 3. Their greatest common divisor is
thus gcd (72,120,180) = 2 ×2 ×3 = 12. (This second
236 greatest common divisor