Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Heawood graph
In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.
The graph is cubic, and all cycles in the graph have six or more edges. Every smaller cubic graph has shorter cycles, so this graph is the 6-cage, the smallest cubic graph of girth 6. It is a distance-transitive graph (see the Foster census) and therefore distance regular.
There are 24 perfect matchings in the Heawood graph; for each matching, the set of edges not in the matching forms a Hamiltonian cycle. For instance, the figure shows the vertices of the graph placed on a cycle, with the internal diagonals of the cycle forming a matching. By subdividing the cycle edges into two matchings, we can partition the Heawood graph into three perfect matchings (that is, 3-color its edges) in eight different ways. Every two perfect matchings, and every two Hamiltonian cycles, can be transformed into each other by a symmetry of the graph.
There are 28 six-vertex cycles in the Heawood graph. Each 6-cycle is disjoint from exactly three other 6-cycles; among these three 6-cycles, each one is the symmetric difference of the other two. The graph with one node per 6-cycle, and one edge for each disjoint pair of 6-cycles, is the Coxeter graph.
The Heawood graph is a toroidal graph; that is, it can be embedded without crossings onto a torus. The result is the regular map {6,3}2,1, with 7 hexagonal faces. Each face of the map is adjacent to every other face, thus as a result coloring the map requires 7 colors. The map and graph were discovered by Percy John Heawood in 1890, who proved that no map on the torus could require more than seven colors and thus this map is maximal.
The map can be faithfully realized as the Szilassi polyhedron, the only known polyhedron apart from the tetrahedron such that every pair of faces is adjacent.
The Heawood graph is the Levi graph of the Fano plane, the graph representing incidences between points and lines in that geometry. With this interpretation, the 6-cycles in the Heawood graph correspond to triangles in the Fano plane. Also, the Heawood graph is the Tits building of the group SL3(F2).
The Heawood graph has crossing number 3, and is the smallest cubic graph with that crossing number (sequence A110507 in the OEIS). Including the Heawood graph, there are 8 distinct graphs of order 14 with crossing number 3.
Hub AI
Heawood graph AI simulator
(@Heawood graph_simulator)
Heawood graph
In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.
The graph is cubic, and all cycles in the graph have six or more edges. Every smaller cubic graph has shorter cycles, so this graph is the 6-cage, the smallest cubic graph of girth 6. It is a distance-transitive graph (see the Foster census) and therefore distance regular.
There are 24 perfect matchings in the Heawood graph; for each matching, the set of edges not in the matching forms a Hamiltonian cycle. For instance, the figure shows the vertices of the graph placed on a cycle, with the internal diagonals of the cycle forming a matching. By subdividing the cycle edges into two matchings, we can partition the Heawood graph into three perfect matchings (that is, 3-color its edges) in eight different ways. Every two perfect matchings, and every two Hamiltonian cycles, can be transformed into each other by a symmetry of the graph.
There are 28 six-vertex cycles in the Heawood graph. Each 6-cycle is disjoint from exactly three other 6-cycles; among these three 6-cycles, each one is the symmetric difference of the other two. The graph with one node per 6-cycle, and one edge for each disjoint pair of 6-cycles, is the Coxeter graph.
The Heawood graph is a toroidal graph; that is, it can be embedded without crossings onto a torus. The result is the regular map {6,3}2,1, with 7 hexagonal faces. Each face of the map is adjacent to every other face, thus as a result coloring the map requires 7 colors. The map and graph were discovered by Percy John Heawood in 1890, who proved that no map on the torus could require more than seven colors and thus this map is maximal.
The map can be faithfully realized as the Szilassi polyhedron, the only known polyhedron apart from the tetrahedron such that every pair of faces is adjacent.
The Heawood graph is the Levi graph of the Fano plane, the graph representing incidences between points and lines in that geometry. With this interpretation, the 6-cycles in the Heawood graph correspond to triangles in the Fano plane. Also, the Heawood graph is the Tits building of the group SL3(F2).
The Heawood graph has crossing number 3, and is the smallest cubic graph with that crossing number (sequence A110507 in the OEIS). Including the Heawood graph, there are 8 distinct graphs of order 14 with crossing number 3.