# Triangulations of the sphere, hamiltonian circuits, colorings

Mohamed Boubekeur, Alain Grigis

► To cite this version:

Mohamed Boubekeur, Alain Grigis. Triangulations of the sphere, hamiltonian circuits, colorings. 2025. hal-05146350

HAL Id: hal-05146350

https://hal.science/hal-05146350v1

Preprint submitted on 5 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Triangulations of the sphere, hamiltonian circuits, colorings

Mohamed BOUBEKEUR and Alain GRIGIS

Université Paris XIII (Sorbonne Paris-Nord),

CNRS - UMR 7539,

99 avenue Jean-Baptiste Clément, 93430 Villetaneuse, France

grigis@math.univ-paris13.fr, boubekeur@math.univ-paris13.fr

June 2025

## Abstract

In this paper we study the 4-connected triangulations of the sphere and their number co of coloring with 4 colors up to permutation of the colors, and also the number ch of their hamiltonian circuits. The four colors theorem is equivalent to say that co does not vanish for any 4-connected triangulation of the sphere. A theorem of H. Whitney in 1931 shows that every 4-connected triangulation of the sphere admits at least one hamiltonian circuit. If G is obtained by gluing the triangulations G1 and G2 along a triangle then co(G) = co(G1)co(G2). Since to be 4-connected means to be indecomposable for a triangulation, we get the conclusion.

We have calculated the number of colorations of all the 4-connected triangulations with n vertices, which set is $c_4(n)$ for $n \le 24$ and we support the following conjecture :

Every non zero integer is the number of colorations of a finite set of 4-connected triangulations of the sphere.

We have shown that the maximum of co for $c_4(n)$ and even for the set of triangulations of the sphere with n vertices is obtained for the n-suspension. We also have calculated the number ch of hamiltonian circuits of the elements of $c_4(n)$ for $n < 17$ and we support the conjecture :

For $n > 5$ the n-suspension is the triangulation of $c_4(n)$ which realizes also the minimum of ch.

We also show that every triangulation of the sphere having a hamiltonian circuit in particular the elements of $c_4(n)$ can be represented by an ordered list of $2n - 2$ positive integers. We deduce an algorithm to build all the graphs. However as it is difficult to sort the isomorphic graphs, we have used the code plantri of Brinkmann, Van den Camp and McKay to get the list of $c_4(n)$ for $n > 16$.

We study also the numbers co and ch for some series of triangulations of the sphere.
Résumé

Dans cet article nous faisons une étude du nombre co de colorations avec 4 couleurs à permutation près des couleurs des triangulations de la sphère 4-connectées et aussi de leur nombre ch de circuits hamiltoniens. Le théorème des 4 couleurs équivaut à dire que co est non nul pour toute triangulation de la sphère. Un théorème de H. Whitney de 1931 [W] montre que toute triangulation indécomposable admet au moins un circuit hamiltonien. Si G est le collage des triangulations G1 et G2 le long d'un triangle on a co(G) = co(G1)co(G2). De plus comme être indécomposable est équivalent à être 4-connectée pour une triangulation de la sphere, il suffit comme l'avait déduit H. Whitney de montrer que co est non nul pour toutes les triangulations 4-connectées pour obtenir le théorème des 4 couleurs.

Nous avons calculé les nombres de colorations de l'ensemble $c4(n)$ des triangulations 4-connectées à n sommets pour $n \le 24$ et nous étayons la conjecture suivante : Tout entier non nul est le nombre de colorations d'un ensemble fini de triangulations 4-connectées.

Nous avons montré que le maximum de co pour $c4(n)$ et même pour l'ensemble des triangulations à n sommets est obtenu pour la n-suspension. Nous avons aussi calculé le nombre ch de circuits hamiltoniens des éléments de $c4(n)$ pour $n < 17$ et nous étayons la conjecture : Pour $n > 5$ la n-suspension est la triangulation 4-connectée qui réalise aussi le minimum de ch sur l'ensemble $c4(n)$.

Nous montrons aussi que toute triangulation de la sphère possédant un circuit hamiltonien et en particulier tout élément de $c4(n)$ peut être représenté par une liste de 2n-2 entiers positifs. Nous en déduisons un algorithme qui permet de construire tous ces graphes. Par contre, comme il est difficile de trier tous les graphes isomorphes nous utilisons le code plantri de Brinkmann, Van den Camp et McKay, [B,VdC,McK]) pour obtenir la liste des graphes 4-connectés pour $n > 16$.

Nous étudions aussi les nombres co et ch pour quelques séries de triangulations de la sphère.

# 1 Introduction

To color a graph is to give a color to each of its vertices in such a way that two vertices joined by an edge get different colors. In 1976 Appel et Haken ([A-H1], [A-H2], [A-H3]) have proven the four colors theorem : every planar graph can be colored with four colors. The proof was technical and used computer assistance. Later, more simple proof, still using computers were given ([RSST]). More recently, people were working on proving that the proof is complete ([G]).

It is well known that the problem can be reduced to color the graphs which are triangulations of the sphere. Indeed we can add edges to a planar graph and get a triangulation of the sphere. Every coloring of the triangulation is a coloring of the graph.

In this article we will consider triangulations of the sphere and the number of ways to color them with four colors up to permutation of the colors.
We show the already known fact for a triangulation of the sphere that to be 4-colorable is equivalent to some property of the kernel of a matrix associated to the graph, the incident matrix of vertices-faces. This idea was introduced by Heawood [H] in the 19-th century, and a 4-coloring of the graph is related to a Heawood vertex character. In fact it is clear if we observe that a triangulation of the sphere is 4-colorable if and only if it can be folded over a tetrahedron. We study these foldings in section 7.

In section 4 we study the rank of the incident matrix and we give a good majoration of the number of colorings of a triangulation of the sphere with $n$ vertices. We show in theorem 8.5 that the $n$-suspension has the greatest number of these colorations.

In 1931 H. Whitney [W] has shown that every 4-connected triangulation has at least one hamiltonian circuit and that it is sufficient to prove that these triangulations can be 4-colored. We remark that the numbers of colorations of these triangulations form a multiplicative set. Then it is natural to study this set. The conjecture is that this set is $N*$. Moreover we conjecture that the tetrahedron is the unique 4-connected triangulation with $co = 1$. We conjecture also that 2 and 3 are with 1 the unique positive integers such that there is only one 4-connected triangulation with this co.

We have also found a way to build the set $c4(n)$ of all the 4-connected triangulations with $n$ vertices and to identify each triangulation with an ordered set of $2n$ integers, ($2n-2$ is even sufficient). This is in section 10. We use this way for $n \le 16$ but for larger $n$ we use the code plantri of Brinkmann, Van den Camp and McKay ([B,VdC,McK]) which is more efficient.

In section 8 and 9, following H. Whitney we consider first what we call the pies. A pie is the interior of a convex polygon which is triangulated by diagonals. An hamiltonian triangulation of the sphere is the union of two pies with the same boundary. We give the number of colorings of a pie and we deduce an equivalent of the four colors theorem : "Any pair of pies with $n > 3$ vertices have a commun 4-coloring", even if the gluing of these pies is not a triangulation of the sphere (if two vertices are joined by more than one edge) or if the obtained triangulation is not 4-connected.

In section 11 and 13 we give the results of our computations and we propose some conjectures about the number of coloring co and the number of hamiltonian circuits ch of the 4-connected triangulations.

In section 12 we built some series of triangulations for which we can compute co and ch.

In the conclusion we give the picture of the 4-connected triangulations with $co=2$ and $co=3$. We have joined also one of their decompositions in two pies for illustrating the section 10 where we see how to generate the pies.

# 2 About planar graphs

Then we will consider triangulations of the sphere, that means polyhedron which faces are triangles and which have the topology of the two-dimensional sphere.

More precisely we have an integer $n$ with $n \ge 4$ and three finite sets :

- $S$ is the set of vertices $\{s_1, s_2, ..., s_n\}$, it contains $n$ elements.
corresponding object is a polyhedron. Each (2, 2) block $(c_{ij}, c_{il}, c_{kj}, c_{kl})$ with all equal to 1 corresponds to an edge. This edge contains the vertices $s_i$ and $s_k$ and belongs to the faces $f_j$ and $f_l$. To be sure that we get a polyhedron the edges must be organized in cycles, a cycle around each face and a star around each vertex.

We will give later some statements about the rank of the incident matrix.

## 3 Coloring

Let $G$ be a triangulation of the sphere, $n(G)$ the number of its vertices and $co(G)$ the number of its colorings with four or three colors, up to permutations of the colors. Then if $\chi(G, k)$ is the chromatic polynomial of the graph $G$ and for $n = 1, 2, 3, 4$ $c_n(G)$ is the number of coloring $G$ with $n$ of the four colors up to permutation of these four colors, we have :

$$ \chi(G, 4) = \sum_{n=1}^{4} n! \binom{4}{n} c_n(G) $$

and $c_2(G) = 0, c_1(G) = 0$, since $G$ is a triangulation. Then we have :

$$ \mathrm{co}(G) = c_4(G) + c_3(G) = \frac{\chi(G, 4)}{24}. $$

As a set of three elements we will use the field $F_3 = \mathbb{Z}/3\mathbb{Z}$. Its elements are $\{-1, 0, 1\}$. As a set of four elements we will use the vertices $\{a, b, c, d\}$ of the tetrahedron $abcd$. We will use also the three pairs of opposite edges of the tetrahedron as a set of three elements, and denote it $DT$.

