Frucht graph
Cubic graph with 12 vertices and 18 edges
title: "Frucht graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["individual-graphs", "regular-graphs", "planar-graphs"] description: "Cubic graph with 12 vertices and 18 edges" topic_path: "general/individual-graphs" source: "https://en.wikipedia.org/wiki/Frucht_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary Cubic graph with 12 vertices and 18 edges ::
::data[format=table title="infobox graph"]
| Field | Value |
|---|---|
| name | Frucht graph |
| image | [[File:Frucht planar Lombardi.svg |
| image_caption | The Frucht graph |
| namesake | Robert Frucht |
| vertices | 12 |
| edges | 18 |
| automorphisms | identity |
| girth | 3 |
| radius | 3 |
| diameter | 4 |
| chromatic_number | 3 |
| chromatic_index | 3 |
| properties | Cubic |
| Halin | |
| Pancyclic | |
| :: |
| name = Frucht graph | image = [[File:Frucht planar Lombardi.svg|200px]] | image_caption = The Frucht graph | namesake = Robert Frucht | vertices = 12 | edges = 18 | automorphisms = identity | girth = 3 | radius = 3 | diameter = 4 | chromatic_number = 3 | chromatic_index = 3 | properties = Cubic Halin Pancyclic
In graph theory, the Frucht graph is a cubic graph with 12 vertices, 18 edges, and no nontrivial symmetries.{{citation | last1 = Ali | first1 = Akbar | last2 = Chartrand | first2 = Gary | last3 = Zhang | first3 = Ping | title = Irregularity in Graphs | year = 2021 | publisher = Springer | url = https://books.google.com/books?id=bZEvEAAAQBAJ&pg=PA25 | pages = 24–25 | doi = 10.1007/978-3-030-67993-4 | isbn = 978-3-030-67993-4
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.
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.{{citation | last1 = Bussemaker | first1 = F. C. | last2 = Cobeljic | first2 = S. | last3 = Cvetkovic | first3 = D. M. | last4 = Seidel | first4 = J. J. | publisher = Department of Mathematics and Computing Science, Eindhoven University of Technology | series = EUT report | title = Computer investigation of cubic graphs | url = https://research.tue.nl/en/publications/computer-investigation-of-cubic-graphs | volume = 76-WSK-01 | year = 1976 | last1 = Frucht | first1 = R. | title = Herstellung von Graphen mit vorgegebener abstrakter Gruppe. | url = http://www.numdam.org/item?id=CM_1939__6__239_0 | language = German | zbl = 0020.07804 | year = 1939 | journal = Compositio Mathematica | issn = 0010-437X | volume = 6 | pages = 239–250 | last1 = Frucht | first1 = R. | title = Graphs of degree three with a given abstract group | doi = 10.4153/CJM-1949-033-6 | mr = 0032987 | year = 1949 | journal = Canadian Journal of Mathematics | issn = 0008-414X | volume = 1 | issue = 4 | pages = 365–378 | s2cid = 124723321 | doi-access = free
::figure[src="https://upload.wikimedia.org/wikipedia/commons/3/34/Frucht_graph_as_a_convex_polyhedron.svg" caption="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. It is also Hamiltonian.
It is pancyclic,{{citation | last = Parrochia | first = Daniel | title = Mathematics and Philosophy 2: Graphs, Orders, Infinites and Philosophy | year = 2023 | publisher = John & Wiley, ISTE Ltd. | url = https://books.google.com/books?id=T8W1EAAAQBAJ&pg=PA18 | page = 18 | isbn = 978-1-78630-897-9
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).
Gallery
File:Frucht_graph_3COL.svg|The chromatic number of the Frucht graph is 3. File:Frucht Lombardi.svg| The Frucht graph is Hamiltonian.
References
References
- "Frucht Graph".
- "Halin Graph".
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::