Jacques Verstraete Department of Mathematics Ucsd La Jolla Ca Jacques@ucsd - Edu

Map Coloring Theorems
Jacques Verstraete
Department of Mathematics
UCSD La Jolla CA
[email protected]
Outline
1. Motivation
2. Duality
3. Coloring graphs
4. Coloring algorithm
5. Euler’s Formula
6. Art Galleries
Motivation
Definition.
A k-coloring of a map is an assignment of k colors, one

to each country, in such a way that no two countries
sharing a border have the same color.
A coloring of a map of Europe in thirteen colors

Motivation
Definition.
A map is k-colorable if it has a coloring with at most

k colors.
A coloring of a map of Europe in five colors

Motivation
De Morgan (1982)
A student of mine asked me today to give him a

reason for a fact which I did not know was a fact
- and do not yet. He says that if a figure be
anyhow divided and the compartments differently
coloured so that figures with any portion of
common boundary line are differently coloured -
four colours may be wanted, but not more - the
following is the case in which four colours are
wanted. Query cannot a necessity for five or
more be invented.
The 4-Color Conjecture (1852)
Is every map 4-colorable?

Duality
Definition.
The dual G* of a map G is obtained by replacing

each state with its capital and then putting an edge
between two capitals if the states share a border.
A simple example of duality

Duality
The dual of the USA

Duality
The dual of the USA

Duality
Coloring the dual of the USA

Coloring graphs
Definition.
A graph consists of vertices together with edges

joining pairs of vertices.
Coloring graphs
Definition.
A graph consists of vertices together with edges

joining pairs of vertices.
Coloring graphs
Definition.
A k-coloring of a graph is an assignment of k colors,

one to each vertex, in such a way that no two
adjacent vertices share the same color.
The chromatic number of a graph G is the minimum

k for which a k-coloring exists. It is written χ(G ).
Coloring graphs
Definition.
A k-coloring of a graph is an assignment of k colors,

one to each vertex, in such a way that no two
adjacent vertices share the same color.
The chromatic number of a graph G is the minimum

k for which a k-coloring exists. It is written χ(G ).
Coloring graphs
A 4-coloring of the USA

Coloring graphs
Observation 1.
If a graph G contains a graph H, then
χ(G ) ≥ χ(H )
Therefore the chromatic number of the USA is 4.

Coloring algorithm
Definition.
The degree of a vertex in a graph is the number of

edges out of that vertex.
The minimum degree of a graph is the minimum of all

the degrees of the vertices in the graph.
Coloring algorithm
"
Uvctv"ykvj"c"itcrj"I3"ykvj"p"xgtvkegu0"
"
" Hqt"k"?"3"vq"p"fq"
"
30 Hkpf"c"xgtvgz"xk"qh"uocnnguv"
fgitgg"kp"Ik0"
40 Tgrnceg"Ik"ykvj"Ik"⁄"xk0"
"
Eqnqt"xp"ykvj"eqnqt"30""
"
" Hqt"k"?"p/3"vq"3"fq"
"
Eqnqt"xk"ykvj"vjg"hktuv"cxckncdng"
eqnqt"pqv"wugf"qp"vjg"pgkijdqtu"
qh"xk"coqpiuv"xl"hqt"l"@"k0"
Coloring algorithm
1 2
6
3
5
4
Coloring algorithm
Pick a vertex of smallest degree, say 4.

Delete it
1 2
6
3
5
Coloring algorithm
Pick vertex of smallest degree, say 3.
Delete it.
1
2
6
5
Pick vertex of smallest degree, say 2.

Delete it.
Coloring algorithm
1
5 6
6
5
5
1
2 1 2
6 6
3
5 5
1 2
6
3
5
4
Euler’s Formula
Definition.
A planar graph is a graph which can be drawn in

the plane without any two edges crossing.
Euler’s Formula
Definition.
A face of a graph drawn without crossings is one of

the lakes that you get when you pour water on the
picture and treat the edges as walls.
Euler’s Formula
If G is a graph drawn without crossings in the plane,
let f (G ), n(G ), e(G ) be the number of faces, vertices
and edges in the graph.
Euler’s Formula (1752)

For any connected plane graph G
n(G )  f (G ) e(G )  2
Euler’s Formula
How to prove Euler’s Formula:
Basic idea
If you delete one edge from a cycle in the graph,

then the number of faces drops by 1.
So continuing deleting edges in cycles,
n(G )  f (G ) e(G )
never changes until there are no cycles left.
But if there are no cycles left, then the graph is a

tree. For a tree we have
e(G )  n(G )  1 f (G ) 1
and so the value of the formula is 2.

Euler’s Formula
Definition.
The degree of a face surrounded by a cycle is the

