Skip to main content
2 of 3
added 4 characters in body; edited title
Yiftach Barnea
  • 5.5k
  • 2
  • 38
  • 53

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)=n/2$, 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$.)

Yiftach Barnea
  • 5.5k
  • 2
  • 38
  • 53