Four Colour Theorem and other colourings I By

Four
Colour Theorem and other colourings I

 

 

By

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

 

Lai Sheung Mo

(14223392)

A thesis submitted in partial fulfilment of the requirements for the degree of

 

Bachelor of
Science (Honours)
in

Mathematical
Science

At

Hong Kong Baptist
University

 

ACKNOWLEDGEMENT

 

Part of the work presented in this thesis
was done in collaboration with my supervisor Dr. Sun Pak Kiu. I would like to
thank my supervisor Dr. Sun Pak Kiu for his kindly guidance throughout the
semester. Thank you for the helpful suggestions and ideas. All the works
presented in this thesis are carried out by myself under the supervision of Dr.
Sun Pak Kiu.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

_________________

Signature of Student

_______Lai Sheung Mo

Student Name

Department of Mathematics

Hong Kong Baptist University

Date: _______________

 

 

Contents

Abstract……………………………………………………………………………………………………………

Chapter 1 Introduction………………………………………………………………………………………………5

Chapter 2
Notation and
Definition……………………………………………………………………………..6

Chapter 3 Elementary
Results……………………………………………………………………………………8

3.1 Important
Results……………………………………………………………………………………………..8

3.2 Edge Chromatic
on Graphs……………………………………………………………………………..10

3.2.1 Complete
Graph ……………………………………………………………………………………….10

3.2.2 Bipartite
Graph…………………………………………………………………………………………11

3.2.3 Cycle Graph
……………………………………………………………………………………………..12

3.2.4 Tree Graph……………………………………………………………………………………………….13

Chapter 4
Important Theorems
……………………………………………………………………………….14

4.1 Theorems from
Tait ………………………………………………………………………………………..14

4.2 Vizing
Theorem………………………………………………………………………………………………15

Chapter 5
Application of Edge Coloring
…………………………………………………………………..17

References……………………………………………………………………………………………………………….21

 

 

 

 

 

 

 

 

 

 

 

Four
Colour Theorem and other colourings I

 

Lai Sheung Mo

(14223392)

Department of
Mathematics

ABSTRACT

This
project is about Four Colour Theorem and other colourings. Before discussing
the Theorem, we will first introduce the history of four colour theorem and
some important definition and theorem of graph theory, such as Kempe chain,
Duality, plane graph and some special graph. In Chapter 2, We will discuss
about the first prove of Four Colouring Theorem published by Kempe and why his
prove was failed. Also, we will introduce Heawood’s prove of Five Colouring
Theorem. In Chapter 3, we present the other approaches to four-colour problem.
We will also discuss about some theorem of edge-colouring. In the last chapter,
we will discuss the map-colouring problem on surfaces and the Heawood number of
the surface.

 

 

 

 

 

 

Chapter 1 Introduction

1.1  
The
History of Four Colour Theorem

 

Four-colour
Theorem is one of the most famous graph theory problem in the development of
graph theory. The most common application of this theory is map colouring. Four
colour Theorem states that in any given separation of a plane into contiguous
region, these regions can be coloured by 4 colours such that no adjacent
regions using the same colour.

 

Alfred
Kempe’s prove was published in 1879, but Percy Heawood Spotted the error of
Kempe’s proof when Heawood proving the five colour theorem in 1890. Although
Kempe’s proof was failed, he had provided a lot of important theorems and contribution
in graph theory. In particular, the general inductive argument, the use of
Euler’s formula, and Kempe-chain argument brought a lot of insight to the later
mathematicians.

 

After
Percy Heawood proved that five colours were sufficient to colour the map. The
problems remained open. Mathematicians began to determine whether four colours
were enough, or some maps required five colours. In 1922, Franklin found that
for any maps with at most 25 countries, four colour is enough. Heesch later
carried out two important concepts, ‘reducibility’ and ‘discharging’, which is
contributive to the later proof.

 

Nearly
100 years later, in 1976, Haken and Koch achieved the proof of Four Colour
Theorem, basing their methods on reducibility using Kempe chains. They used
1200 hours of computer time to finish the details of the final proof. In 1977,
their proof was first appeared in two articles.

 

Here
is an example of a 4-colouring map:

Chapter 2 Theorem and Definition

2.1 Basic graph theory

 

