In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the Frucht graph is a
cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.
A bicubic graph is a cubic bipa ...
with 12
vertices, 18 edges, and no nontrivial
symmetries
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...
. It was first described by
Robert Frucht in 1939.
The Frucht graph is a
pancyclic,
Halin graph with
chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
3,
chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
3, radius 3, and diameter 4. Like every Halin graph, the Frucht graph is
polyhedral (
planar and
3-vertex-connected) and
Hamiltonian, with
girth 3. Its
independence number
Independence is a condition of a person, nation, country, or Sovereign state, state in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independ ...
is 5.
The Frucht graph can be constructed from the
LCF notation: .
Algebraic properties
The Frucht graph is one of the five smallest
cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.
A bicubic graph is a cubic bipa ...
s possessing only a single
graph automorphism
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.
Formally, an automorphism of a graph is a permutation of the ...
, the identity (that is, every vertex can be distinguished topologically from every other vertex). Such graphs are called
asymmetric
Asymmetric may refer to:
*Asymmetry in geometry, chemistry, and physics
Computing
* Asymmetric cryptography, in public-key cryptography
*Asymmetric digital subscriber line, Internet connectivity
* Asymmetric multiprocessing, in computer architect ...
(or identity) graphs.
Frucht's theorem states that any
group can be realized as the group of symmetries of a graph,
[.] and a strengthening of this theorem also due to Frucht states that any group can be realized as the symmetries of a 3-regular graph;
[.] the Frucht graph provides an example of this realization for the
trivial group
In mathematics, a trivial group or zero group is a group consisting of a single element. All such groups are isomorphic, so one often speaks of the trivial group. The single element of the trivial group is the identity element and so it is usual ...
.
The
characteristic polynomial
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...
of the Frucht graph is
.
Gallery
File:Frucht_graph_3COL.svg, The chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
of the Frucht graph is 3.
File:Frucht Lombardi.svg, The Frucht graph is Hamiltonian.
See also
References
{{reflist
Individual graphs
Regular graphs
Planar graphs