number of edges in that cycle.
Observation.
If d(F ) is the degree of face F in a graph G, then
 d(F )  2e(G)
F
This follows from the fact that if we add up the

number of edges on the boundary of each face, then
each edge of the graph is counted twice.
Euler’s Formula
Theorem (Plato, <360bc)
There is only one connected planar graph where
all faces are quadrilaterals and all vertices have
degree three.
How to prove Plato’s Theorem:
Euler’s Formula says
n(G )  e(G )  f (G )  2
Adding up degrees of faces says
4 f (G )  2e(G )
Adding up degrees of vertices says
3n(G )  2e(G )
Euler’s Formula
The only solution to the equations
n  e f  2
4 f  2e
3n  2e
is n  8, e 12, f  6 . We recognize the cube:

Art Galleries
An art gallery is a region in the plane bounded by a simple
polygon.
Art Galleries
A guard is a point and the visibility of a guard is the set of
points which can be joined to the guard by a straight line
that does not cross through a wall of the art gallery.
Art Galleries
For each art gallery, what is the smallest number of guards
required so that every point of the art gallery is visible to
at least one guard?
Art Gallery Theorem (Chvátal, 1975)

For any art gallery with n corners, n/3 guards
are enough to guard the whole gallery.
Art Galleries
How to prove the art gallery theorem
Triangulate the polygon

Art Galleries
Then we get a planar graph A with n vertices. A has a
vertex of degree two. Remove the vertex of degree two
from A. We get another triangulation of an art gallery.
Again find a vertex of degree two and remove it.
So we conclude that A is built up from a single vertex

by repeatedly adding a vertex of degree at most two.
By the coloring algorithm it is 3-colorable.
Pick color 1. Then every triangle has color 1 on it since

three colors are needed to color a triangle.
Then place guards at vertices of color 1 and they see the

whole art gallery.
Art Galleries
How to prove the art gallery theorem
(1) Can you draw an art gallery with
(a) 6 corners and cannot be guarded by 1
guard?
(b) 7 corners and cannot be guarded by 2
guards?
(c) 3n corners that cannot be guarded by
n – 1 guards?
(3)(a) Color the map below with four colors. Can it
be colored with three colors?
(b) Find the chromatic number of each continent
shown below.
(5) Is it possible to hang a picture on a wall using a
string and two nails in such a way that the picture
does not fall but if either nail is removed then the
picture falls down.

Jacques Verstraete Department of Mathematics Ucsd La Jolla Ca Jacques@ucsd - Edu

Uploaded by

Copyright:

Available Formats

Jacques Verstraete Department of Mathematics Ucsd La Jolla Ca Jacques@ucsd - Edu

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Jacques Verstraete Department of Mathematics Ucsd La Jolla Ca Jacques@ucsd - Edu

Uploaded by

Copyright:

Available Formats

Map Coloring Theorems

A k-coloring of a map is an assignment of k colors, one

A coloring of a map of Europe in thirteen colors

A map is k-colorable if it has a coloring with at most

A coloring of a map of Europe in five colors

A student of mine asked me today to give him a

The 4-Color Conjecture (1852)

Is every map 4-colorable?

The dual G* of a map G is obtained by replacing

A simple example of duality

The dual of the USA

The dual of the USA

Coloring the dual of the USA

A graph consists of vertices together with edges

A graph consists of vertices together with edges

A k-coloring of a graph is an assignment of k colors,

The chromatic number of a graph G is the minimum

A k-coloring of a graph is an assignment of k colors,

The chromatic number of a graph G is the minimum

A 4-coloring of the USA

If a graph G contains a graph H, then

Therefore the chromatic number of the USA is 4.

The degree of a vertex in a graph is the number of

The minimum degree of a graph is the minimum of all

Pick a vertex of smallest degree, say 4.

Pick vertex of smallest degree, say 2.

A planar graph is a graph which can be drawn in

A face of a graph drawn without crossings is one of

Euler’s Formula (1752)

If you delete one edge from a cycle in the graph,

So continuing deleting edges in cycles,

never changes until there are no cycles left.

But if there are no cycles left, then the graph is a

and so the value of the formula is 2.

The degree of a face surrounded by a cycle is the

If d(F ) is the degree of face F in a graph G, then

This follows from the fact that if we add up the

How to prove Plato’s Theorem:

Euler’s Formula says

Adding up degrees of faces says

Adding up degrees of vertices says

is n  8, e 12, f  6 . We recognize the cube:

Art Gallery Theorem (Chvátal, 1975)

Triangulate the polygon

So we conclude that A is built up from a single vertex

By the coloring algorithm it is 3-colorable.

Pick color 1. Then every triangle has color 1 on it since

Then place guards at vertices of color 1 and they see the

You might also like