To
make our discussion simple, for all graph mentioned in this thesis, we denote
the graph  is the edge set and  is the vertices set.

 

2.1.1 Definition. (adjacent)

Two
vertices are adjacent if they are the endpoints of an edge.

Two
edges are adjacent if they have an endpoint in common.

 

2.1.2 Definition. (walk, trail, circuit,
path cycle)
A
walk
is a sequence  of vertices and edges that each is incident to
the next. A closed walk is a walk started and end at the same vertex, and open
otherwise.

A
trail
is a walk that all edges are not the same. A circuit is a closed trail
with at least one edge.

A
path
is a trail that all vertices are not the same. A cycle is a circuit that
all vertices are not the same.

 

2.1.3 Definition. (Connected)

Two
vertices are connected if there is a walk from one to the other.
Connectedness is an equivalence relation on the vertices of a graph.

 

2.1.4 Definition. (Degree of a
vertex)

The
degree
of a vertex is the number of edges that incident to it. And it denoted by

 

2.1.5 Definition. (isomorphic, plane,
planar)

Two
graph is isomorphic if there is a bijection between the vertices, and a
bijection between the edges, which preserves incidence.

A
plane
graph is a graph drawn in the plane with no intersection between two edges.

A
planar
graph is a graph that is isomorphic to a plane graph.

 

2.1.6. Definition. (embedding, map)

Embedding
means a drawing of a planar graph in which that the edges do not cross.

A
standard map is a map with properties that its underlying graph is a
connected plane graph with no bridges, no loops of parallel edges and no
vertices of degree less than 3.

We
assume all our maps are standard in the discussion.

 

2.1.7 Definition. (dual)

The
dual
 of a map  is a new map by draw a vertex in the interior
of rach region in  and join the region by edges. In other words,
the edge of  crossing each edge of .

 

2.1.8
Definition. (Euler circuits)

A Euler circuit is a circuit that use
each edge exactly once.

 

2.1.9
Theorem. If G
is connected graph and the degree of every vertex is even, then it have an Euler
circuit

 

2.2 Euler’s formula and its application

 

2.2.1 Lemma. If
a graph has at least one edge, and no vertex of degree 1, then it contains a
cycles.

 

Proof. Let the
edge . By
assume, no vertex of degree. Therefore we have  (there is a cycle) or there is a second edge .
Similarly,  does not have degree 1. So we have (there is
a cycle) or there is third edge . By
induction, since the graph is finite, we must end the process at a vertex.
Suppose we end at , then  for some . And  is a cycle.

 

2.2.2 Theorem. (Euler’s Theorem) If
G is a connected plane graph with  vertices,  edges, and  faces, then .

 

Proof. First, we
remove all the vertices with degree 1 and the edges incident to it. (It doesn’t
change , since
it doesn’t change the number of faces). Then there is no vertex of degree 1. By
Lemma 2.2.1, we could find a cycle in the graph. Therefore, we could find a
circuit in the graph and remove an edge in the circuit while keeping the graph
connected. (It doesn’t change, since
it doesn’t change the number of vertices and both the  and reduce by 1) Finally, we removed all the edges
and left 1 vertex and 1 face, and get the result .

 

 

 

 

 

 

2.2.3 Lemma. The
sum of the degrees of the vertices of a graph is equal to the twice of the
number of edges.

 

Proof. Every
edges have 2 endpoints and contribute 2 to the sum of the degrees of the
vertices.

 

2.2.4 Lemma. If
G is a plane graph, and  is the number of faces with  sides,  is the number of edges, then .

 

Proof. An edge
is counted twice if it occurs twice in the boundary walk of a face. We walk
along the boundary of all the faces and we walk along each edges twice.

 

2.2.5 Corollary.
Every plane connected graph G with all vertices of degree at least 3 has a face
with at most five sides.

 

Proof. We prove
this corollary by contradiction. Let G be a graph with vertices,  edges and  faces. Suppose all the vertices have degree at
least 3 and all the faces have at least six sides. By Lemma 2.2.4 and 2.2.3, we
have and.

 

Therefore,
by Euler’s formula,

                                               

Which
create a contradiction.

 

 

 

 

Chapter 3 Four colour Theorem

 

