4
$\begingroup$

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.

  • 0
    @JeffE Of course you're right. I corrected the question.2012-05-13

1 Answers 1

5

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.

Not transitive

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.

  • 1
    yes, there are no 4-cycles which aren't 4-faces in this planar graph though since every edge lies in exactly one triangle2012-05-15