On Equivalent Color Transform and Four Coloring Theorem
Wenhong Tiana
a

School of Information and Software Engineering,
University of Electronic Science and Technology of China (UESTC)

arXiv:1610.01865v1 [] 6 Oct 2016

Abstract
In this paper, we apply an equivalent color transform (ECT) for a minimal k-coloring of
any graph G. It contracts each color class of the graph to a single vertex and produces a
complete graph Kk for G by removing redundant edges between any two vertices. Based on
ECT, a simple proof for four color theorem for planar graph is then proposed.
Keywords: Four color theorem, Equivalent color transform (ECT)
1. Introduction
Four Coloring Theorem (FCT) states that every planar map is four colorable so that no
two adjacent regions have the same color, given any separation of a plane into contiguous
regions in the map. Proving four colors theorem is a very hard and challenging task since
the first statement of the four color theorem in 1852.
The four color theorem was proved in 1976 by Kenneth Appel and Wolfgang Haken [3] [4]
with computer assistance. It was the first major theorem to be proved using a computer.
To dispel remaining doubt about the Appel-Haken proof, a simpler proof using the same
ideas still with computer-assistance was published in 1996 by Robertson, Sanders, Seymour,
and Thomas [7] and the part which required hand verification was not as tedious as in AppelHaken proof. A quadratic algorithm to 4-color planar graph was proposed in [5] by Appel
and Haken. An efficient algorithm for four-coloring planar graph was also proposed in [6].
In this paper, we apply an equivalent color transform (ECT) for planar graph and propose
a simpler proof for four color theorem.
2. Methods
Definition 1. Equivalent Color Class (ECC). For coloring a simple graph, node i
and j can have the same color if they are non-adjacent, node i and j are called in equivalent
color class.
Definition 2. Equivalent Color Graph (ECG) is a composite graph, where composite nodes are formed by moving those non-adjacent nodes in original graph together and

Preprint submitted to Elsevier

October 7, 2016

edges are kept the same as in the original graph.
Definition 3. Equivalent Color Transform (ECT) is contracting each equivalent
color class in ECG to a single vertex and keep just one edge between any adjacent vertex.
There may be more than one way to form ECG for any given graph. Figure 1 shows an
example of 6-node simple graph (a) and its corresponding ECG (b) and ECT (c).

1,4

1

3

5
2

2,5

6

6

3

(b) Equivalent color graph G2:
a composite graph

4

(a) 6-node planar graph G1

1_
3_
2_

4_

(c) Equivalent color transform G3
:a complete simple graph K4

Figure 1: An instance of ECG and ECT

Definition 4. Planar Graph is a graph that can be embedded in the plane, i.e., it can
be drawn in such a way that no edges cross each other [1].
Lemma 1. There exists an efficient ECT for planar graph.
There are exact algorithms to determine if a graph is 4-colorable such as one suggested in
[2]; there are also efficient algorithms such as one suggested in [6] for efficiently four-coloring
a planar graph. Notice that the RSST(abbreviated by the first letter of four authors in
[6]) algorithm has computational complexity of O(n2 ), where n is the number of nodes in
the graph. We therefore can conduct ECT efficiently by using RSST algorithm or similar
algorithm.
Theorem 1. For a planar graph, there exist an ECT which does not change
the planarity of the graph.
Proof. Building ECG just moves the place of original nodes and does not alter any node
or edge or their connection relationship, so we can apply RSST algorithm to find an ECT,
2

which do not change the planarity of the original graph.
Notice that there may be more than one ECG and ECT for any given planar graph; we
can apply RSST algorithm and similar algorithm to find an ECG and ECT, which do not
change the planarity of the graph. To do this, we may need running RSST algorithm a few
times until the ECG and ECT are found to keep the planarity of the original graph.
Theorem 2. A k-coloring graph which needs the minimum number of k colors,
can be converted to a complete simple graph Kk by ECT.
Proof. We prove by contradiction. Let us assume the original k-coloring graph G1 is converted to a simple graph G2 with k nodes by ECT and G2 is not complete graph. Since G2
is not complete graph, there must exist at least two nodes ni and nj which are not adjacent.
According to the definition of ECC and ECG, ni and nj can be contracted to a single vertex
(by equivalent color class and ECT) and a new graph with (k-1) nodes is formed. Therefore
there only need (k-1) colors for G1 and G2 , this contradicts the fact that G1 is k-coloring
and needs the minimum k colors.
Lemma 1. Wagner’s Theorem. A finite graph is planar if and only if it does
not have K5 or K3,3 as a minor [1].
Theorem 3. Planar graph is four colorable.
Proof. We prove by contradiction. Set k as the minimum number of colors needed for coloring
planar graph G. Let assume the planar graph G needs more than four colors, i.e., k > 4.
From Theorem 2, we know that G can be converted to a complete graph Kk (k >4) in this
case. This means G is transformed by ECT to a complete graph Kk (k >4) which is not
planar because any complete graph with more than 4 nodes will have K5 as a minor and is
not planar (by Lemma 1). But this contradicts the fact that G is planar and there exits an
ECT which does not change the planarity of the original graph (by Theorem 1). So k ≤ 4
and planar graph is four colorable.

Acknowledgments
This research is sponsored by the National Natural Science Foundation of China (NSFC)
(Grand Number: 61672136). The manuscript is also posted online at https://arxiv.org/
References
[1] https://en.wikipedia.org/wiki/Planar graph

3

[2] Fomin, F.V.; Gaspers, S.; Saurabh, S. (2007), Improved Exact Algorithms for Counting 3- and 4-Colorings, Proc. 13th Annual International Conference, COCOON 2007,
Lecture Notes in Computer Science, 4598, Springer, pp. 65-74.
[3] K. Appel and W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois
J. Math. 21 (1977), 429-490.
[4] K. Appel, W. Haken and J. Koch, Every planar map is four colorable. Part II. Reducibility, Illinois J. Math. 21 (1977), 491-567.
[5] K. Appel and W. Haken, Every planar map is four colorable. Contemp. Math. 98,1989.
[6] N. Robertson, D. P. Sanders, Efficiently four-coloring planar graphs, STOC ’1996 Proceedings of the twenty-eighth annual ACM symposium on Theory of computing,Pages
571-575.
[7] N. Robertson, D. P. Sanders,P. D. Seymour and R. Thomas, A new proof of the four
colour theorem, Electron. Res. Announc. AMS 2 (1996), 17-25.

4

