Here's a non-regular one: Graph 1, order 9. 0 : 3 6 7; 1 : 4 6 8; 2 : 5 7 8; 3 : 0 6 7; 4 : 1 6 8; 5 : 2 7 8; 6 : 0 1 3 4; 7 : 0 2 3 5; 8 : 1 2 4 5; Now the list of pairwise distances 0 2 2 1 2 2 1 1 3 2 0 2 2 1 2 1 3 1 2 2 0 2 2 1 3 1 1 1 2 2 0 2 2 1 1 3 2 1 2 2 0 2 1 3 1 2 2 1 2 2 0 3 1 1 1 1 3 1 1 3 0 2 2 1 3 1 1 3 1 2 0 2 3 1 1 3 1 1 2 2 0