Up

# (0,2)-graphs

A (0,2)-graph is a graph such that every two vertices have 0 or 2 common neighbours. Obvious (0,2)-graphs are K2 and K4 and the icosahedron and the incidence graph of the 2-(7,4,2) biplane. This page describes a (0,2)-graph on 20 vertices related to the dodecahedron.

There is a unique (0,2)-graph on 20 vertices such that all local graphs are K3+3K1. It has full group Alt(5) acting vertex-transitively, and distance distribution 1+6+12+1 around each point. Interchanging antipodes is not an automorphism.

## Construction

a) Let the vertices be the ordered pairs ij of distinct elements from the 5-set {1,2,3,4,5}, where ij~ik whenever i,j,k are distinct, and ij~kl when i,j,k,l are distinct, so that {1,2,3,4,5} = {i,j,k,l,m} for some m, and the permutation that maps 1,2,3,4,5 to i,j,k,l,m is an even permutation.

b) Equivalently, let the vertices be the 20 vertices of the dodecahedron. Choose a fixed partition of the dodecahedron into five tetrahedra. Now let two vertices be adjacent whenever they either lie in a common tetrahedron, or are joined by an edge of the dodecahedron.

## Discussion

Geometrically, the dodecahedron is a cubic graph on the sphere, and while following a path on the dodecahedron it makes sense to talk about turning left or turning right. Being at distance three and joined by a path of the form: step, turn left, step, turn right, step is a symmetric relation R of valency 3. Being adjacent in the dodecahedron is a symmetric relation S of valency 3. The union of R and S defines our graph.

There are two isomorphic ways of picking the tetrahedra (our way, and its mirror image), and thus the group Sym(5) of the dodecahedron is reduced to the Alt(5) of this graph.

In the representation with ordered pairs, the antipode of ij is ji. Now having the same first coordinate defines a 4-clique, but having the same second coordinate defines a 4-coclique, so interchanging antipodes is not an automorphism.