Up

Heawood graph

Percy John Heawood (1861-1955) was an English mathematician who spent a large amount of time on questions related to the four colour theorem.

There is a unique distance-regular graph Γ with intersection array {3,2,2;1,1,3}. It has 14 vertices and spectrum 31 (√2)6 (–√2)6 (–3)1. It is the point-line incidence graph of the Fano plane, and is commonly called the Heawood graph. It occurs as subgraph of the Hoffman-Singleton graph.

It is the unique (3,6)-cage: the regular cubic graph of girth 6 with minimal number of vertices.

co-Heawood graph

The point-line nonincidence graph of the Fano plane is the distance-3 graph of the above, and is distance-regular with intersection array {4,3,2,1,2,4}. It is sometimes called the co-Heawood graph. It occurs as subgraph of the Gewirtz graph, and is the first subconstituent of the U3(3) graph.

Group

The full group of automorphisms is PGL(2,7) = L3(2).2, acting distance-transitively with point stabilizer S4.

Subgraphs

Substructures belonging to the maximal subgroups of the automorphism group:

a) A partition of the edges into three matchings. There are 8 of these, forming a single orbit. The stabilizer of one is 7:6, with vertex orbit size 14. (There are 24 matchings. The complement of a matching is a 14-cycle that decomposes uniquely into two matchings. So, matchings come in groups of three.)

b) A vertex. There are 14 of these, forming a single orbit. The stabilizer of one is S4, with vertex orbit sizes 1+3+6+4.

c) An edge. There are 21 of these, forming a single orbit. The stabilizer of one is D16, with vertex orbit sizes 2+4+8. These correspond to the flags of the Fano plane.

d) A crossing non-edge. (The graph is bipartite; a crossing non-edge is a non-edge meeting both sides of the bipartition.) There are 28 of these, forming a single orbit. The stabilizer of one is D12, with vertex orbit sizes 2+6+6. These correspond to the antiflags of the Fano plane. The graph on the crossing non-edges, adjacent when their union is a 4-coclique, is the Coxeter graph.

Map

Heawood proved the 7-color theorem for the torus. This graph has an embedding on the torus with 7 areas that are mutually adjacent, showing that 7 is best possible.

References

P.J. Heawood, Map-colour theorem, Quart. J. Math. Oxford Ser. 24 (1890) 332-338.