Frucht graph: Difference between revisions

Cubic graph with 12 vertices and 18 edges

In the mathematical field of 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]

The Frucht graph can be constructed from the LCF notation: [−5,−2,−4,2,5,−2,2,5,−2,−5,4,2].

The Frucht graph 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.^[3] 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,^[4] 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.

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

The Frucht graph is a Halin graph.^[1] It is pancyclic, with chromatic number 3, chromatic index 3, radius 3, and diameter 4. Like every Halin graph, the Frucht graph is polyhedral (planar and 3-vertex-connected)^[5] and Hamiltonian, with girth 3. Its independence number is 5.