TOPICS
Search

Franklin Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
FranklinGraph

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 isomorphic to the 6-crossed prism graph, Knödel graph W_(3,12), and honeycomb toroidal graph HTG(1,12,5).

FranklinGraphColoring

The minimal coloring of the Franklin graph is illustrated above.

The Franklin graph is nonplanar but Hamiltonian. It has LCF notations [5,-5]^6 and [-5,-3,3,5]^3.

The graph spectrum of the Franklin graph is (-3)^1(-sqrt(3))^2(-1)^31^3(sqrt(3))^23^1.

See also

Crossed Prism Graph, Cubic Graph, Heawood Conjecture, Honeycomb Toroidal Graph, Klein Bottle

Explore with Wolfram|Alpha

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.

Cite this as:

Weisstein, Eric W. "Franklin Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FranklinGraph.html

Subject classifications