Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
From wikipedia's page Cage graph
Formally, an $(r,g)$-graph is defined to be a graph in which each vertex has exactly $r$ neighbors, and in which the shortest cycle has length exactly $g$. It is known that an $(r,g)$-graph exists for any combination of $r \geq 2$ and $g \geq 3$.
Can someone provide a proof of this claim?
Thanks.
A cycle of length $g$ is a $(2,g)$-graph.
The graphs of the Platonic solids are $(3,3)$-, $(3,4)$-, $(4,3)$-, $(3,5)$-, and $(5,3)$-graphs.
Regular tilings of the Euclidean plane by triangles, squares, and hexagons are $(3,6)$-, $(4,4)$-, and $(6,3)$-graphs, respectively. If you insist on a finite graph, take a large parallelogram whose vertices lie on the lattice, and identify opposite edges to obtain a torus.
Regular tilings of the hyperbolic plane give $(r,g)$-graphs for any other pair $(r,g)$. Again, one can obtain finite $(r,g)$-graphs by choosing a sufficiently large portion of the infinite $(r,g)$-tiling and rolling it up into a surface (which must have genus at least 2).
Finally, if you don't insist that all graphs are simple, it is easy to construct $(2,2)$-graphs and $(1,g)$-graphs for all $g\ge 1$.
I cut'n'paste from http://symomega.wordpress.com/2010/02/03/the-cage-problem/ (note Cay(G,S) is the Cayley graph).
Now for the construction of Biggs: take a tree T of depth g-1 such that all vertices at depth less than g-1 have valency k. Colour the edges of T with k colours so that no two edges adjacent to a common vertex have the same colour. For each colour $\alpha$, define an involutory permutation $i_{\alpha}$ of the vertices of T such that $i_{\alpha}$ interchanges v and w if and only if v and w are joined by an edge coloured $\alpha$. Now let S be the set of k involutions obtained and G be the group generated by S (G is finite as it is a group of permutations of a finite set). Then Cay(G,S) is a k-regular graph. Now if the girth of our Cayley graph was $s\lt g$ then we would have a word $w_1w_2\cdots w_s=1_G$ with each $w_i$ in S. However, the image of the root of our tree T under $w_1w_2\cdots w_s$ is a vertex at distance $s\lt g$ from the root, contradicting $w_1w_2\cdots w_s$ being the identity permutation. Thus Cay(G,S) has girth at least g.
