# Is this a sufficient condition for vertex and edge transitivity?

I'm traying to prove (or disprove) the following statement:

Any connected $r$-regular graph of girth $g$ such that every edge is shared by the same number of minimum length cycles (that is, cycles of length $g$), is vertex-transitive and edge-transitive.

This is not a textbook exercise. Any ideas appreciated.

Thanks.

-
The statement is false if the graph can be disconnected. A connected (4,4)-graph can be constructed by drawing a grid on the torus. Consider the disjoint union of two such graphs with different numbers of vertices. – JeffE May 13 '12 at 16:13
@JeffE Of course you're right. I corrected the question. – becko May 13 '12 at 18:06

## 1 Answer

I believe it is also false for connected graphs.

For instance, if you take the pentagonal prism (it is vertex transitive but not edge transitive) you can then form a graph as follows: replace each vertex by a triangle then identify vertices which are joined by an edge.

This graph is 4-regular and of girth 3 and every edge is in exactly one triangle.

However it is not vertex or edge transitive; 10 vertices are part of 5-cycles without chords but 5 vertices aren't. Some edges lie in a 4-face and some don't.

-
Thanks. That disproves it. – becko May 15 '12 at 2:54
when you say "Some edges lie in a 4-face ...", you mean "... 4-cycle", right? – becko May 15 '12 at 2:55
yes, there are no 4-cycles which aren't 4-faces in this planar graph though since every edge lies in exactly one triangle – jp26 May 15 '12 at 10:01