Franklin Graph

The Franklin graph is the 12-vertex cubic graph shown above whose embedding on the Klein bottle divides it into regions having a minimal coloring using six colors, thus providing the sole counterexample to the Heawood conjecture. The graph is implemented in the Wolfram Language as GraphData["FranklinGraph"].

It is the 6-crossed prism graph.

The minimal coloring of the Franklin graph is illustrated above.

The Franklin graph is nonplanar but Hamiltonian. It has LCF notations  and .

The graph spectrum of the Franklin graph is .

REFERENCES

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 244, 1976.

Franklin, P. "A Six Color Problem." J. Math. Phys. 13, 363-379, 1934.