In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 field of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the Dürer graph is an undirected graph with 12 vertices and 18 edges. It is named after Albrecht Dürer

Albrecht Dürer

Albrecht Dürer was a German painter, printmaker, engraver, mathematician, and theorist from Nuremberg. His prints established his reputation across Europe when he was still in his twenties, and he has been conventionally regarded as the greatest artist of the Northern Renaissance ever since...

, whose 1514 engraving

Engraving

Engraving is the practice of incising a design on to a hard, usually flat surface, by cutting grooves into it. The result may be a decorated object in itself, as when silver, gold, steel, or glass are engraved, or may provide an intaglio printing plate, of copper or another metal, for printing...

 Melencolia I

Melencolia I

Melencolia I is a 1514 engraving by the German Renaissance master Albrecht Dürer. It is an allegorical composition which has been the subject of many interpretations...

includes a depiction of Dürer's solid, a convex polyhedron having the Dürer graph as its skeleton. Dürer's solid is one of only four well-covered

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. Well-covered graphs were defined and first studied by .-Definitions:...

 simple

Simple polytope

In geometry, a d-dimensional simple polytope is a d-dimensional polytope each of whose vertices are adjacent to exactly d edges . The vertex figure of a simple d-polytope is a -simplex....

 convex polyhedra.

Dürer's solid

Dürer's solid is combinatorially equivalent to a cube

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. The cube can also be called a regular hexahedron and is one of the five Platonic solids. It is a special kind of square prism, of rectangular parallelepiped and...

 with two opposite vertices truncated

Truncation (geometry)

In geometry, a truncation is an operation in any dimension that cuts polytope vertices, creating a new facet in place of each vertex.- Uniform truncation :...

, although Dürer's depiction of it is not in this form but rather as a truncated rhombohedron

Rhombohedron

In geometry, a rhombohedron is a three-dimensional figure like a cube, except that its faces are not squares but rhombi. It is a special case of a parallelepiped where all edges are the same length....

. The exact geometry of the solid depicted by Dürer is a subject of some academic debate. claims that the rhombi of the rhombohedron from which this shape is formed have 5:6 as the ratio between their short and long diagonals, from which the acute angles of the rhombi would be approximately 80°. and instead conclude that the ratio is √3:2 and that the angle is approximately 82°. measures features of the drawing and finds that the angle is approximately 79°. argues based on the writings of Dürer that all vertices of Dürer's solid lie on a common sphere, and further claims that the rhombus angles are 72°. analyzes a 1510 sketch by Dürer of the same solid, from which he confirms Schrieber's hypothesis that the shape has a circumsphere but with rhombus angles of approximately 79.5°.

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

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

 of 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 to the opposite vertices of a cube graph, or as the generalized Petersen graph

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 of constructing the Petersen graph. The generalized...

 G(6,2). As with any graph of a convex polyhedron

Polyhedral graph

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...

, the Dürer graph is a 3-vertex-connected

K-vertex-connected graph

In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...

 simple planar graph

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

.

The Dürer graph is a well-covered graph

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. Well-covered graphs were defined and first studied by .-Definitions:...

, meaning that all of its maximal independent set

Maximal independent set

In graph theory, a maximal independent set or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S...

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 simple

Simple polytope

In geometry, a d-dimensional simple polytope is a d-dimensional polytope each of whose vertices are adjacent to exactly d edges . The vertex figure of a simple d-polytope is a -simplex....

 convex polyhedra are the tetrahedron

Tetrahedron

In geometry, a tetrahedron is a polyhedron composed of four triangular faces, three of which meet at each vertex. A regular tetrahedron is one in which the four triangles are regular, or "equilateral", and is one of the Platonic solids...

, triangular prism

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

, and pentagonal prism

Pentagonal prism

In geometry, the pentagonal prism is a prism with a pentagonal base. It is a type of heptahedron with 7 faces, 15 edges, and 10 vertices.- As a semiregular polyhedron :...

.

The Dürer graph is Hamiltonian

Hamiltonian path

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex...

, with LCF notation

LCF notation

In combinatorial mathematics, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by Coxeter and Frucht, for the representation of cubic graphs that are Hamiltonian. Since the graphs are Hamiltonian, the vertices can be arranged in a cycle, which accounts for two edges...

 [-4,5,2,-4,-2,5;-]. 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 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

Dihedral group

In mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.See also: Dihedral symmetry in three...

of order 12 : D₆.