From Surf Wiki (app.surf) — the open knowledge base

Frucht graph

Cubic graph with 12 vertices and 18 edges

Field	Value
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

Halin Pancyclic

In graph theory, the Frucht graph is a cubic graph with 12 vertices, 18 edges, and no nontrivial symmetries.{{citation

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 | doi-access = free

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

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

"Frucht Graph".
"Halin Graph".

Info: 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.

individual-graphs regular-graphs planar-graphs

Want to explore this topic further?

Ask Mako anything about Frucht graph — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report