Four

Colour Theorem and other colourings I

By

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