Talk:Vertex-transitive graph

From Wikipedia, the free encyclopedia

it would be nice to have an example of a regular graph that is not vertex-transitive, however, I don't know any. Evilbu 20:43, 14 February 2006 (UTC)

This is precisely what I came here looking for!! there are semisymmetric examples at mathworld, but these are edge transitive. Should be able to find a non-vertex-transitive regular graph with fewer than 20 vertices!MotherFunctor

The (connected) counterexample with the least number of vertices is an order-7 quartic graph. Consider the graph consisting of a disjoint 3-cycle and 4-cycle. Its complement graph is the desired example. This graph is not planar, having crossing number 2. The smallest planar example is an order-8 cubic graph, so has fewer edges than the first one. I don't know how this stuff can be worked into the article, because it's original research. Ntsimp (talk) 21:36, 16 February 2008 (UTC)