About stefanutti

V: "Do you know me?" S: "yes." V: "No you don't." S: "Okay." V: "Did you see my picture in the paper?" S: "Yes." V: "No you didn't." S: "I don't even get the paper."

Let’s leave the beach: pentagonal regions and the Four Color Theorem (2/2)

Posted on March 17, 2026 by stefanutti

Case F5-F5

By removing an edge between two F5 faces, you obtain an F6 face. The two adjacent faces that shared the removed vertices each lose one edge. If the two adjacent faces are actually the same face, the number of edges decreases by two.

General case F5-Fn

By removing an edge between an F5 face and a Fn face, you obtain an F(n+1) face. The two adjacent faces that shared the removed vertices each lose one edge. If the two adjacent faces are actually the same face, the number of edges decreases by two.

The problem is that maps on the sphere can exist:

for sure, without adjacent F5-F5 faces, as in C60 Fullerene and other structures
theoretically, without adjacent F5-F6 faces, as established in “An Eberhard-like theorem for pentagons and heptagons” by Matt DeVos, Agelos Georgakopoulos, Bojan Mohar, Robert Šámal
- Also check the “Zur morphologie der polyeder” by DR. V. EBERHARD

Let’s go to the beach: pentagonal regions and the Four Color Theorem

Posted on March 12, 2026 by stefanutti

I need relax. Let’s go to the beach!

Personal note: I don’t know where I am headed, so don’t follow me. I am just wandering around and taking notes.

Suppose that there exist maps that are not four-colorable, perhaps only one, perhaps a few, or even infinitely many.

Now, remove from this set all maps that have regions with 2, 3, or 4 borders. For the scope of the four color theorem and without lack of generality, we can skip them. 🤞🏻 I am confident it is true, but not completely sure I can do this passage. Or at least it should be proved.

Now select a pentagonal region and regard it as the outer boundary: the ocean that surrounds all other lands.

And now walk along the shoreline.

What can we say about the five regions that face the ocean?

Can one of them be always an F5?

The answer is no, not always. Fullerene graphs show that it is possible for all F5 faces to be isolated, with no two pentagons sharing an edge. The standard example is the Buckminsterfullerene. Or, more commonly a soccer ball.

Can one of them be always an F6?

Euler’s formula neither guarantees nor rules out this possibility.

1 F5 – 0 F6 – 1 F7 – 2 F8 – 3 F9 – … = 12

👉 I don’t know if there are studies done to analyze these maps. F5 always surrounded by F7 or higher.

To be continued …

Remove an edge between F5-F5, or F5-F6 or 😦 F5-F7+
Analyze all combinations of colors along the new shoreline of the reduced maps
And search for a contradiction to the hypothesis that there exist maps that cannot be colored with four colors

Four colored fullerenes

Posted on February 25, 2026 by stefanutti

Download all 15 colored fullerenes taken from here: https://networks.skewed.de/net/fullerene_structures

The Tait three colored edges of the graph is equivalent to the four colored faces of the same graph.

This is an example for the C2940 Fullerene.

15-fullerenes Download

See you!

C6000 Fullerene: a playground for the Four Color Theorem coloring algorithm

Posted on February 24, 2026 by stefanutti

On this great website https://networks.skewed.de/net/fullerene_structures, you can view and download fullerene structures in various formats.

Fullerenes are a perfect playground to test my four color algorithm.

I used the C6000 fullerene. 6000 atoms! A fullerene is an allotrope of carbon. Its molecules consist of carbon atoms connected by single and double bonds. A perfect 3-regular planar graphs ready to be tested.

And this is the four colored version you can play with, created using:

# python3 4ct.py -p planar_inputs/C6000.planar -c 2354 -o C6000

Actually, it is the Tait edge three colored version of the graph. This is equivalent to the four colored version of the faces.

This zip file includes the C6000.dot + C6000.edgelist files.

C6000.zip Download

See you around!

Boosting performance: Sage to Python/Networkx transition

Posted on February 10, 2026 by stefanutti

I converted the Sage implementation to a pure Python / Networkx solution.

sage 4ct.py -r 2000

python3 4ct_without_sage.py -r 2000

	Sage	Python3 + Networkx
Random graph creation	17 min 59 s * RandomTriangulation	22 s * Custom
Planar embedding	16 min 09 s * dual + set_embedding=True	0 s * Not necessary
Elaboration	2 min 12 s	1 min 58 s

Here is the file:

bye_bye_sage_from_100_to_23_secs_2000_nodes.dot Download

