Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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. –  Gerry Myerson May 13 '12 at 6:01
add comment

2 Answers 2

up vote 4 down vote accepted
  • 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$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.