We call a 4-coloring of the triangulation $(F, A, S)$ a function $\phi$ on $S$ with values on $\{a, b, c, d\}$, taking different values at $s$ and $s'$ if they are joined by an edge. If $\sigma$ is a permutation of $\{a, b, c, d\}$, we say that the 4-colorings $\phi$ and $\sigma\phi$ are equivalent. The four color theorem tells us that such a function exists. The problem of coloring the graph $(S, A)$ with four colors is equivalent to color the graph of edges with three colors. This result is due to Tait (see [[RSST]]). A 3-coloring of the edges is a function $g$ on $A$ with values on a set with three elements, say $F_3$ or $DT$ such that for each face $f \in F$ the values on the three edges of $f$ are different. If $\tau$ is a permutation of the set with three elements, we say that $g$ and $\tau g$ are equivalent. To each 3-coloring of the edges corresponds up to equivalence exactly one 4-coloring of the vertices of the triangulation $(F, A, S)$. To be complete let us prove it. We can recall that a 4-coloring of the triangulation defines a continuous mapping of the triangulation of the sphere $(F, A, S)$ on the tetrahedron $abcd$. It defines also an application of the edges on the three pairs of opposite edges of the tetrahedron. This shows that a 4-coloring of the triangulation produces a 3-coloring of the edges. Conversely if we have a 3-coloring of the edges, it is easy to color the vertices with four colors. One gives one color, say $a$ to some vertex and since the triangulation is connected and simply connected, this defines a unique mapping from the edges of the triangulation to the edges of the tetrahedron, and we get a coloring of the other vertices.
It can happen that the triangulation admit a 3-coloring, that means a 4-coloring which avoids one of the values {$a, b, c, d$}. This is possible if and only if all the vertices have even degree. Then the dual graph (F, A) is bipartite and admits a 2-coloring. If $\sigma$ is a permutation of {$a, b, c, d$}, we say that the 3-colorings $\phi$ and $\sigma\phi$ are equivalent. Then we see that up to equivalence there is at most one 3-coloring of the triangulation. We will count it among the 4-coloring.

Before we state our result we remark that a 3-coloring of the edges is an element in the kernel $\mathcal{B}$ if we consider $\mathcal{B}$ as a linear application from $F_3^{3n-6}$ to $F_3^{2n-4}$. Indeed the sum of three elements in $F_3$ vanishes if they all equals or all different. Then the elements of the kernel of $\mathcal{B}$ are the functions on the edges which take on the three edges of any face either the same value or three different values.

Let us state now our result. We consider the linear map $\mathcal{C} : F_3^{2n-4} \to F_3^n$ with matrix $\mathcal{C}$. It is a linear map from the spaces of function on the faces with values in $F_3$ to the space of functions on the vertices with values in $F_3$.

**Definition 3.2** Let $P$ be the projective space associated with the kernel of $\mathcal{C}$. We call good function an $\tilde{x} \in P$ having all non vanishing components.

In other terms, if $x$ is a function on $F$ with values in $\{-1, 1\}$ such that at each vertex $s$ the sum on the values on the faces whose $s$ is incident is 0 modulo 3, the function $-x$ has the same property and $\tilde{x} = x/\{\pm 1\}$ is a good function.

**Theorem 3.1** Up to equivalence, a 4-coloring of the triangulation (F, A, S) corresponds to exactly one good function. Then $\text{co}(G)$ is the number of good functions.

Let us prove the theorem. Suppose that we have a 4-coloring of the triangulation (F, A, S). As we have seen it corresponds to a function $g$ from A to $F_3$ which is in the kernel of $\mathcal{B}$ and has the following property. For each face $f$, the function $g$ takes at the three edges belonging to $f$ the values $\{-1, 0, 1\}$.

Our sphere is oriented. We will define a linear application $\mathcal{D}$ from the kernel of $\mathcal{B}$ to the space of functions on $F$ with values in $F_3$. If $g$ is in the kernel of $\mathcal{B}$ and $f$ in $F$ we choose two successive edges $a_j$ and $a_{j+1}$ belonging to this face and we define $\mathcal{D}g(f) = g(a_{j+1}) - g(a_j)$. This definition is independent on the choice of the successive edges, and the application $\mathcal{D}$ is linear. The function $\mathcal{D}g$ is in the kernel of $\mathcal{C}$. Indeed consider a vertex $s$ and the edges containing it, in positive order $\{a_0, a_1, ..., a_d = a_0\}$.

Two successive edges ($a_j, a_{j+1}$) belongs to a face $f_j$, and around this face they are in negative order. Then we get that the sum of the $\mathcal{D}g(f_j)$ is the sum of the $g(a_j) - g(a_{j+1})$ and therefore is 0. If $g$ is a 3-coloring of the edges, the values of $\mathcal{D}g$ are $\{+1, -1\}$, and $\mathcal{D}g$ is a good function. Then to a 4-coloring of the triangulation we have associated a good function.

Conversely consider $x \in \ker(\mathcal{C})$ associated to a good function $\tilde{x}$. Then each face $f$ of the triangulation has an orientation $x(f) = +1$ or $x(f) = -1$. At each vertex $s$ the sum of the $x(f_j)$ for the faces containing $s$ is 0. We have to build a function $g$ on the edges. Let us choose an edge and let us give to some value, say 0. Then we have to respect the following rules. Consider a face $f$ whose orientation is +1 or -1, then the
values of $g$ on the edges will be $\{-1, 0, +1\}$ in the order respecting the orientation.
The function is determined as soon as we have given a value to one edge of the face.
At every vertex $s$ we consider the star centered at it and the edges containing $s$, in
positive cyclic order $\{a_0, a_1, ..., a_d = a_0\}$. The difference in $F_3$, $g(a_j + 1) - g(a_j)$ is equal
to $+1$ if the face $f_j$ containing $a_j$ and $a_{j+1}$ has orientation $x(f_j) = -1$ and equal to $-1$
if $x(f_j) = +1$. Then as soon as $g$ is defined on an edge of the star it is determined at
all the edges of the star. If we consider a loop of the edge-graph it can be decomposed
in a finite sum of elementary loops, because the sphere is simply connected. Then the
function $g$ is defined everywhere, because the triangulation of the sphere is connected,
and the value at each $f$ does not depend on the path used to reach it. If we choose
$-x$ instead of $x$ we change the orientation of the sphere and we get a 3-coloring of
the edges and a 4-coloring of the vertices equivalent to the previous ones. Then we
have shown that there is up to equivalence a unique 3-coloring of the edges, and then
a unique 4-coloring of the triangulation, associated to a good function.

The theorem is proven. More precisely we have proven that $\mathcal{D}$ is a linear application
from $\ker \mathcal{B}$ to $\ker \mathcal{C}$, which is onto and has a 1-dimensional kernel, which is the set of
constant functions. Moreover the image by $\mathcal{D}$ of the set of 3-coloring functions on the
edges is exactly the set of good functions on the faces.

# 4 The rank of the incident matrix

In this section we consider the incident matrix $\mathcal{C}$ of a triangulation $(F, A, S)$ of the
sphere. The entries of $\mathcal{C}$ are 0 or 1. Then we can consider the linear map $\mathcal{C} : K^{2n-4} \to
K^n$, for any field $K$. We will consider here the case of $F_3$ which we need and the case
of $\mathbb{R}$. We denote by $r(\mathcal{C}, K)$ the rank in the case of the field $K$.

**Definition 4.3** We call a star centered at a vertex $s$ the union of the faces containing the vertex $s$.

**Definition 4.4** We say that the triangulation $(F, A, S)$ is a partition in stars if the set $F$ has a partition in stars. $S$ has a partition $S' \cup S''$ and the stars centered at the $s \in S'$ form a partition of $F$. The vertices in $S'$ are called the centers and those of $S''$ the borders. Every face of the triangulation has a vertex in $S'$ and two vertices in $S''$. The vertices which are borders have an even degree. The vertices of odd degrees are in $S'$, they are isolated.

We have the following result :

**Theorem 4.2** Let us consider the incident matrix of a triangulation of the sphere with $n$ vertices. There are three possibilities :

- case 1: $r(\mathcal{C}, \mathbb{R}) = n$ and $r(\mathcal{C}, F_3) = n - 1$. The triangulation is not a partition of stars

- case 2: $r(\mathcal{C}, \mathbb{R}) = n - 1$ and $r(\mathcal{C}, F_3) = n - 1$. The triangulation is a partition of stars and at least a vertex is of odd degree.
- case 3: $r(C, \mathbb{R}) = n-2$ and $r(C, F_3) = n-2$. The triangulation is a partition of stars and all the vertices are of even order. The dual graph of the triangulation is a bipartite graph and the graph has a 3-coloring. This 3-coloring is unique.

We remark that $r(C, \mathbb{R}) \ge r(C, F_3)$ because if some determinant extracted from the matrix vanishes in $\mathbb{R}$ it vanishes in $F_3$. We also remark that the sum of the rows vanishes in $F_3$ then $r(C, F_3) < n$.

If the sum of three numbers in $F_3$ vanishes, then they must be all the same or all different. Then consider a linear combination of the lines of $C$ which is equal to 0 in $F_3$, in other words consider an element in the kernel of $C^t$. It corresponds to a function $h: S \to F_3$ for which the sum of the values on the three vertices belonging to any face vanishes. Then for each face $f$ in $F$ the three vertices have equal values or different values. Since the dual graph of our triangulation is connected, it follows that all the faces have the same property and we conclude that the function $h$ is constant or that it takes different values at the ends of any edge. We get that the kernel of $C^t$ in $F_3$ has dimension one or two, and $r(C, F_3)$ is $n-1$ or $n-2$.

Consider now a function $h$ on $S$ which is in the kernel of $C^t$ in $\mathbb{R}$. If we fix the values of $h$ at two vertices of one edge, then the function $h$, if it exists, is determined. Therefore we see that $r(C, \mathbb{R})$ is $n, n-1$ or $n-2$.

If $r(C, F_3) = n-2$, there exists a function $h: S \to F_3$ which takes different values at the three vertices of any face. One can define a function $k$ on the faces with values in $\{+1, -1\}$ in the following manner. If the values of $h$ on the vertices of $f$ are in positive cyclic order we define $k(f) = +1$, and if they are in the negative cyclic order we defines $k(f) = -1$. We get a function $k$ which takes different values on two faces which have a common edge. Then $k$ is a good function, all the vertices of the triangulation have an even degree, and the triangulation has a 3-coloring. We have also $r(C, \mathbb{R}) = n-2$. If the vertices are colored by $\{a, b, c\}$, that means that there exists a function $h$ on $S$ with values in $\{a, b, c\}$, with different values at the three vertices of any face. If we put respectively $\{a, b, c\} = \{-2, 1, 1\}$ or $\{a, b, c\} = \{0, 1, -1\}$ we get two linearly independent elements of the kernel of $C^t$. Then we have proven that the case 3 occurs when the triangulation has a 3-coloring, and this is equivalent to say that all the vertices have an even degree. The 3-coloring is unique up to permutation of the colors, because the choice of the colors of the vertices of one triangle determines the coloring of all the vertices of the triangulation. Let us remark also that a triangulation which has a 3-coloring is a partition of stars, it is sufficient to take $S' = h^{-1}(a)$.

