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 conne ...

, the Dürer graph is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

with 12 vertices and 18 edges. It is named after

Albrecht Dürer Albrecht Dürer (; ; hu, Ajtósi Adalbert; 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 (without an umlaut) or Due ...

, whose 1514

engraving Engraving is the practice of incising a design onto 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 ...

Melencolia I ''Melencolia I'' is a large 1514 engraving by the German Renaissance artist Albrecht Dürer. The print's central subject is an enigmatic and gloomy winged female figure thought to be a personification of melancholia – melancholy. Holding he ...

'' includes a depiction of

Dürer's solid 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 Truncation (geometry), truncating two oppos ...

, a

convex polyhedron A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

having the Dürer graph as its

skeleton A skeleton is the structural frame that supports the body of an animal. There are several types of skeletons, including the exoskeleton, which is the stable outer shell of an organism, the endoskeleton, which forms the support structure inside ...

. 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 Johnn ...

convex polyhedra.

Dürer's solid

Dürer's solid is combinatorially equivalent to a

cube In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross. The cube is the only r ...

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 Traditionally, in two-dimensional geometry, a rhomboid is a parallelogram in which adjacent sides are of unequal lengths and angles are non-right ang ...

or triangular truncated trapezohedron. The exact geometry of the solid depicted by Dürer is a subject of some academic debate, with different hypothetical values for its acute angles 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 bipa ...

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 4. As well as its construction as the skeleton of Dürer's solid, it can be obtained by applying a

Y-Δ transform The Y-Δ transform, also written wye-delta and also known by many other names, is a mathematical technique to simplify the analysis of an electrical network. The name derives from the shapes of the circuit diagrams, which look respectively like th ...

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

''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 that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

. The Dürer graph is a

well-covered graph In graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Equivalently, these are the graphs in which all maximal independent sets have equal size. Well ...

, meaning that all of its

maximal independent set In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maxim ...

s have the same number of vertices, four. It is one of four well-covered cubic polyhedral graphs and one of seven well-covered 3-connected cubic graphs. The only other three well-covered

convex polyhedra are the

tetrahedron In geometry, a tetrahedron (plural: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all the o ...

triangular prism In geometry, a triangular prism is a three-sided prism; it is a polyhedron made of a triangular base, a translated copy, and 3 faces joining corresponding sides. A right triangular prism has rectangular sides, otherwise it is ''oblique''. A unif ...

, 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 H. S. M. Coxeter and Robert Frucht, for the representation of cubic graphs that contain a Hamiltonian cycle. The cycle ...

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 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 to the

dihedral group In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ge ...

of order 12 : D₆.

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

Notes

References

*. *. *. *. *. As cited by . *. {{DEFAULTSORT:Durer Graph Individual graphs Polyhedra Regular graphs Planar graphs