Other run:

sage 4ct.py -r 1000

python3 4ct_without_sage.py -r 1000

	Sage	Python3 + Networkx
Random graph creation	3 min 19 s	6 s
Planar embedding	2 min 44 s	0 s
Elaboration	14 s	23 s

Optimizing Graph Coloring with Reinforcement Learning

Posted on January 6, 2025 by stefanutti

This is what I will be working for a while. Restart is difficult, but necessary.

Why use Reinforcement Learning for Graph coloring?

In my Python application, that works on 3-regular planar graph, deciding which is the order of the edges to remove can be non-trivial. A naive approach randomly picks edges from F2 faces, F3, F4 or F5. This is the approach I used :-(. It leads to impasses when rebuilding the map. See https://4coloring.wordpress.com/2014/08/27/four-color-theorem-experimenting-impasses-as-in-life/

But a reinforcement learning agent can learn to make better selections over time to reduce color conflicts, I hope :-), and shed light on some properties of the graph that can be used in the proof.

The code will be here: https://github.com/stefanutti/maps-coloring-python

Remove one edge at a time from F2, F3, F4, or F5 faces. These faces represent the basic unavoidable set. This process will reduce the map to three faces, including the ocean as the external area. Afterward, I will restore the edges in reverse order, consistently working with 3-regular planar graphs. I will consider Tait coloring of the edges and apply, when necessary, Kempe’s chain color switching to the edges.

For the Agent:

Environment initialization = The starting uncolored 3-regular planar graphs
Action = Select the edge to remove from the 3-regular planar graphs
State = The updated 3-regular planar graphs
Reward = +1 if Random Kempe’s chain color switching was not necessary, -1 otherwise

Color Voronoi graphs

Posted on September 4, 2022 by stefanutti

To color Voronoi graphs using the algorithm here https://github.com/stefanutti/maps-coloring-python, it is necessary to do some adjustments first:

Transform it into a 3-regular graph, by adding a frame and modifying the vertices with more than 3 edges, as shown below
Consider the surrounding area (out of the frame) as part of the map (the ocean) and color also that

It is known that we can also suppose that exactly three edges meet at each vertex since maps that have vertexes with more than three edges can be easily simplified without affecting the search of the coloring. In other words, if you can find a coloring for the map on the right, you can use the same coloring for the original map on the left.

Here is an example of these steps applied to the following Voronoi diagram. Three vertices have a degree greater than three.

3-regular planar graph decomposition in cycles and 4CT

Posted on August 24, 2022 by stefanutti

If you can prove that it is possible to decompose a 3-regular graph into cycles, all with even length, you have also proved the four color theorem.

I think this fact is already known, but I never paid too much attention to it before.

Naturally, also the opposite is true: since the 4CT is true, it means that it is possible to color it, and also get the Tait coloring. And for any two colors you choose (for example Red and Green), the related Kempe cycles form a partition of the graph and each cycle has an even number of edges.

Once the decomposition is found, since the cycles have an even number of edges, it is possible to color the edges of a cycle with two alternate colors (for example Red and Green), forming this way Kempe cycles. When all cycles are colored (with R and G), it is possible to use a third color (for example Blue) to color the remaining edges.

The resulting graph will have a Tait coloring for all edges, which is equivalent to coloring all faces with four different colors.

But, how difficult is it to find all cycles?

This one has 6 Red-Green cycles (all of even length), that form a division on the 3-regular planar graph into cycles.

4CT and loops, cycles, circuits, chains, paths

Posted on August 23, 2022 by stefanutti

I realized that for some posts I may have used “Kempe loops” and “Kempe cycles” to describe closed “Kempe chains”, that in other words form closed paths (cycles). I think it would have been better always to use “Kempe cycles”.

https://en.wikipedia.org/wiki/Loop_(graph_theory)

https://en.wikipedia.org/wiki/Path_(graph_theory)

https://en.wikipedia.org/wiki/Hamiltonian_path

Non-Hamiltonian 3-regular planar graphs, Tait coloring and Kempe cycles … what else ;-)

Posted on August 22, 2022 by stefanutti

Considering the smallest known non-Hamiltonian 3-regular planar graphs, discovered by Barnette-Bosák-Lederberg, I computed the Tait coloring and then deformed it to put in evidence the R-G cycles that in this case are four.

Links to the historical importance of this graph:

https://mathworld.wolfram.com/Barnette-Bosak-LederbergGraph.html

https://en.wikipedia.org/wiki/Barnette–Bosák–Lederberg graph