3.1 The first ‘proof’ of the four-colour
theorem by Kempe

 

3.1.1 Definition. (Kempe chain)

In
a map, given two colour  and  and a country k coloured by, the -Kempe
chain is the largest connected set of countries containing k such that all the
countries in the set are coloured either  or .

 

The
set S = {A,B,C,D,E} is an example of red-yellow Kempe chain containing A.

3.1.2
Lemma. In a 4-colourable map. If four countries meet at a
point, then these four countries only need to use three colours such that the
whole map can be 4-coloured.

 

Proof. Assume
that the colours of the four countries are red, blue, green, yellow in order
round the point. If the red and green countries belong to the same red-green
Kempe chain, then the chain separate the blue and yellow countries and they are
not belong to the same blue-yellow chain. Therefore, we could swap the colours
in one of these blue-yellow chains. If red and green countries do not belong to
the same red-green chain, then we can swap the colours of one of these red-blue
chains.

 

Fig.3.2  (a) red
and green countries belong to the same chains

(b) red and green countries do not
belong to the same chains.

3.1.3 Lemma. In
a 4-colourable map. If five countries meet at a point, then these five countries
only need to use three colours such that the whole map can be 4-coloured.

 

Actually,
Kempe made same mistakes in the proof. Let’s take a look at the proof and find
the error.

 

Proof. Suppose
we need four colour around the point (by
3.1.2). Then two countries with the same colour. Assume that the colours
are red, blue, green, yellow, blue in clockwise. If red and green countries do
not belong to the same red-blue chain, then we can swap the colours in one of
these two red-blue chains. Similarly, If red and yellow countries do not belong
to the same red-yellow chain, then we can swap the colours in one of these two
red-yellow chains. And therefore three colours is enough.

 

The
only case left is that a red-blue chain isolating the first blue country and a
red-yellow chain isolating the second blue country.

 

In
this case, we can swap the colours in the blue-yellow chain containing the
first blue country, and in the blue-green chain containing the second blue
country. The colours of these countries become red, yellow, green, yellow,
green, clockwise in order which achieve.

 

However,
fig 3.3 shows the counter example.

  

By
Kempe’s argument in 3.1.3, first
swaps the colours in the Green-Yellow chain containing the country 1. This
process will break the red-yellow chain and creating a green-blue chain from
country 2 to the country 3. If we perform the second colour change, we swap the
colour in this green-blue chain and make country 3 coloured with green which
could not achieved the result.

 

Simply
speaking, if two chains intersect each other, by changing the colour of one of
the chain, it will change the other change. So we could not achieve the result.

3.2 The five colour theorem

 

Although
Kempe’s proof was failed, Heawood salvaged the five-colour theorem from Kempe’s
work. Let’s see the proof of Heawood’s five colour theorem.

 

3.2.1 Theorem. Every
map is 6-colourable.

 

Proof. Obviously,
it is true for all map with less than 7 countries. Suppose the map has at least
7 countries. By Corollary 2.2.5 ,
there is a country with fewer than 6 neighbours. Removing this country by
sharing amongst its neighbor, the new map has one fewer country. By induction,
the map become 6-colourable. Finally, put the countries removed back to the
map. These countries has at most five neighbours and there is a colour
available for the country.

 

3.2.2
Lemma. In a 5-colourable
map,
If five countries meet at a point, then these five countries only need to use
five colours such that the whole map can be 4-coloured.

 

Proof.
Supporse the five colours that we need are
red, yellow, blue, green and orange. If red and blue countries are in the same
red-blue chain, then yellow and green countries is separated by this chain.
Therefore, we can swap the colour of the countries in the yellow-green chain
containing the yellow country. If red and blue countries are not in the same
red-blue chain, we swap the colours in one of these chains and achieved the
result.

 

3.2.3
Theorem. (Heawood, 1890) Every
plane map can be coloured with at most five coulours.

 

Proof.
By Corollary 2.2.5, we can find a country
with five or fewer edges and share it up equally amongst its neighbours. By
induction, we canobtain a map that is 5-colourable. Then we put the country
back. If it has four or less neighbours, then we can use the remaining colour.
If it has five neighbours, by Lemma 3.2.2. These countries only use 4 colours.
We can use the remaining colour for the country we put back.

 

 

 

 

 

 

