Meredith Graph

The Meredith graph is a quartic nonhamiltonian graph on 70 nodes and 140 edges that is a counterexample to the conjecture that every 4-regular graph that is 4-connected is Hamiltonian.

It is implemented in the Wolfram Language as GraphData["MeredithGraph"].

The Meredith graph has chromatic number 3 and edge chromatic number 5.

The plots above show the adjacency matrix, incidence matrix, and graph distance matrix of the graph.

Explore with Wolfram|Alpha

More things to try:

References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 236-239, 1976.Bondy, J. A. and Murty, U. S. R. Graph Theory. Berlin, Germany: Springer-Verlag, p. 463, 2008.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, pp. 103-104, 1993.House of Graphs. "Meredith Graph." https://houseofgraphs.org/graphs/1225.Meredith, G. H. J. "Regular