Heawood family

In graph theory the term Heawood family refers to either one of the following two related graph families generated via ΔY- and YΔ-transformations:

the family of 20 graphs generated from the complete graph

K

7

{\displaystyle K_{7}}

.

the family of 78 graphs generated from

K

7

{\displaystyle K_{7}}

and

K

3

,

3

,

1

,

1

{\displaystyle K_{3,3,1,1}}

.

In either setting the members of the graph family are collectively known as Heawood graphs, as the Heawood graph is a member.

This is in analogy to the Petersen family, which too is named after its member the Petersen graph.

The Heawood families are significant in topological graph theory.

They contain the smallest known examples of intrinsically knotted graphs, of graphs that are not 4-flat, and of graphs with Colin de Verdière graph invariant

μ

=

6

{\displaystyle \mu =6}

.

The

K

7

{\displaystyle K_{7}}

-family

The

K

7

{\displaystyle K_{7}}

-family is generated from the complete graph

K

7

{\displaystyle K_{7}}

through repeated application of ΔY- and YΔ-transformations.

The family consists of 20 graphs, all of which have 21 edges.

The unique smallest member,

K

7

{\displaystyle K_{7}}

, has seven vertices.

The unique largest member, the Heawood graph, has 14 vertices.