A noncayley graph is a graph which is not a Cayley graph. All graphs that are not vertex-transitive are noncayley graphs. However, some vertex-transitive graph are noncayley. The numbers of vertex-transitive noncayley graphs on , 2, ... nodes are 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 4, 8, 0, 4, 0, 82, ... (OEIS A006792; McKay and Royle 1990, McKay and Praeger 1994), with the first nonzero case occurring at .
Royle maintains a list of non-Cayley graphs up to 31 vertices and although the values for 27, 28 and 30 vertices have not been independently verified (though an error in the groups can only affect the graphs if somehow a minimal transitive group has been omitted, so errors are unlikely).
A partial list of undirected vertex-transitive graphs that are not Cayley graphs is given in the following table, which extends Holton and Sheehan (1993, p. 292) and Scherphuis (and corrects Scherphuis by omitting the great rhombicuboctahedral graph, which is a Cayley graph).
10 | 5-triangular graph |
10 | Petersen graph |
15 | vertex-transitive graph |
15 | 6-triangular graph |
15 | -generalized quadrangle |
15 | quartic vertex-transitive graph Qt39 |
16 | quartic vertex-transitive graph Qt44 |
20 | 6-tetrahedral Johnson graph |
20 | Desargues graph |
20 | dodecahedral graph |
26 | -generalized Petersen graph |
28 | -Kneser graph |
28 | 8-triangular graph |
28 | Coxeter graph |
30 | -arrangement graph |
30 | cubic vertex-transitive graph Ct57 |
30 | cubic vertex-transitive graph Ct66 |
30 | icosidodecahedral graph |
30 | Tutte 8-cage |
30 | line graph of the icosahedral graph |
30 | -permutation star graph |
30 | Kronecker product of Petersen line graph complement and ones matrix |
84 | triangle-replaced Coxeter graph |
120 | great rhombicosidodecahedral graph |