3
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Seems to have been first proved in H. Sachs, Regular graphs with given girth and restricted circuits, J. London Math. Soc. 38 (1963) 423-429. $\endgroup$ Commented May 13, 2012 at 6:01

2 Answers 2

5
$\begingroup$
  • 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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .