Frucht graph

In graph theory, the Frucht graph is a cubic graph with 12 vertices, 18 edges, and no nontrivial symmetries.^[1] It was first described by Robert Frucht in 1949.^[2]

Frucht graph
The Frucht graph
Named after	Robert Frucht
Vertices	12
Edges	18
Radius	3
Diameter	4
Girth	3
Automorphisms	identity
Chromatic number	3
Chromatic index	3
Properties	Cubic Halin Pancyclic
Table of graphs and parameters

The Frucht graph can be constructed from the LCF notation: [−5,−2,−4,2,5,−2,2,5,−2,−5,4,2]. This describes it as a cubic graph in which two of the three adjacencies of each vertex form part of a Hamiltonian cycle and the numbers specify how far along the cycle to find the third neighbor of each vertex.^[3]

Properties

The Frucht graph is a cubic graph, because three vertices are incident to every vertex, thereby the degree of every vertex is 3. It is one of the five smallest cubic graphs possessing only a single graph automorphism, the identity: every vertex can be distinguished topologically from every other vertex.^[4] Such graphs are called asymmetric (or identity) graphs. Frucht's theorem states that any finite group can be realized as the group of symmetries of a graph,^[5] and a strengthening of this theorem, also due to Frucht, states that any finite group can be realized as the symmetries of a 3-regular graph.^[2] The Frucht graph provides an example of this strengthened realization for the trivial group.

Frucht graph as a convex polyhedron

The Frucht graph is a Halin graph, a type of planar graph formed from a tree with no degree-two vertices by adding a cycle connecting its leaves.^[1] Every Halin graph is 3-vertex-connected: deleting two of its vertices cannot disconnect it. By Steinitz's theorem, the Frucht graph is hence polyhedral, meaning its 12 vertices and 18 edges form the skeleton of a convex polyhedron.^[6] It is also Hamiltonian.

It is pancyclic,^[7] with chromatic number 3, chromatic index 3, radius 3, and diameter 4. Its girth 3. Its independence number is 5.

The characteristic polynomial of the Frucht graph is ${\displaystyle (x-3)(x-2)x(x+1)(x+2)(x^{3}+x^{2}-2x-1)(x^{4}+x^{3}-6x^{2}-5x+4)}$.

Gallery

• 
  The chromatic number of the Frucht graph is 3.
• 
  The Frucht graph is Hamiltonian.