Graphs

Here, we list a selection of famous graphs supported by "Free graph theory software". They occur as examples or counter examples in graph theory. When we give additional informations we refer to the corresponding articles in Wikipedia.

  • Bidiakis cube
  • Chvatal graph - "It is, as Chvatal observes, the smallest possible 4-chromatic 4-regular triangle-free graph."
  • Coxeter graph - A cubic distance-regular hypohamiltonian graph.
  • Dodecahedron graph - The graph of the dodecahedron, one of the five platonian solids.
  • Duerer graph
  • Errera graph - "... it provides an example of how Kempe's proof of the four color theorem cannot work."
  • Folkman graph - "It is the smallest undirected graph that is edge-transitive and regular, but not vertex-transitive."
  • Franklin graph - "The Franklin graph can be embedded onto the Klein bottle so that it forms a map requiring six colors ..."
  • Frucht graph - "The Frucht graph is one of the two smallest cubic graphs possessing only a single graph automorphism ..."
  • Goldner-Harary graph - "... the smallest non-Hamiltonian maximal planar graph."
  • Groetsch graph - "... its existence demonstrates that the assumption of planarity is necessary in Groetzsch's theorem (Groetzsch 1959) that every triangle-free planar graph is 3-colorable."
  • Heawood graph
  • Herschel graph - "... the smallest non-Hamiltonian polyhedral graph."
  • Icosahedron graph - The graph of the icosahedron, one of the five platonian solids.
  • Markstroem graph - "Markstroem's 24-vertex cubic planar graph with no 4- or 8-cycles ..."
  • Petersen graph - "... a useful example and counterexample for many problems in graph theory."
  • Tietze graph - "It and the Petersen graph are the only 2-vertex-connected cubic non-Hamiltonian graphs with 12 or fewer vertices."
  • Tutte graph - "The Tutte graph is a cubic polyhedral graph, but is non-hamiltonian. Therefore, it is a counterexample to the Tait's conjecture that every 3-regular polyhedron has a Hamiltonian cycle."