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.
This page's graph
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.