3.3
Reduction theorem and vertex-colouring of graphs

 

If we want to prove the four-colour theorem,
we have to use reduction theorem which was proved by Cayley.

 

3.3.1
Definition. (cubic) A graph
or map is called cubic if every vertex has degree 3.

 

3.3.2
Theorem If the four-colour
theorem holds for cubic plane maps, then it holds for all plane maps.

 

Proof.
Given any maps, if there is a vertex with
more than 3 countries meet, we add a small countries to replace this vertex, so
that only 3 countries meet at some vertices. If the new map is 4-colourable,
the old map can do so. (We could delete the small countries with no violation
of the colouring.)

 

Kempe’s work in 1879 had mentioned the dual
version of the four-colour problem, where considering colouring the vertices of
the dual of a map.

 

3.3.3
Conjecture If G is
any planar graph, then G is 4-vertex-colourable.

 

We consider Kempe chain in a vertex version:
A maximal connected subgraph consisting of vertices of two colours. To finish
this, we prove the dual version of Lemma 3.1.2.

 

3.3.4
Lemma Let G be a
4-vertex-colourable plane graph, and let  be the
vertices of a face. Then G is 4-vertex-colourable in such a way that  use at
most 3 colours.

 

Proof.
Assume that 4 colours are used. Then the
graph cannot contain a Kempe chain from to  and a
Kempe chain from  to  at the
same time. These two chains must intersect at a vertex. It is impossible becase
the colour a and c are different from the colours of b and d. Therefore, either and  have
the same colour of  and have the same colour.

 

 

 

 

 

Chapter 4
Other approaches to the four-colour problem

 

5.1
Hamilton cycles

This section is about the Hamilton cycles and
4-colour problem. Tait proved that if a 
map has a Hamilton cycle, then the map is 4-colourable. First of all, we
take a look at the properties of Hamilton cycles.

 

5.1.1
Definition
(Hamilton cycle, Hamiltonian)

A Hamilton cycle is a cycle which
includes each vertex exactly once.

A Hamiltonian is a graph which has a
Hamilton cycle.

 

5.1.2
Theorem A Hamiltonian can be
4-coloured.

 

Proof.
Consider the Hamilton cycle of a map. It
separate the map into two parts. The dual of the interior of the Hamilton cycle
is a tree. It is because if it contain a cycle, it imply that a vertex in the
interior part of the Hamilton cycle is enclosed by the dual graph, which is
impossible. Consider the vertices of the tree, it is 2-colourable. Therefore,
the countries inside the Hamilton cycle can be coloured with two colours. So is
the exterior of the Hamilton cycle. Thus the map can be 4-coloured.

 

Later, Tait wondered whether all cubic graphs
have Hamilton cycles. However, he immediately reject this. A cubic graph with a
bridge cannot have Hamilton cycle since when you cross the bridge, you cannot
get back to where you started. Here is a counter example:

 

 

 

 

Instead of this counterexample, other counter
example with no bridge were given by Petersen in 1898. Until 1946, Tutte
provided a counterexample with 46 vertices and 25 countries. According to
Barnette, Okamura has shown that no counter example exist with fewer than 34
vertices.

     

Petersen graph

Tutte’s polyhedral counterexample

      

 

5.2
Edge-colourings

 

5.2.1
Definition (edge-k-colouring)

Edge-k-colouring of a graph is a colouring of the edges of
the graph with k colours such that no adjacent edges have the same colour.

 

5.2.2
Proposition Any
Hamiltonian cubic graph can be edge-3-coloured.

 

Proof.
If G with  vertices and edges is cubic, we have . Then p must be even. Then the Hamilton
cycle has an even number of edges and can be coloured by 2 colours. Then we
coloured the remaining edges with the third colour. We can do so because there are
just 1 more edges at each vertex (G is cubic).

 

5.2.3
Theorem (Tait) Let G be
a cubic graph. The G can be edge-3-coloured if and only if G is spanned by a
collection of disjoint cycles of even length.

 

Proof.
If G is edge-3-coloured, then the edges of any
two colours will form a collection of cycles of even length. If G is panned by
a collection of disjoint cycles of even length, then by 5.2.2, we could
colourthe edges of the cycles with two colours and the remaining edges with
third colour.

 

 