Consider now a triangulation which is a partition of stars. If we define $h(s') = -2$ if $s'$ is a center and $h(s'') = 1$ if $s''$ is a border, we get that $h$ is in the kernel of $C^t$ in $\mathbb{R}$. Then $r(C, \mathbb{R})$ is $n-1$ and we are in case 2, or $n-2$ and we are in the case 3.

Consider now the situation when we are in case 2. Then $r(C, F_3) = n-1$ that means that the kernel of $C^t$ in $F_3$ is reduced to the constant functions. Consider a function $h$ in the kernel of $C^t$ in $\mathbb{R}$. Consider a star with center $s$ and consider the cycle of the frontier of this star. On the cycle the function $h$ must be 2-periodic. Then if the degree of $s$ is odd the function $h$ is constant on the cycle, and up to some factor we have $h(s) = -2$ and $h=1$ on all the vertices of the cycle. If the degree of $s$ is even, the set of solutions on the star is 2-dimensional on $\mathbb{R}$. As a basis we can take
$h_1$ the solution above and define $h_2 = 1$ at the center and at one over two vertices on the cycle and $h_2 = -2$ at the others. We have the same conclusions for any star. We have already remarked that our function $h$ is determined by its values at two vertices belonging to some edge. Then we get that if there exists a vertex with an odd degree the function $h$ takes, up to a factor, the values $\{-2, 1\}$ and for each face its takes the value $\{-2, 1, 1\}$ at the vertices of this face. Now if we defines $S' = h^{-1}(-2)$ we see that the triangulation is a partition of stars. Then in case 2 the triangulation is a partition of stars, and there exists at least a vertex having an odd degree.

The proof of the theorem is complete.

# 5 The number of colorings

If $G$ is a triangulation of the sphere, let $n(G)$ be the number of its vertices, and $co(G)$ the number of its colorings with 4 or 3 colors. Using the precedent results we get

**Corollary 5.1** If $G$ is in case 1 or in case 2 we have :

$$ \mathrm{co}(G) \leq 2^{(n-4)}. $$

If $G$ is in case 3 then :

$$ \mathrm{co}(G) \leq 2^{(n-3)}. $$

Indeed in case 1 or in case 2 the kernel of $\mathcal{C}$ is of dimension $2n - 4 - (n - 1)$ and the number must be divided by 2 when we pass to the projective space. In case 3 the kernel of $\mathcal{C}$ is of dimension $2n - 4 - (n - 2)$ and we also pass to the projective space.

We begin by giving a few examples.

For the **tetrahedron** which is in the case 1 we have $co = 2^{n-4} = 1$.

For the **icosahedron** which is also in case 1 we have $co = 10$. It is easy to describe the good solutions of the matrix $\mathcal{C}$. We choose four faces corresponding to one of the ten tetrahedron inscribed in the dual dodecahedron. The function on the faces of the icosahedron which is equal to -1 on these four faces and 1 on the other faces is a good function.

The **octahedron** is in the case 3 and we have $co = 4$. One of the coloring is with 3 colors. The octahedron is one of the suspensions, that we describe now.

**Definition 5.5** The n-suspension for $n \geq 5$ is the graph with $n$ vertices, union of two stars of n-2 faces having the same boundary. The centers of the stars have degree $n - 2$ and the vertices of the boundary have degree 4.

The **octahedron** is the **6-suspension**.

The **5-suspension** is in case 2, since the centers of the stars are of odd degree. The number of its colorings is 1.

**Proposition 5.1** The number of colorings of the n-suspension is

$$ \mathrm{mco}(n) = \frac{2^{n-3}}{3} + (-1)^n \frac{5}{6} + \frac{1}{2} $$

which is $\frac{2^{n-3}-1}{3}$ if $n$ is odd and $\frac{2^{n-3}+4}{3}$ if $n$ is even.
We deduce immediately the following majoration of the number of colorings of the triangulations of the sphere. Moreover in Theorem 8.5 we will prove that mco(n) is the maximum of the number of 4-colorings of the triangulations of the sphere having n vertices.

**Theorem 5.3** For any triangulation of the sphere G, we have the equality :

$$ \sup_G \frac{\log \mathrm{co}(G)}{\mathrm{n}(G)} = \log 2. $$

This maximum is obtained for $n = 4$ (the tetrahedron) and also as limit when $n \to \infty$ for the n-suspension.

Let us remark that for the set of connected simple graphs, we get $\log 3$ instead of $\log 2$, and for the set of simple graphs we get $\log 4$. Consider respectively the case of a tree with n vertices and the cases of a graph with n vertices and no edge.

We now give an elementary proof of the proposition. Later we will give another proof. Let $p = n - 2$. Consider one of the star of the n-suspension. We have to built a function on the p faces with values in $\{1, -1\}$ and the sum vanishing in $F_3$. Let $d(p)$ be the number of these functions. We have

$$ d(p) = A(p) = \binom{p}{0} + \binom{p}{3} + \dots \text{ if } p = 0 \mod 3, $$

$$ d(p) = B(p) = \binom{p}{1} + \binom{p}{4} + \dots \text{ if } p = 2 \mod 3, $$

$$ d(p) = C(p) = \binom{p}{2} + \binom{p}{5} + \dots \text{ if } p = 1 \mod 3. $$

It is easy to get: $3A(p) = 2^p + (-1)^{p2} \cos(p \frac{2\pi}{3})$, $3B(p) = 2^p + (-1)^{p2} \cos((p + 1) \frac{2\pi}{3})$, $3C(p) = 2^p + (-1)^{p2} \cos((p + 2) \frac{2\pi}{3})$,

If n is odd $\frac{1}{2}d(p)$ is the number of 3-colorings of the boundary of the star, and the centers of the two stars of the suspension must get the fourth color, then $\mathrm{co}(p) = \frac{1}{2}d(p)$. If n is even, two of the $d(p)$ functions give a 2-coloring of the boundary of the stars. It is when the 1 and the -1 do alternate. These two colorings are equivalent, and there are two manners to color the centers of the star, with one of the remaining colors of with the two remaining. Therefore if n is even we have $\mathrm{co}(p) = \frac{1}{2}d(p) + 1$. By considering n modulo 6 we get the proposition.

**Remark 5.1** Let E the set of the number of 4-colorings, up to permutation of the colors of the triangulation of the sphere. This set is multiplicative.

If $G_1$ and $G_2$ are triangulations of the sphere. We can glue these two spheres along a face and get a triangulation $G_1 \# G_2$ with $n(G_1) + n(G_2) - 3$ vertices, we have $\mathrm{co}(G_1 \# G_2) = \mathrm{co}(G_1)\mathrm{co}(G_2)$.

If we glue n tetrahedrons we can build a triangulation $T_n$ with $n + 3$ vertices and $\mathrm{co}(T_n) = 1$.
# 6 Hyperplans

We have seen that the good functions are special points of the projective space P. The dimension of P is $n-4$ in case 1 and 2 and $n-3$ in case 3. We are looking now at the intersection of P and the hyperplan $x_i = 0$.

Let $C_i$ be the $(n+1, 2n+4)$ matrix :

$$C_i = \begin{pmatrix} l_i \\ C \end{pmatrix},$$

where $l_i = (0, \dots, 0, 1, 0, \dots, 0)$ with 1 in the place $i$. Then $C_i x = 0$ is equivalent to $Cx = 0$ and $x_i = 0$.

**Proposition 6.2** For $i = 1, \dots, 2n-4$ the equation $x_i = 0$ defines a hyperplan of P

We will prove that $r(C_i) = r(C) + 1$ for any $i$. We have to prove that the row $l_i$ is not generated by the rows of the matrix $C$, which is equivalent to show the non existence of a function $f$ on the vertices with values in $F_3$ which satisfies

$$\sum_{T_i} f = 1, \sum_{T} f = 0 \text{ if } T \neq T_i$$

where the $T$'s are the faces and $\sum_T f$ is the sum of $f$ on the vertices of $T$. On the three vertices of the face $T_i$, $f$ must take two different values, $a$ on two vertices $V_1, V_2$ and $b$ on the third $V_3$. On the vertices of another face $T$, $f$ must take three different values $a, b, c$ or the same values. By considering the star of $V_1$ and the values of $f$ on the vertices of the link of this star we get a contradiction because on one side $f$ must take the value $a$ and on the other side $f$ must take successively the values $b$ and $c$. The proposition is proven.

We see that the good functions are the points of P outside of $2n-4$ hyperplans.

We will consider now the rank of the matrix $C_i$ on $\mathbb{R}$.

**Proposition 6.3** We have $r(C_i, \mathbb{R}) = r(C, \mathbb{R})$ only if the triangulation minus the face $T_i$ is a partition of stars and the three vertices of $T_i$ are of odd degrees. This situation can occur only in case 1. Other way we have $r(C_i, \mathbb{R}) = r(C, \mathbb{R}) + 1$.

The simplest example for which $r(C_i, \mathbb{R}) = r(C, \mathbb{R})$ is the tetrahedron with $T_i$ any one of its faces. In general let us name A, B, C the vertices of the face $T_i$ and D, E, F the vertices such that ABD, BCE, ACF are faces of the triangulation of the sphere. It is possible that D, E, F are not all different, in the case of the tetrahedron they are all the same. We are looking for a real-valued function $f$ on the vertices which satisfies

$$f(A) + f(B) + f(C) = 1, \sum_{T \neq T_i} f = 0.$$

If such a function exists we get $f(C) - f(D) = 1$. Consider now the link of A that means the boundary of the faces of the star of A. The sum of $f$ on all the faces of this star, but the face $T_i$, is equal to 0. Then the sequence on the vertices of the link from
C to B, f(C), f(F), ...f(D), f(B) must be periodic of period two, which implies that A has an odd degree and f(B) = f(C).

We can do the same for the other vertices B and C of Tᵢ and we get

$$f(A) = f(B) = f(C) = \frac{1}{3}, f(D) = f(E) = f(F) = -\frac{2}{3}$$

Then on the vertices all the faces T ≠ Tᵢ f takes the values 1/3, 1/3, -2/3 and Tᵢ and the stars of the vertices S' where f takes the value -2/3 form a partition of the set of the faces of the triangulation. The triangulation is in case 1 (rank(C, R) = n) since the edge AB has its two ends of odd degree, which is impossible in case 2 and 3.

The proposition is proven.

Moreover if in case 1 we have rank(Cᵢ, R) = n for Tᵢ = ABC then any edge whose two ends have an odd degree, has at least one of its ends in {A, B, C}.

**Proposition 6.4** The case 1 (rank(C, R) = n) can be divided in the following sub-cases. We keep the same notations A, B, C, D, E, F as above.

- case 1a : rank(C, R) = n and rank(Cᵢ, R) = n + 1 for all the faces Tᵢ.

- case 1b : rank(C, R) = n and rank(Cᵢ, R) = n for only one face Tᵢ = ABC.

- case 1c : rank(C, R) = n and rank(Cᵢ, R) = n for only two faces Tᵢ = ABC and Tᵢ = ABD. Then we have E = F.

- case 1d : rank(C, R) = n and rank(Cᵢ, R) = n for four faces Tᵢ = ABC, Tᵢ = BCD, Tᵢ = ACD and Tᵢ = ABD. Then we have E = F = G. The triangulation is the tetrahedron.

The simplest triangulation in case 1a has 7 vertices A, B, C, D, E, F, G and the 10 faces are ABC, ABD, BCE, ACF, ADG, BDG, BEG, CEG, CFG, AFG. The triangulation minus the face ABC is the union of the 3 stars of center {D, E, F}.

The simplest triangulation in case 1b has 6 vertices A, B, C, D, E, G and the 8 faces are ABC, ABD, ADG, AEG, ACE, BCE, BEG, BDG. The vertices A, B, C, D have an odd degree, the triangulation minus ABC is the union of the stars of center D and E, and the triangulation minus ABD is the union of the stars of center C and G.

# 7 Foldings

Let T₁ et T₂ be two triangulations of the sphere. We say that T₁ can be folded on T₂ if there exist a continuous PL application of T₁ on T₂. This application φ send every triangle of T₁ onto a triangle of T₂. To define φ it is sufficient to give a function f on the triangles of T₁ with values in {+1, -1} and give the image φ(t₀) of a triangle t₀ of T₁. Then we can have the following rule :

Let t = {a, b, c} and t' = {a, b, d} two contiguous triangles of T₁, and

$$\phi(t) = \{\phi(a), \phi(b), \phi(c)\}; \phi(t') = \{\phi(a), \phi(b), \phi(d)\}.$$
If $f(t) = f(t')$ then $\phi(t')$ is the triangle contiguous to $\phi(t)$ with the commune side $\{\phi(a), \phi(b)\}$. If $f(t) \neq f(t')$ then $\phi(d) = \phi(c)$ and $\phi(t') = \{\phi(a), \phi(b), \phi(d)\}$ is the triangle folded on $\phi(t)$ along the side $\{\phi(a), \phi(b)\}$. The condition on $f$ necessary to obtain $\phi$ continuous is that:

For every vertex $s$ of $T_1$ the sum of the values of $f$ on the triangles of the star of $s$ on $T_1$ vanishes modulo the degree of $\phi(s)$ on $T_2$.

In particular for the cases $T_2$ is the tetrahedron, the octahedron, the icosahedron the condition on the function $f$ on the triangles of $T_1$ in order to get a folding on $T_2$ is that the sum of the values of $f$ on the triangles of the star of any vertex of $T_1$ vanishes respectively modulo 3, 4 and 5.

The claim of Heawood is that the 4-colors problem is equivalent to the existence of a folding of any triangulation of the sphere to the tetrahedron.

In general this condition on $f$ is not sufficient if $T_2$ is not the tetrahedron or the octahedron

We can see that a triangulation of the sphere can be folded on the octahedron if and only if the degree of all his vertices are even. And in this case the triangulation can get a 3-coloring and it can be folded on a single triangle.

It is easy to see that the n-suspension can be folded on the (n-2)-suspension and by induction can be folded to the 5-suspension or to the octahedron which is the 6-suspension and then on the tetrahedron.

# 8 Use of a theorem of H. Whitney

Let us say that a triangulation of the sphere $G$ is decomposable if it contains a 3-circuit that is not the boundary of a face of $G$. Then $G = G_1 \# G_2$ where $G_1$ and $G_2$ are smaller triangulations of the sphere. To be not-decomposable is equivalent to be 4-connected.

In ([W]) H.Whitney has proven that a not-decomposable triangulation of the sphere is hamiltonian that means it contains a circuit without self intersections which passes through every vertex of the triangulation.

As H. Whitney does we can represent such a triangulation $G$ with $n$ vertices as a regular polygon of $n$ sides with the interior cut in triangles by diagonals not intersecting each other and the exterior decomposed also in faces by not intersecting arcs. It is easy to see that there are $n-2$ triangles in the interior and $n-2$ in the exterior. There are $n$ edges on the boundary of the polygon, $n-3$ in the interior and $n-3$ in the exterior.

**Definition 8.6** Let us call a *pie* a planar graph with $n$ vertices and $n$ edges forming a circuit without intersections and $n-3$ other edges as diagonals which cut the interior in $n-2$ triangles.

Then a not-decomposable triangulation $G$ of the sphere can be seen as two pies with the same boundary.

Let us consider the $n-2$ triangles and the $n-3$ diagonals of a pie $P$. We consider the graph $T_P$ which vertices are the triangles of $P$ and where there is an edge between two triangles if they have a diagonal as a commune side. We see that if $n > 3$ there are two triangles whose only one side is a diagonal and by induction we immediately get:
**Proposition 8.5** The graph $T_P$ is a connected tree whose nodes are of degree at most 3. If $n > 3$ the number of triangles with two sides at the boundary of the pie is equal to the number of triangles without any side on the boundary plus 2.

**Remark 8.2** A pie determines its tree $T_P$. But in general a connected tree whose nodes are of degree at most 3 can be associated to more than on pie. If $m$ is the number of its nodes of degree two, there are $2^m$ pies which can be associated to the tree.

We will now consider the 4-colorings of a pie with $n$ vertices. Let us recall that we consider the colorings up to permutation of the colors. Let $C_1$ be the incident matrix of the pie. Its size is $(n,n-2)$ and $C_1(i,j) = 1$ if the vertex $i$ belongs to the face $j$, other way $C_1(i,j) = 0$.

**Theorem 8.4** A pie $P_1$ with $n$ vertices admit $2^{n-3}$ 4-colorings. Among them one and only one is a 3-coloring. The kernel of $C_1^t$ is of dimension 2 and the rank of $C_1$ is $n-2$. This is true on $F_3$ and on $\mathbb{R}$. The image of $C_1$ on $F_3$ can be defined by the equations $\delta_0.x = 0$ and $\delta_1.x = 0$, where $\delta_0 = (1, 1, \dots, 1)$ and the coordinates of $\delta_1$ are a 3-coloring of the pie $P_1$ with the colors $\{1, 0, -1\}$. To define the image of $C_1$ on $\mathbb{R}$ we can use $\delta_1$ and $\delta_1' \neq \delta_1$ where the coordinates of $\delta_1'$ are also a 3-coloring of the pie $P_1$ with the colors $\{1, 0, -1\}$.

We are reduced to count the foldings of the pie $P$ on the tetrahedron. Then we count the number of functions $f$ on the triangles with values in $\{+1, -1\}$. There is no condition on $f$ because no vertex has its complete star in the set of the triangles. Then there are $2^{n-2}$ choices of $f$ and we divide by 2 because $f$ and $-f$ give equivalent colorings.

The graph $T_P$ is a tree then only two functions $f_0$ and $-f_0$ do alternate their values on contiguous triangles. For this $f_0$ the pie is folded on a single face of the tetrahedron and the pie is 3-colored.

We consider the kernel of the transposed matrix $C_1^t$. Consider a function on the vertices with values in $F_3$. The sum of the values at the 3 vertices of a triangle vanishes in $F_3$ if they are all equal or all different. This property propagates on the tree $T_P$. Then the kernel of $C_1^t$ is of dimension 2 and the rank of $C_1$ is $n-2$. For the same property of $F_3$ we see that the equations of the image of $C_1$ are $\delta_0.x = 0$ and $\delta_1.x = 0$.

By using the permutations of the colors $\{1, 0, -1\}$, we get 6 equivalent 3-coloring of the pie. On $F_3$ the corresponding $\delta$'s are in a vector space of dimension 2 and the 3 remaining vectors are $\delta_0, -\delta_0$ and 0. Moreover we see that the vectors of the image of $C_1$ on $\mathbb{R}$ satisfy the 6 equations using the $\delta$'s corresponding to the permutations of the colors.

**Remark 8.3** Consider a pie with $n$ vertices and add a vertex $v$ in the exterior and $n$ edges between this vertex and the other vertices. We get a triangulation of the sphere which has only one 4-coloring. This can be seen also because this triangulation can be decomposed into $n-2$ tetrahedrons.
Let us consider now a not-decomposable triangulation T. By using the theorem of Whitney we can consider two pies, the interior pie $P_1$ and the exterior pie $P_2$, which have the hamiltonian circuit as the commune boundary.

We will now give a new proof of the part of theorem 4.2 concerning the rank of the incident matrix $C$ on the field $F_3$. We can separate the triangles of the interior and those of the exterior and write $C = [C_1, C_2]$, where $C_1$ and $C_2$ are respectively the incident matrices of the two pies.

Using the theorem above we get:

**Proposition 8.6** The ranks of $C_1$ and $C_2$ are n-2. If the triangulation can be 3-colored the image of $C_1$ and the image of $C_2$ are the same and the rank of $C$ is n-2. If at least one vertex has an odd degree the intersection of the images is of dimension $n-3$ and the rank of $C$ is n-1. The image of $C$ is defined by the equations $\delta_0.x = 0, \delta_1.x = 0, \delta_2.x = 0$, where $\delta_0 = (1, 1, \dots, 1)$ and the coordinates of $\delta_1$ and $\delta_2$ are respectively a 3-coloring of the pie $P_1$ or $P_2$ with the colors $\{1, 0, -1\}$. The equation defining the hyperplan which is sent by $C_1$ on the intersection of the images of $C_1$ and $C_2$ is $\delta_2 C_1.y = 0$ where $\delta_2 C_1$ is a function on the triangles of the pie $P_1$. Its value on the triangle $T_i$ is the sum of the values on the vertices of $T_i$ of the 3-coloring of the pie $P_2$ with the colors $\{1, 0, -1\}$.

**Remark 8.4** The space image of $C_1$ is defined by the equations $\delta_0.x = 0, \delta_1.x = 0$ where $\delta_1$ is a 3-coloring of $P_1$. The six 3-coloring equivalent to $\delta_1$, this mean by permutation of $\{1, 0, -1\}$ are $\delta_1, \delta_1 + \delta_0, \delta_1 - \delta_0$ and their opposite. Then we see that the definition of the image does not depend of the choice of $\delta_1$ among its equivalents.

Let us now give a way to define a squared block of the matrix $C$ having the rank of $C$. Recall that the rows correspond to the vertices and the columns to the triangles of the triangulation. Then we have to choose the triangles which are principal and those which are auxiliary.

**Proposition 8.7** If the rank of $C$ is $n-2$ we can say that the principal triangles are those of the exterior of the hamiltonian circuit. We can erase two rows corresponding to two vertices which are joined by an edge.

If the rank of $C$ is $n-1$, we can erase any row of $C$, and for the principal columns take the triangle of the exterior and add an interior triangle which is not colored by the 3-coloring of the exterior pie.

We recall that the number of 4-coloring of the n-suspension is:

$$mco(n) = \frac{2^{n-3}}{3} + (-1)^n \frac{5}{6} + \frac{1}{2}, n \geq 5.$$

We put $mco(4) = 1$, we have $mco(5) = 1$, $mco(6) = 4$ and the sequence is increasing for $n > 4$.

**Theorem 8.5** We have $co(G) \leq mco(n)$ for every triangulation $G$ with $n$ vertices for every $n > 3$. The n-suspension is the triangulation with $n$ vertices which has the biggest number of 4-colorings.
We will first prove it for the 4-connected triangulations. Let us remark that

$$mco(n) = \frac{2^{n-3}}{3} \left(1 - \frac{1}{2^{n-3}}\right), \text{ if n is odd,}$$

$$mco(n) = \frac{2^{n-3}}{3} \left(1 + \frac{1}{2^{n-5}}\right), \text{ if n is even,}$$

Let G a 4-connected triangulation with n vertices. If G has a vertex of degree n-1 we know that $co(G) = 1$ and if G has no more that one vertex of degree n-2, G is not the n-suspension.

Let consider G as union of two pies with boundary a hamiltonian circuit.

If G admit a 3-coloring, every vertex has an even degree. We can choose a vertex whose star contains one triangle of the exterior pie and m triangles of the interior pie, with $m \le n - 3$. Then m is odd. The good solutions of $Cx = 0$ are obtained by putting 1 or $-1$ on the interior triangles and hoping that the values on the exterior triangles will not vanish. Then we must have the sum of the values on the m triangles not equal to 0. But we see that the number of ways to do that is $\frac{2^m}{3}(1 - \frac{1}{2^m})$ and we get $co(G) \le \frac{2^{n-3}}{3}(1 - \frac{1}{2^m})$ which implies $co(G) < mco(n)$.

If G does not admit a 3-coloring, we can choose a vertex whose star contains one triangle principal and the m others are auxiliary triangles. Then the good ways of choosing the values on the m triangles is $\frac{2^m}{3}(1 - \frac{1}{2^m})$ if m is odd and $\frac{2^m}{3}(1 + \frac{1}{2^m})$ if m is even. Then we get $co(G) \le \frac{2^{n-4}}{3}(1 + \frac{1}{2^m})$ which implies also $co(G) < mco(n)$.

Now we come to the case of not 4-connected triangulations. It is true for $n = 4$. Suppose the assumption true for every $p \in [4, n-1]$. Let G a non 4-connected triangulation of the sphere with n vertices. Then $G = G_1\#G_2$ where $G_1$ has p vertices with $p > 3$ and $G_2$ has q vertices with $q > 3$ and $n = p + q - 3$.

If $G_1$ or $G_2$ is a tetrahedron we have $n = p+1$ or $n = q+1$ and $co(G) = mco(n-1)$ which is less than $mco(n)$.

Other way we have $p > 4, q > 4, n = p + q - 3 > 6$ and $co(G) = mco(p)mco(q)$.

Let for $n > 4$

$$\epsilon_n = \left(\frac{3}{2^{n-3}}\right)mco(n) - 1.$$

We have to prove that

$$\begin{align*}
mco(p)mco(q) &< mco(n), \\
(1 + \epsilon_p)(1 + \epsilon_q) &< 3(1 + \epsilon_n), \\
\epsilon_p + \epsilon_q + \epsilon_p\epsilon_q - 3\epsilon_n &< 2,
\end{align*}$$

and this is true because

$$|\epsilon_p| \le \frac{1}{2}, |\epsilon_q| \le \frac{1}{2}, |\epsilon_n| \le \frac{1}{8}.$$

The proof is complete.
# 9 The Whitney equivalence to the four colors theorem

In his paper of 1932, H. Whitney shows that to prove the four colors theorem it is sufficient to prove that any not decomposable triangulation of the sphere can be colored with 4 colors. He gives also the formula of Euler for the number of pies with n vertices :

$$P_n = 2^{n-3} \frac{3.5.7...(2n-5)}{3.4.5...(n-1)},$$

and says that we have to consider the $P_n^2$ planar graphs composed of two pies with the same cycle.

We easily get :

$$P_n = \frac{1}{n-1} \cdot \frac{(2n-4)!}{(n-2)!(n-2)!}$$

and

$$P_n \sim 4^{n-2} \frac{1}{\sqrt{\pi n^{3/2}}} \text{ as } n \to \infty.$$

When we glue two pies of n vertices along the cycle to get a planar graph G we do not always get a triangulation of the sphere. It can happen that two vertices are joined by a diagonal in both pies. But we can identify these two diagonals and see the graph G as the gluing of two planar graphs $G_1$ and $G_2$ along an edge, and see that G is 4-colorable if and only if $G_1$ and $G_2$ are. In fact we have :

**Proposition 9.8** If two planar graphs containing triangles $G_1$ and $G_2$ have only a commun edge then

$$\mathrm{co}(G) = 2\mathrm{co}(G_1)\mathrm{co}(G_2)$$

Indeed let $\mathrm{Col}$ a coloration of $G_1$ and $\mathrm{Co2}$ a coloration of $G_2$. If $\mathrm{Col}$ is fixed the colors of the two commun vertices are fixed and we find two colorings of $G_2$ equivalent to $\mathrm{Co2}$ who give with $\mathrm{Col}$ two not equivalent colorings of G. If we consider the couples of pies $P1$ and $P1$ then we can glue all the n-3 interior edges and we get a collection of n-2 triangles. Since a triangle T has $c(T) = 1$ we get $c(P1) = 2^{(n-3)}$.

It can happen also that there exists a 3-cycle in G, which is not a triangle. Then G is the gluing of two planar graphs $G_1$ and $G_2$ along a face and we have the same conclusion since we have seen that $\mathrm{co}(G) = \mathrm{co}(G_1)\mathrm{co}(G_2)$. We will see use this property for the following example :

**Definition 9.7** We call a scallop a pie of n vertices having one vertex $v_1$ joined to all the others by an edge.

As an exemple consider a scallop $P1$ of n vertices having one vertex $v_1$ joined to all the others by an edge. Let $P2$ be any another pie and consider the graph G obtained by gluing $P1$ and $P2$ along their cycle with the vertex v coinciding with a vertex $v_2$
of P2 having the property that no interior edge of P2 ended at $v_2$, other way $v_2$ and its two neighboring vertices constitute a triangle of P2. Then the triangulation G of the sphere is the cone of summit $v = v_1 = v_2$ over the pie of n-1 vertices obtained by cutting the triangle containing $v_2$ from P2. We see that G can be decomposed in n-3 tetrahedrons and co(G) = 1.

Then we have the **Whitney equivalence**:

**Theorem 9.6** *The four color theorem is equivalent to the following statement :*

*For any $n \ge 3$, any couple of pies P1 and P2 with $n$ vertices have a commun 4-coloring.*

*This is equivalent to the fact that if their incident matrix are $C_1$ and $C_2$ there exists $x_1$ and $x_2$ in $F_3^{n-2}$ with all their coordinates non vanishing satisfying $C_1x_1 = C_2x_2$.*

Let now count the number of colorings of a n-cycle for $n \ge 3$. Let $C(n)(k)$ be the number of coloring of an n-cycle with exactly k colors up to permutations of the colors.

**Proposition 9.9** *We have $C(n)(0) = 0, C(n)(1) = 0$,*

$$C(n)(2) = \frac{1 + (-1)^n}{2}, C(n)(3) = \frac{2^n - (-1)^n - 3}{6}, C(n)(4) = \frac{3^n - 2^{n+2} + (-1)^n + 6}{24}$$

This comes from the following : The chromatic polynomial of a n-cycle is

$$Q_n(t) = (t - 1)^n + (-1)^n(t - 1)$$

and

$$C(n)(2) = \frac{Q_n(2)}{2},$$

$$C(n)(3) = \frac{Q_n(3)}{6} - C(n)(2),$$

$$C(n)(4) = \frac{Q_n(4)}{24} - C(n)(3) - \frac{C(n)(2)}{2}.$$

We have seen that any pie has, up to permutation of the four colors, one 3-coloring and $2^{n-3} - 1$ 4-colorings. It is natural to see if we get all the colorings of the cycle.

**Proposition 9.10** *Let us consider a 4-coloring or a 3-coloring of a n-cycle for $n \ge 3$, There exists at least one n-pie which admits this coloring.*

We prove it by induction on n. It is true for n=3. Suppose that it is true for p = 3, .., n - 1 and consider a coloring Co with 3 or 4 colors. There exists 3 successive vertices $v_{j-1}$, $v_j$, $v_{j+1}$ with 3 different colors.

If Co is a 4-coloring we can join $v_{j-1}$ and $v_{j+1}$ by a diagonal and the (n-1)-cycle got by removing $v_j$ has a 3-coloring or a 4-coloring and there exists a (n-1)-pie admitting this coloring. With the added above diagonal we get an n-pie we want.

If Co is a 3-coloring and $v_j$ is not the unique vertex with its color then the (n-1)-cycle got by removing $v_j$ has a 3-coloring and we do exactly the same thing than in
the previous case. If $v_j$ is not the unique vertex with its color, then $v_j, v_{j+1}, v_{j+2}$ have different colors and $v_{j+1}$ is not the unique vertex with its color. Then we can join $v_j$ and $v_{j+2}$ by a diagonal and use a (n-1)-pie admitting the coloring of the (n-1)-cycle got by removing $v_{j+1}$.

The proposition is proven.

Since the number of pies if of order $4^n$ and the number of 3-coloring of the n-cycle is of order $2^n$ it happens that different pies can be colored by the same 3-coloring. For 7 vertices there exists 21 3-colorings and 42 pies. We can see that 7 3-colorings correspond each to one pie, 7 others correspond to two pies, and the last 7 correspond to three pies.

Let us consider a n-cycle with a 3-coloring with the letters {a, b, c}. Consider two not consecutive vertices $v_1$ and $v_2$ with color a and b. There exists a pie having the interior edge $v_1v_2$ if and only if each of the two arcs joining $v_1$ and $v_2$ contain a vertex with color c.

We can deduce immediately that the 3-coloring of a scallop is the 3-coloring of only the scallop.

Consider now two pies $P_1$ and $P_2$ with n vertices. Let $C_1$ and $C_2$ their incident matrices and $E_1, E_2$ the respective images of $C_1$ and $C_2$. If $P_1$ and $P_2$ have the same 3-coloring then $E_1 = E_2$ and we have $C_1x_1 = \pm C_2x_2$ if the components of $x_1$ alternate on the triangles of the tree of $P_1$ and $x_2$ has the same properties on the tree of $P_2$.

Suppose now that $P_1$ and $P_2$ have different 3-coloring. Then the spaces $E_1$ and $E_2$ are not the same and their intersection $E_1 \cap E_2$ has dimension $n-3$. We are looking on the existence of $x_1$ and $x_2$ without vanishing components such that $C_1x_1 = C_2x_2$. Of course $C_1x_1$ and $C_2x_2$ must belong to $E_1 \cap E_2$. The following proposition has an interest.

**Proposition 9.11** Let $P_1$ and $P_2$ with n vertices and different 3-colorings. We color the vertices with the 3-coloring of $P_2$. A triangle T of $P_1$ has its vertices colored with 1 or 2 or 3 colors. If this number of colors is 1 or 3 then the image by $C_1$ of the vector with component 1 on T and 0 on the other triangles is in $E_1 \cap E_2$. If this number is 2 then the image is in $E_1$ but not in $E_2$. The number of triangles of $P_1$ with 2 colors is m and $m > 1$. The number of vector $x_1$ without vanishing components such that $C_1x_1 \in E_1 \cap E_2$ is

$$ \frac{2^{n-2}}{3} \left(1 + \frac{(-1)^m}{2^{m-1}}\right) $$

which is between $\frac{2^{n-2}}{4}$ for $m=3$ and $\frac{2^{n-2}}{2}$ for $m=2$ and is greater than $\frac{2^{n-2}}{3}$ if m is even and less than $\frac{2^{n-2}}{3}$ if m is odd.

Only the interior edges can have the same color at their ends. We have at least $m=1$ and at least one interior edge with this property. The two triangles having this edge as a side have 1 or 2 colors. One triangle with 1 color correspond to a node of the tree of $P_1$ and the 3 triangles having a side in commun with it have also 1 or 2 colors. A triangle having only one interior side correspond to a leaf of the tree and he has 2 or 3 colors. We get that $m \ge 2$, and that $m \ge 3$ if there exists a triangle with 3 colors.
To build an $x_1$ without vanishing components satisfying $C_1x_1 \in E_2$ we can put $\pm 1$ on the triangles having 1 or 3 colors and the good choices on the w triangles with 2 colors to satisfy the equations of $E_2$ are

$$ \frac{2^m}{3} \left( 1 + \frac{(-1)^m}{2^{m-1}} \right). $$

The proposition is proven.

**Remark 9.5** If we call $m_1$ the value of m above and $m_2$ the value obtained when we exchange the pies $P_1$ and $P_2$ it can happen that $m_1 \neq m_2$.

# 10 Generating the pies and the 4-connected triangulations of the sphere

In this section we will show how to build and sort the pies of n vertices and how we can represent a pie by a function on the n-cycle with values in $N*$.

**Definition 10.8** We call degree function of a pie the function on the n-cycle which value at the vertex a is the number of triangles having a as a vertex.

We know that the set of the triangles of the pie has a structure of a tree. Then there exist at least two triangles which have two sides at the boundary and the degree of the vertex commune to these sides is 1. Then the degree function has the value 1 on at least two vertices.

**Proposition 10.12** The degree function on a n-cycle determines all the triangles of the pies.

We prove this by induction on n. For n=3 the only degree function is (1,1,1). Suppose that d is the degree function of a n-cycle. The exist at least two vertices where d=1. Let $v_j$ be one of them. If we erase the triangle of vertices {$v_{j-1}, v_j, v_{j+1}$ we get a pie with n-1 vertices {$v_1, ..v_{j-1}, v_{j+1}, ..v_n$} and degree d' with $d'(v_{j-1}) = d(v_{j-1})$ and $d'(v_{j+1}) = d(v_{j+1})$. This function d' take at least twice the value 1 because it is the degree function a pie and successively we recover all the triangles of the initial pie.

The degree function contains not only the tree of the triangles but also the way this tree is drawn on the plane. The degree functions

$$ (1, 3, 1, 5, 1, 3, 1, 4, 1, 4) \text{ and } (1, 3, 1, 4, 1, 4, 1, 3, 1, 5) $$

represent two different pies, with the same tree.

The dihedral group $D_n$ of order 2n acts on the n-cycle. The following definition is natural.

**Definition 10.9** Two pies of respective degrees $d_1$ and $d_2$ are equivalent if there exists an element g of the dihedral group such that $d_2 = d_1 \circ g$.
If the $n$ points of the cycle are the vertices of the regular convex polygone and the interior edges are strait lines then two pies are equivalent by an isometry if they are equivalent in the former sense.

The cardinal of the equivalence class of a pie is $\frac{2n}{p}$ if $p$ is the order of the stabilizer of the pie under the action of the dihedral group.

As a representative of this equivalence class we can choose the first by lexicographic order in the list of the degrees of all the pies of the classes.

Let $P_n$ be the set of the representative of all the equivalence classes of pies with $n$ vertices. Let $d \in P_n$ a degree function. If $d = \{d_1, d_2, ..., d_n\}$, the $n$ functions $d = \{d_1, d_2, ..., d_{j-2}, d_{j-1} + 1, 1, d_{j+1} + 1, d_{j+2}, ..., d_n\}$ are degree functions of pies with $n+1$ vertices. If we do this for all $d \in P_n$, we can get at least one pie of all the equivalence classes of pies with $n+1$ vertices and it is easy to build the set $P_{n+1}$.

Let us consider now the set of pairs of pies with $n$ vertices. The product $D_n \times \mathbb{Z}/2$ acts on the pairs. The dihedral group acts on the two members of the pairs and $\mathbb{Z}/2$ exchange or not these two members.

**Definition 10.10** *Two pairs of pies of degree functions ($d_1, d_2$) and ($d'_1, d'_2$) are equivalent if they are in the same orbit of the action of $D_n \times \mathbb{Z}/2$ on the set of pairs.*

In the case where the pair of pies form a triangulation of the sphere by gluing them the equivalence corresponds to an isometry of the graphs.

The cardinal of an equivalent class of a pair of degree functions is $\frac{4n}{p}$ where $p$ is the order of the stabilizer of the pair.

If we know the two degree functions $d_1$ and $d_2$ we can recover all the triangles of the two pies and then all the elements of the triangulation of the sphere. Of course this triangulation of the sphere must be hamiltonian.

**Definition 10.11** *We will call representative of an hamiltonian triangulation of the sphere the first by lexicographic order of the pairs of degree functions associated to all the pairs of pies separated by an hamiltonian circuit of the triangulation.*

**Remark 10.6** *It seems to be interesting to represent a graph on $n$ vertices with only $2n$ positive integers ($d_1, \dots, d_n, d'_1, \dots, d'_n$) but the number of hamiltonian circuits of a graph can be very large, between $n^2$ and $3^n$, and it takes a very long time to sort all the pairs of pies which represent the same graph and find the first pair in lexicographic order.*

This is why for the computation of the next section we have used the list of $c'(n)$ given by [B,VdC,MvK].

# 11 Computation and conjectures

In this section we restrict to the set of 4-connected triangulations of the sphere, with $n$ vertices which is called $c_4(n)$ by the authors of the code plantri ([B,VdC,MvK]). This set is important because any triangulation of the sphere can be decomposed in
a product of elements of c4 and we can get its co as the product of the co of these elements. And H. Whitney has proven that all the graphs of c4 are hamiltonian we have also computed the number ch of hamiltonian circuits of these graphs. We have computed all the ch's for $n \le 19$, all the co's for $n \le 21$ and the minimum of the co's for $n \le 24$.

What can we see considering the data for $n \le 21$?

The minimum of co is slightly increasing if we restrict to n odd or to n even. This is a confirmation of the four colors theorem. It seems also that $co = 1$ happens only for the tetrahedron or for a triangulation product of tetrahedrons.

For $n \ge 15$ the minimum of co is reached by many triangulations of c4(n). In the last column, for $n < 24$ we have written the number of times $min(co)$ is reached.

We have seen in theorem 8.5 that the maximum of co for n fixed is obtained for the n-suspension and is, as we have already seen,

$$mco(n) = \frac{2^{n-3}}{3} + (-1)^n \frac{5}{6} + \frac{1}{2}, n \ge 5.$$

We put $mco(4) = 1$, we have $mco(5) = 1$, $mco(6) = 4$ and the sequence is increasing for $n > 4$.

The minimum of ch is also obtained for the n-suspension and is $2(n-2)(n-4)$. This has been checked for $n \le 19$ and is written with an asterisk for $19 < n \le 27$.

The maximum of ch seems to be obtained for $n > 13$ for a graph with vertices of degree 5 or 6 whose dual is a fullerene. This is checked for $n = 14, 15, 16$ and the $max(ch)$ for $n = 17, ..., 24$ given in the table are the $max(ch)$ for the graphs with vertices of degree 5 or 6.

If we consider the set of the numbers of coloring of all the graphs of c4(n), for $12 \le n \le 21$ we see that it contains a large interval $I(n)$ whose minimum is close to $min(co)$ and that the union of the $I(n)$ for $n \le p, p \ge 21$ contains all the integers from 1 to 3686.

Then we can formulate the following

**Conjecture 1** For any positive integer co there exist a finite number of 4-connected graphs which get exactly co distinct 4-colorings up to permutations of the colors.

This requires two things. The $I(n)$ must cover all the set of positive integers and $lim(inf(I(n))) = +\infty$.
<table><thead><tr><th>n</th><th>card(c4(n))</th><th>min(ch)</th><th>max(ch)</th><th>min(co)</th><th>max(co)</th><th>I(n)</th><th>minima</th></tr></thead><tbody><tr><td>4</td><td>1</td><td>3</td><td>3</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>6</td><td>1</td><td>16</td><td>16</td><td>4</td><td>4</td><td>4</td><td>1</td></tr><tr><td>7</td><td>1</td><td>30</td><td>30</td><td>5</td><td>5</td><td>5</td><td>1</td></tr><tr><td>8</td><td>2</td><td>48</td><td>60</td><td>3</td><td>12</td><td>3</td><td>1</td></tr><tr><td>9</td><td>4</td><td>70</td><td>122</td><td>2</td><td>21</td><td>2</td><td>1</td></tr><tr><td>10</td><td>10</td><td>96</td><td>268</td><td>5</td><td>44</td><td>5:8</td><td>1</td></tr><tr><td>11</td><td>25</td><td>126</td><td>508</td><td>4</td><td>85</td><td>6:11</td><td>1</td></tr><tr><td>12</td><td>87</td><td>160</td><td>1280</td><td>5</td><td>172</td><td>5:19</td><td>1</td></tr><tr><td>13</td><td>313</td><td>198</td><td>2222</td><td>4</td><td>341</td><td>4:35</td><td>1</td></tr><tr><td>14</td><td>1357</td><td>240</td><td>5076</td><td>6</td><td>644</td><td>6:74</td><td>1</td></tr><tr><td>15</td><td>6244</td><td>286</td><td>10004</td><td>8</td><td>1365</td><td>8:114</td><td>4</td></tr><tr><td>16</td><td>30926</td><td>336</td><td>20318</td><td>10</td><td>2732</td><td>10:202</td><td>8</td></tr><tr><td>17</td><td>158428</td><td>390</td><td>40812</td><td>8</td><td>5461</td><td>8:366</td><td>2</td></tr><tr><td>18</td><td>836749</td><td>448</td><td>84412</td><td>12</td><td>10924</td><td>12:658</td><td>2</td></tr><tr><td>19</td><td>4504607</td><td>510</td><td>168579</td><td>16</td><td>21845</td><td>16:1258</td><td>15</td></tr><tr><td>20</td><td>24649284</td><td>576*</td><td>347017*</td><td>20</td><td>43692</td><td>20:2118</td><td>42</td></tr><tr><td>21</td><td>136610879</td><td>646*</td><td>704149*</td><td>16</td><td>87381</td><td>24:3686</td><td>3</td></tr><tr><td>22</td><td>765598927</td><td>720*</td><td>1445871*</td><td>24</td><td>174764*</td><td></td><td>6</td></tr><tr><td>23</td><td>4332047595</td><td>798*</td><td>2333880*</td><td>32</td><td>349525*</td><td></td><td>42</td></tr><tr><td>24</td><td>24724362117</td><td>880*</td><td>6089764*</td><td>40</td><td>699052*</td><td></td><td></td></tr><tr><td>25</td><td>142205424580</td><td>966*</td><td></td><td></td><td>1398101*</td><td></td><td></td></tr><tr><td>26</td><td>823687567019</td><td>1056*</td><td></td><td></td><td>2796204*</td><td></td><td></td></tr><tr><td>27</td><td>4801749063379</td><td>1150*</td><td></td><td></td><td>5592405*</td><td></td><td></td></tr></tbody></table>

In this table all the data without asterisk have been computed. The data with asterisk are supposed after the following conjectures.

We give now a word about the algorithm we use to compute co. Let T be a triangulation of the sphere. We built step by step sets E of partial colorings of T having the following property :

(A) Every completed coloration not already found is an extension of a unique partial coloration belonging to the set E.

At the beginning we choose a triangle of T and we color the vertices with 3 different colors. The first set E is this unique partial coloring.

Given a partial coloring pc of a set E, we choose a non colored vertex s for which the number p of possible colors is minimum. If $p = 0$ then we delete pc and the set $E \setminus pc$ has also the property A. If $p > 0$ we replace pc by the p new partial colorings with the vertex s colored by the possible colors. We obtained again a set having the property A.

If pc is a complete coloring of T, then we put it in the set of founded coloring, and $E pc$ has the property A.

The algorithm to compute ch follows the same way. A partial hamiltonian circuit is a set of edges such that every vertex is the end of at most two of these edges and such there is no circuit of length less than n. We built step by step sets of partial
hamiltonian circuit having a property similar to (A).

When the cardinal of c4(n) is too large, we can find the minimum of co without computing all the co's. If we have computed co for of subset of c4(n) and the minimum of these co is 40, we stop the computation for a new triangulation as soon we have found 41 colorations.

# 12 Series of triangulations of the sphere

In this section we build some series of triangulations $T_n, n \ge n_0$ of 4-connected triangulations of the sphere for which $T_n$ has n vertices and a great number co of 4-colorings and a small number ch of hamiltonian circuits. We will use the following formula.

**Proposition 12.13** Let G be a triangulation of the sphere with a circuit of length 4. Let $G_1$ be the subgraph of G containing the circuit and the part of G at one side of the circuit, and $G_2$ the subgraph of G containing the circuit and the part of G at the other side of the circuit, Let $\alpha_1, \beta_1, \gamma_1, \delta_1$ be the numbers of 4-colorings of the graph $G_1$ such that the colors on the successive vertices of the 4-cycle are respectively equivalent to abcd, abcb, abac, abab. Let $\alpha_2, \beta_2, \gamma_2, \delta_2$ be the corresponding numbers of 4-colorings of the graph $G_2$. Then we have the formula for the number of 4-coloring of the triangulation G :

$$co(G) = \alpha_1\alpha_2 + \beta_1\beta_2 + \gamma_1\gamma_2 + 2\delta_1\delta_2.$$

Indeed when the coloring of the 4-cycle is given the coloring on $G_1$ and the coloring on $G_2$ are fixed in general, but in the case where the 4-cycle is colored with two colors abab we get, given a coloring of $G_1$ and a coloring of $G_2$, two different 4-colorings of G since we can permute the colors c, d on one side and not on the other side of the circuit.

**Definition 12.12** For $n \ge 5$ let $A(n)$ be the graph obtained by dropping an edge at the boundary of the disks of the n-suspension. $A(n)$ has n vertices, $3n - 7$ edges, and its faces are $2n - 6$ triangles and one which is 4-sided.

Let $v_1, v_2, v_3, v_4$ the vertices at the boundary of the 4-sided face of $A(n)$, with the degrees of $v_1$ and $v_3$ is $n - 2$ and the degrees of $v_2$ and $v_4$ is 1.

**Proposition 12.14** Let $\alpha_n, \beta_n, \gamma_n, \delta_n$ be the numbers of 4-colorings of $A(n)$ having respectively up to equivalence the colors abcd, abcb, abac, abab on these vertices. Let $a(n) = co(A(n))$ and $b(n) = mco(n)$ be the number of 4-colorings of the n-suspension. Then

$$\alpha(n) = \frac{1}{2} + \frac{(-1)^n}{2}, \quad \beta(n) = \frac{1}{2} - \frac{(-1)^n}{2},$$

$$\gamma(n) = \frac{2^n}{24} + \frac{(-1)^n}{3}, \quad \delta(n) = \frac{2^n}{48} - \frac{(-1)^n}{3},$$

$$a(n) = \frac{2^n}{16} + 1, \quad b(n) = \frac{2^n}{24} + \frac{5}{6}(-1)^n + \frac{1}{2}.$$
We use the trick of Birkhoff and we get

$$a(n) = b(n) + b(n - 1)$$

if we add the omitted edge of the n-suspension $v_2v_4$. If we add the edge $v_1v_3$ we get

$$a(n) = c(n) + d(n)$$

where $c(n)$ is the number of 4-coloring of the scallop with $n - 1$ vertices, and $d(n)$ is the number of coloring of the graph with the added edge. We have immediately

$$c(n) = \frac{2^n}{16}, d(n) = 1.$$

Then with $b(n) + b(n - 1) = \frac{2^n}{16} + 1$ and $b(5) = 1$, we find the result for $b(n)$. We also have that $\alpha_n$ et $\beta_n$ are the number of coloring with two colors respectively of a (n-2)-cycle or of a (n-2)-line. We get the value of $\alpha_n$ and of $\beta_n$. With $b(n) = \alpha_n + \gamma_n$, and $\gamma_n + \delta_n = \frac{2^n}{16}$ we get the values of $\gamma_n$ and $\delta_n$.

**Definition 12.13** Let $F(n)$, $n \ge n_0$ be a series of graph with a 4-cycle such that one side is a fixed graph $G$ with $m_0$ vertices and the other side is $A_m$ with $m = n - m_0 + 4$ and $n_0 = m + m_0 - 4$.

In particular the n-suspension is a series $F(n)$ for which $G_0$ is the graph with the circuit $v_1v_2v_3v_4$ and the edge $v_2v_4$.

**Proposition 12.15** Let $co(n)$ be the number of 4-coloring of $F(n)$. There exist three constants $c_2, c_1, c_0$ such that

$$co(F(n)) = c_2 2^n + c_1 (-1)^n + c_0.$$

The constants depend of the values $\alpha, \beta, \gamma, \delta$ for $G$ and $m_0$. The formula is :

$$\begin{aligned} co(F(n)) = & (\gamma + \delta) \frac{2^m}{24} + (\frac{\alpha}{2} + \frac{\beta}{2} + \frac{\gamma}{3} - \frac{2\delta}{3})(-1)^m + (\frac{\alpha}{2} + \frac{\beta}{2}); \\ & m = n + m_0 - 4. \end{aligned}$$

We consider now the number $ch$ of hamiltonian circuit of the series $F(n)$.

**Proposition 12.16** Let $F(n)$ a series of 4 connected triangulations of the sphere as above. There exists three constants $a_2, a_1, a_0$ such that

$$ch(F(n)) = a_2 n^2 + a_1 n + a_0$$

In particular for the n-suspension we have $mch(n) = 2n^2 - 12n + 16$.

The vertices of $A_m$ are $v_1, v_2, v_3, v_4$ and $w_1, \dots, w_{m-4}$ which are of degree 4. Consider an edge $w_iw_{i+1}$. If an hamiltonian circuit does not contains this edge then it must contain one of $w_i v_1, w_i, v_3$ and one of $w_{i+1} v_1, w_{i+1} v_3$. Since the circuit contains only
two edges ending at each vertex, we see that there are at most two edges of the line $w_1w_{m-4}$ missing in an hamiltonian circuit.

Then we can count the number of hamiltonian circuits. We find :

$2(m-5)(m-4)$ paths from $w_1$ to $w_2$ containing all the w's and $v_1, v_3$ and omitting two non consecutive edges of the line $w_1w_{m-4}$.

$2(m-6)$ paths from $w_1$ to $w_2$ containing all the w's and $v_1, v_3$ and omitting two consecutive edges of the line $w_1w_{m-4}$.

$2(m-5)$ paths from $w_1$ to $w_2$ containing all the w's and one of $v_1, v_3$ and omitting one edge of the line $w_1w_{m-4}$.

$m-5$ couples of paths $w_1...w_iv_1$ and $v_3w_{i+1}, ...w_m$ and m-5 couples with $v_1$ and $v_3$ exchanged.

one path $w_1, ..., w_m$

Since $m = n - m_0 + 4$ and since there is a finite and independent of n number of ways to complete the paths or couple of paths we have enumerated we see that the number of hamiltonian circuit is as we said, and the proposition is proven.

We will build now a series of 4 connected triangulations with n vertices for which co does not increase so fast. We call it the cigar.

**Definition 12.14** Let A be the piece of tube formed by the four lateral faces of a cube. We draw one diagonal of the four square in such a way that the 8 vertices of A are all of degree 4. We consider $A_m$ a long tube obtained in gluing a collection of m piece A along their 4-vertices faces. Finally we close the cigar $C(n)$ by gluing at each end a square pyramid. Then $C(n)$ is a triangulation of the sphere with n vertices where $n = 6 + 4m$ and 2 vertices have degree 4, 8 (if $m > 0$) have degree 5 and the others have degree 6.

**Proposition 12.17** The number of 4-coloring of the cigar $C(n)$ is $2^m \times 6 = 2^{\frac{n-2}{4}} \times 3$

We know that there are 4 ways to color a cycle of length 4. We find that there are 8 4-coloring of the graph A. Each coloring of A gives a coloring of the two ends of the tube. Let M a (4,4) matrix. $M(i, j)$ is the number of 4-coloring of A who gives the coloring i to the first end and the coloring j to the other end. Because A has a symmetry which exchange the both ends the matrix M is symmetric. We find

$$M = \begin{pmatrix} 2, 0, 0, 0 \\ 0, 1, 1, 0 \\ 0, 1, 1, 0 \\ 0, 0, 0, 2 \end{pmatrix}.$$

Then $M^m = 2^{m-1}M$ and $M^m(i, j)$ is the number of 4-coloring of the long tube having coloring i and j at the ends of the tube. Then using the proposition 12.12 we get the number of 4-coloring of the cigar. We see that the sequence $ch(C(n))$ is increasing more slowly than $ch(F(n))$ for every series $F(n)$ as above.

This construction can be generalized using a different piece of tube A and closing differently the ends of a long tube made of pieces A.
Consider now the five series $F_0, F_1, F_2, F_3, F_4$ where $F_0(n)$ is the n-suspension and $F_j, j = 0, 1, 2, 3, 4$, is built with the following $G_j$.

<figure><img src="image_2.png" /><figcaption>A_m</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>G_0</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>G_1</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>G_2</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>G_3</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>G_4</figcaption></figure>

We have :

<table><thead><tr><th></th><th>co(n)</th><th>ch(n)</th></tr></thead><tbody><tr><td>$F_0(n)$</td><td>$\frac{2^n}{24} + \frac{5}{6}(-1)^n + \frac{1}{2}$</td><td>$2n^2 - 12n + 16$</td></tr><tr><td>$F_1(n)$</td><td>$\frac{2^n}{48} + \frac{25}{6}(-1)^n + \frac{5}{2}$</td><td>$4n^2 - 20n + 46$</td></tr><tr><td>$F_2(n)$</td><td>$\frac{2^n}{96} - \frac{5}{3}(-1)^n + 2$</td><td>$4n^2 - 30n + 44$</td></tr><tr><td>$F_3(n)$</td><td>$\frac{2^n}{64} - 5(-1)^n + 3$</td><td>$4n^2 + 24n - 454$</td></tr><tr><td>$F_4(n)$</td><td>$\frac{2^n}{64} + \frac{35}{2}(-1)^n + \frac{21}{2}$</td><td>$\frac{33}{8}n^2 - \frac{13}{4}n - 2120$</td></tr></tbody></table>

Considering the computation for $n < 18$ we propose :

**Conjecture 2** $F_0(n)$ has not only the highest co but also the least ch of c4(n) for $n \ge 6$.

$F_1(n)$ has the second highest co and the third least ch of c4(n) for $n \ge 10$.

$F_2(n)$ has the second least ch of c4(n) for $n \ge 9$.

$F_3(n)$ has the third highest co of c4(n) if n is odd and $n \ge 11$.
$F_4(n)$ has the third highest co of $c4(n)$ if $n$ is even and $n \ge 14$.

More generally for any series $F(n)$ as above there exist $n_0$ and three rank $r1, r2, r3$ such that for $n \ge n_0$ $F(n)$ has the rank $r1$ among the lowest ch in $c4(n)$, the rank $r2$ for $n$ odd and the rank $r3$ for $n$ even among the highest co in $c4(n)$.

# 13 Reduction to the 5-connected triangulations of the sphere

It can be shown that if a triangulation $G$ of the sphere contains a circuit of length 4 with vertices on the both sides of the circuit then $G$ cannot be the smallest triangulation which cannot be colored with four colors (see [S-K] page 59). Then the 4 colors problem is equivalent to the fact that $co(G) > 0$ for all the 5-connected triangulations. The smallest is the icosahedron.

Let $c5(n)$ be the set of 5-connected triangulations of the sphere with $n$ vertices.

<table><thead><tr><th>n</th><th>card(c5(n))</th><th>min(co)</th><th>max(co)</th><th>J(n)</th></tr></thead><tbody><tr><td>12</td><td>1</td><td>10</td><td>10</td><td></td></tr><tr><td>13</td><td>0</td><td></td><td></td><td></td></tr><tr><td>14</td><td>1</td><td>20</td><td>20</td><td></td></tr><tr><td>15</td><td>1</td><td>32</td><td>32</td><td></td></tr><tr><td>16</td><td>3</td><td>27</td><td>42</td><td></td></tr><tr><td>17</td><td>4</td><td>16</td><td>40</td><td></td></tr><tr><td>18</td><td>12</td><td>30</td><td>78</td><td></td></tr><tr><td>19</td><td>23</td><td>36</td><td>104</td><td></td></tr><tr><td>20</td><td>71</td><td>54</td><td>152</td><td></td></tr><tr><td>21</td><td>187</td><td>58</td><td>184</td><td></td></tr><tr><td>22</td><td>627</td><td>78</td><td>288</td><td>106:190</td></tr><tr><td>23</td><td>1970</td><td>88</td><td>357</td><td>122:266</td></tr><tr><td>24</td><td>6833</td><td>116</td><td>643</td><td>144:334</td></tr><tr><td>25</td><td>23384</td><td>139</td><td>882</td><td>194:510</td></tr><tr><td>26</td><td>82625</td><td>180</td><td>1276</td><td>238:730</td></tr><tr><td>27</td><td>292164</td><td>216</td><td>1799</td><td>288:1042</td></tr><tr><td>28</td><td>1045329</td><td>274</td><td>2904</td><td>338:1538</td></tr><tr><td>29</td><td>3750277</td><td>336</td><td>4334</td><td>410:2102</td></tr><tr><td>30</td><td>13532724</td><td>408</td><td>6640</td><td>480:3150</td></tr><tr><td>31</td><td>48977625</td><td>510</td><td>9794</td><td>598:4518</td></tr></tbody></table>

In fact we can reduce the computation to the subset $c5(n)$ of the 5-connected graphs which is smaller than $c4(n)$. It contains an interval $J(n)$ and the union of the $J(n)$ for $n = 22, \dots, 31$ contains the interval $[106, 4518]$. We also observe that the $min(co)$ is increasing with $n$. And we can suggest the following :

**Conjecture 3** Every integer larger than 105 is the number of 4-colorings of a finite set of 5-connected triangulations of the sphere.
14 Conclusion

Even if we do not give a new proof of the 4 colors theorem, we present some conjectures
which go further.

It is natural to determine the set of number of coloring of the 4-connected triangu-
lations of the sphere. We conjecture that it is N*.

We conjecture also that only 1,2 and 3 are the numbers of colorations of only one
4-connected triangulation of the sphere. In the pictures below we give the 4-connected
triangulations which have co 2 and co 3.

The computations illustrate also the theorem of Whitney. Every 4-connected trian-
gulation of the sphere is hamiltonian and it seems that the number of circuits increase
with the number of vertices.

<figure><img src="image_8.png" /><figcaption>degree = 122331234</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>degree = 332214321</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>$n = 9, ch = 122, co = 2$</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>degree = 12232134</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>degree = 32312421</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>$n = 8, ch = 60, co = 3$</figcaption></figure>

**References**

[A-H1] Appel, K.; Haken, W.; Every planar map is four colorable. I. Discharging.
Illinois J. Math. 21 (1977), no. 3, 429-490.

[A-H2] Appel, K.; Haken, W.; Koch, J.; Every planar map is four colorable. II.
Reducibility. Illinois J. Math. 21 (1977), no. 3, 491-567.
[A-H3] Appel, K.; Haken, W.; Every planar map is four colorable. With the collaboration of J. Koch. Contemporary Mathematics, 98. American Mathematical Society, Providence, RI, 1989. xvi+741 pp.

[B,VdC,McK] Brinkman G., Van den Camp H., McKay B.;
https://users.cecs.anu.edu.au/bdm/plantri/

[B] Birkhoff, G. D.; A Determinant Formula for the Number of Ways of coloring a Map, Ann. Math., vol 14, pp 42-46, 1912.

[G] Gonthier, G.; Formal Proof - The Four Color Theorem, Notices of the AMS, December 2008, 1382-1393.

[H] Heawood P. J.; On the Four-Color Map Theorem, Quart. J. Math. vol 29, pp 270-285, 1898.

[RSST] Robertson, S.; Sanders, D.; Seymour P.; Thomas R.; The four-color theorem, J. Combinatorial Theory, Series B 70 (1997), 2-44.

[S-K] Th. L. Saaty and P. C. Kainen; The Four-Color Problem, Assaults and Conquest, McGraw-Hill International Book Company. IX, 217 p., 1977.

[W] H. Whitney; A theorem on graphs, Annals of Maths 32, 2, pp 378-390, 1931.