In the
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, the Dürer graph is an
undirected graph
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
with 12 vertices and 18 edges. It is named after
Albrecht Dürer
Albrecht Dürer ( , ;; 21 May 1471 – 6 April 1528),Müller, Peter O. (1993) ''Substantiv-Derivation in Den Schriften Albrecht Dürers'', Walter de Gruyter. . sometimes spelled in English as Durer or Duerer, was a German painter, Old master prin ...
, whose 1514
engraving
Engraving is the practice of incising a design on a hard, usually flat surface by cutting grooves into it with a Burin (engraving), burin. The result may be a decorated object in itself, as when silver, gold, steel, or Glass engraving, glass ar ...
''
Melencolia I
''Melencolia I'' is a large 1514 engraving by the German Renaissance artist Albrecht Dürer. Its central subject is an enigmatic and gloomy winged female figure thought to be a personification of melancholia – melancholy. Holding her head in ...
'' includes a depiction of
Dürer's solid, a
convex polyhedron
In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal faces, straight edges and sharp corners or vertices. The term "polyhedron" may refer either to a solid figure or to its boundary su ...
having the Dürer graph as its
skeleton
A skeleton is the structural frame that supports the body of most animals. There are several types of skeletons, including the exoskeleton, which is a rigid outer shell that holds up an organism's shape; the endoskeleton, a rigid internal fra ...
. Dürer's solid is one of only four
well-covered simple
Simple or SIMPLE may refer to:
*Simplicity, the state or quality of being simple
Arts and entertainment
* ''Simple'' (album), by Andy Yorke, 2008, and its title track
* "Simple" (Florida Georgia Line song), 2018
* "Simple", a song by John ...
convex polyhedra.
Dürer's solid
Dürer's solid is combinatorially equivalent to a
cube
A cube or regular hexahedron is a three-dimensional space, three-dimensional solid object in geometry, which is bounded by six congruent square (geometry), square faces, a type of polyhedron. It has twelve congruent edges and eight vertices. It i ...
with two opposite vertices
truncated, although Dürer's depiction of it is not in this form but rather as a truncated
rhombohedron
In geometry, a rhombohedron (also called a rhombic hexahedron or, inaccurately, a rhomboid) is a special case of a parallelepiped in which all six faces are congruent rhombi. It can be used to define the rhombohedral lattice system, a honeycomb w ...
or
truncated triangular trapezohedron
In geometry, the truncated triangular trapezohedron is the first in an infinite series of truncated trapezohedra. It has 6 pentagon and 2 triangle faces.
Geometry
This polyhedron can be constructed by truncating two opposite vertices of a cu ...
. The exact geometry of the solid depicted by Dürer is a subject of some academic debate, with different hypothetical values for its
acute angle
In Euclidean geometry, an angle can refer to a number of concepts relating to the intersection of two straight lines at a point. Formally, an angle is a figure lying in a plane formed by two rays, called the '' sides'' of the angle, sharing ...
s ranging from 72° to 82°.
Graph-theoretic properties
The Dürer graph is the graph formed by the vertices and edges of the Dürer solid. It 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 bip ...
of
girth
Girth may refer to:
Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
3 and
diameter
In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...
4. As well as its construction as the skeleton of Dürer's solid, it can be obtained by applying a
Y-Δ transform to the opposite vertices of a
cube graph
In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube.
has vertices, ...
, or as the
generalized Petersen graph
In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways o ...
''G''(6,2). As with any
graph of a convex polyhedron, the Dürer graph is a
3-vertex-connected simple
planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
.
The Dürer graph is a
well-covered graph
In graph theory, a well-covered graph is an undirected graph in which the minimal vertex covers all have the same size. Here, a vertex cover is a set of vertices that touches all edges, and it is minimal element, minimal if removing any vertex fr ...
, meaning that all of its
maximal independent set
In graph theory, a maximal independent set (MIS) or maximal stable set is an Independent set (graph theory), independent set that is not a subset of any other independent set. In other words, there is no Vertex (graph theory), vertex outside th ...
s have the same number of vertices, four. It is one of four well-covered cubic polyhedral graphs and one of seven well-covered cubic graphs. The only other three well-covered
simple
Simple or SIMPLE may refer to:
*Simplicity, the state or quality of being simple
Arts and entertainment
* ''Simple'' (album), by Andy Yorke, 2008, and its title track
* "Simple" (Florida Georgia Line song), 2018
* "Simple", a song by John ...
convex polyhedra are the
tetrahedron
In geometry, a tetrahedron (: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular Face (geometry), faces, six straight Edge (geometry), edges, and four vertex (geometry), vertices. The tet ...
,
triangular prism
In geometry, a triangular prism or trigonal prism is a Prism (geometry), prism with 2 triangular bases. If the edges pair with each triangle's vertex and if they are perpendicular to the base, it is a ''right triangular prism''. A right triangul ...
, and
pentagonal prism
In geometry, the pentagonal prism is a prism with a pentagonal base. It is a type of heptahedron with seven faces, fifteen edges, and ten vertices. As a semiregular (or uniform) polyhedron
If faces are all regular, the pentagonal prism is ...
.
The Dürer graph is
Hamiltonian
Hamiltonian may refer to:
* Hamiltonian mechanics, a function that represents the total energy of a system
* Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system
** Dyall Hamiltonian, a modified Hamiltonian ...
, with
LCF notation
In the mathematical field of graph theory, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by Harold Scott MacDonald Coxeter, H. S. M. Coxeter and Robert Frucht, for the representation of cubic graphs that contain ...
��4, 5, 2, −4, −2, 5; −[ attribute the proof of Hamiltonicity of a class of generalized Petersen graphs that includes the Dürer graph to a 1968 Ph.D. thesis of G. N. Robertson at the University of Waterloo.] More precisely, it has exactly six Hamiltonian cycles, each pair of which may be mapped into each other by a
symmetry
Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is Invariant (mathematics), invariant und ...
of the graph.
Symmetries
The
automorphism group
In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...
both of the Dürer graph and of the Dürer solid (in either the truncated cube form or the form shown by Dürer) is
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
to the
dihedral group
In mathematics, a dihedral group is the group (mathematics), group of symmetry, symmetries of a regular polygon, which includes rotational symmetry, rotations and reflection symmetry, reflections. Dihedral groups are among the simplest example ...
of
order
Order, ORDER or Orders may refer to:
* A socio-political or established or existing order, e.g. World order, Ancien Regime, Pax Britannica
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
...
12, denoted D
6.
Gallery
Image:Dürer graph 3color edge.svg, The chromatic index of the Dürer graph is 3.
Image:Dürer_graph_3COL.svg, The chromatic number of the Dürer graph is 3.
File:Dürer graph hamiltonicity.svg, The Dürer graph is Hamiltonian
Hamiltonian may refer to:
* Hamiltonian mechanics, a function that represents the total energy of a system
* Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system
** Dyall Hamiltonian, a modified Hamiltonian ...
.
Notes
References
*.
*.
*.
*
*.
*. As cited by .
*.
{{DEFAULTSORT:Durer Graph
Individual graphs
Polyhedra
Regular graphs
Planar graphs