5.2.4
Theorem (Tait) Let G be
a bridgeless cubic plane graph. The face of G can be 4-coloured if and only if
the edges of G can be 3-coloured.

 

Proof.
Suppose we can 4-colouring the faces of G
with red, blue, green, yellow. Then we can separate the edges into 6 types,
according to which two colours are on the two sides of the edge. We denote the
edges between a red and a green face as red-green edge. A red-blue edge cannot
meet a green-yellow edge, since two adjacent edges must lay on one face in
common. Therefore we can colour the red-blue edges and green-yellow edges with
the same colour. Thus, we can use 3 colours for 6 types of edges.

 

Suppose the edges of G can be 3-coloured,
says red, blue and green. Then the edges of any two colours form a collection
of disjoint cycles and it include all the vertices. Noticed that any face is
inside some of these cycles. Suppose we give these cycles a number the number
is odd or even. We do the same for another pairs of colours (says we do this on
red and blue, blue and green). Now we can divided the face into four types. Two
adjacent faces meet either at red edges, at blue edges or at green edges. If
two faces meet at a green edge, then cross the green edge change the parity of
the number of blue-green cycles that a face contained in. If two faces meet at
a red edge, then change the parity of the number of red-blue cycles. If they
meet at a blue edge, then change the parities of both cycles. Therefore, we can
assign four colour to the faces.

 

The following dodecahedron may help to
understand the idea:

 

 

 

From Tait’s Theorem in 5.2.4, we could see
that the four-colour conjecture is equivalent to the conjecture that every
bridgeless cubic plane graph can be 3-edge-coloured. And by 5.2.3, it’s also
equivalent to every beidgeless cubic planar graph is spanned by a collection of
disjoint cycles of even length.

Chapter 4
Map on surfaces with holes

 

4.1
Euler’s formula in curved surfaces

In this chapter, we will discuss the map on
surface with holes. Map on a torus is one of the example. To draw a clear
picture, we will transform the map on a curved surface into a flat maps. The
following are the example:

The
arrows indicate the opposite edges are identical.

4.1.1 Definition (genus)

Genus is the number of ‘holes’ of a orientable
surface have.

 

4.1.2 Proposition If a connected graph G with  vertices,  edges
and  faces
is drawn on a torus and every face is connected, then .

 

Proof. First, we
remove all the vertices with degree 1 and the edges incident to it. (It doesn’t
change , since
it doesn’t change the number of faces and both p and q reduced by 1 ). Then
remove the edge incident with two different faces. (It doesn’t change , since
it doesn’t change the number of p and both q and r reduced by 1 ). The face
formed by the removal of edge is still connected and no holes in it.

 

After removing
the edges, there is only one face and all edges are on the boundary of this
faces. Suppose there are  edges in the vertical line and  edges on the horizontal line, there  and . So we
have

.

 

 

 

 

 

4.1.3
Corollary If G is
a graph embedded in a torus with p vertices, q edges and r face, then .

 

Proof.
First, we add sufficient edges on G to make
it connected which would not rise the value of . Since we only add sufficient edges, no
cycle created and r does not change. So the new value of  .So
the original value is also at least 0.

 

4.1.4
Proposition If a
connected graph G with p vertices, q edges and r face is drawn on a surface of
genus g in such a way that every face is a 2-cell, then

 

Proof.
Imagine boring a hole through the middles of
one face, says A and reappearing of another face, says B. We join  vertices of A to  vertices B by adding  edges
cross the hole. The result replace A and B by  faces
by adding  edges.
The number of vertices unchanged. Since A and B is replaced,  increase by  and  increase by  -2. So
 is
decrease by 2. By induction on the number of holes, we can show the result.

 

4.1.5
Corollary If G is
any graph with p vertices, q edges and r face embedded in a surface of genus g,
then

 

Proof.
The idea is similar to 4.1.3. First, we add sufficient edges on G to
make it connected which would not rise the value of . Since we only add sufficient edges, no
cycle created and r does not change. Now the new value  is  and  is the
genus of the graph. So the original value of  was at
least .

 

 is
called the Euler characteristic.

 

 

 

 

 

 

 

 

 

4.2 Map
colouring on a torus