# Diameter of undirected, connected, vertex-transitive graph on $n$ vertices

I know very little about graphs. I believe the following should be trivial, but I couldn't find an argument to prove it. Let $\Gamma$ be an undirected, connected, vertex-transitive graph on $n$ vertices.

1. What is known about an upper bound for $d(\Gamma)$ the diameter of $\Gamma$? It seems that the worst case scenario is when $\Gamma$ is a cycle and then $d(\Gamma)=\lfloor n/2\rfloor$, is that true? What is known if it is not a cycle?

2. Is it true that any two vertices in $\Gamma$ can be connected by two non-intersecting paths, that is, any two vertices are contained in a cycle? (That will show of course that $d(\Gamma) \leq n/2$.)

The answer to the second question is yes. A vertex-transitive connected finite graph (with more than two vertices) is $2$-connected, i.e., it can't be disconnected by removing a vertex. In a $2$-connected graph every pair of vertices lies on a cycle; this is a special case of Menger's theorem.
• If $G$ can be disconnected by removing a vertex, then by vertex transitivity every vertex has that property. But any connected finite graph $G$ (with more than two vertices) has at least two vertices $u,v$ such that $G-u$ and $G-v$ are connected. Namely, choose $u$ and $v$ so that $d(u,v)=\operatorname{diam}(G).$ – bof Apr 26 '18 at 7:55
The cycle has the greatest diameter. Apart from the cycle, the greatest diameter is close to $n/4$. For example consider a circular ladder consisting of two cycles of length $n/2$ connected by $n/2$ rungs. Or, break that one at some place and join it again a twist (like a Möbius strip). And there are a few more cases too. The exact list of connected transitive graphs with largest diameter other than a cycle depends on $n\;\mathrm{mod}\; 4$.