How to build a 4-regular, vertex-transitive, 'least diameter' graph with $v$ vertices?
This implies to know what is the minimum diameter of a 4-regular vertex-transitive graph with $v$ vertices.
What I found
If $v <= 4 + 1$, the diameter is $1$, and in the particular case $v = 4 + 1$, the only matching graph is $K_5$.
In the case $v = 6$, the graph shown below matches, with a diameter of $2$. The diameter can't be less than 2, since it would then be 1, meaning every vertex is adjacent to the five others, what contradicts with the 4-regularity.
The cases $v=6,7,8$ and $9$ are diameter 2 as well and can be treated with the same pattern: putting a star in a polygon. Example of star used :
- 6: Two triangles (A double edge between opposed vertices works too)
- 7: Star formed by jumping over one vertex. (Over two vertices works too)
- 8: Two squares (The star formed by jumping over two vertices works too)
- 9: Three triangles (Seems to be the only possibility)
For the case $v=10$, the least diameter is 2 too. A matching graph can be obtained from Petersen graph, by adding parallel edges to the ones linking the pentagon to the central star.