◀ ▲ ▶Branches / Graph-theory / Theorem: Four Color Theorem for Planar Graphs With a Dual Hamiltonian Graph

The proof of the four color theorem for planar graphs found in 1976 was computer-assisted. Due to its complexity, it cannot be directly verified by humans. Only the validity of the proving computer algorithm can be verified. This is a highly unsatisfactory situation for mathematicians. In fact, some mathematicians do not accept computer-assisted proofs as mathematical proofs.

The following theorem is a direct implication of the characterization of planar hamiltonian graphs proved by me in 2014. To my knowledge (as of 2020) it is also one of only a few strict proofs of a special instance of the 4-color theorem, which can be verified by humans.

Theorem: Four Color Theorem for Planar Graphs With a Dual Hamiltonian Graph

Let $G$ be a simple, connected, planar graph. If the dual graph $G^*$ is Hamiltonian, then the chromatic number of $G$ obeys the following inequality $$\chi(G)\le 4.$$

Notes

• This is a solution of the 4-color conjecture for special kinds of maps, in which the country borders allow a circular tour without visiting a border edge twice (i.e. a point at a border, at which more than two countries meet each other). In this case, the faces of $G ^*$ and the vertices of $G$ correspond to the countries and the edges of $G^*$ are the country borders.
• In other words, the faces in a planar drawing of a Hamiltonian graph $G^*$ can be colored with at most 4 colors.

Table of Contents

Proofs: 1

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Piotrowski, Andreas: Own Research, 2014