Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.