I've been reading some papers about (n,g)cages, but it doesn't seem trivial to me that there is, indeed, for example, a K-regular graph with girth K, for large Ks. So:
Can you give me an example of a K-regular graph (it may be a graph with minimum degree K, if it's easier) and girth K (it may be >= K, if it's easier) for a given integer K.
Thanks in advance.
It is one of the problems for which Random Graph theory seems amazingly powerful. Bollobas gives a very short (non-deterministic) construction of graphs with "minimum degree at least K" and "girth at least g". He's actually creating a large random graph with few short cycles, then removing an edge from each of them to break them all. As the average degree of his graph is more than 2K, he then removes vertices of degree less than K until the minimum degree is large enough.
You can read all about that in "Extremal Graph Theory (Bollobas)", chapter 3.1 : "Graphs with large minimum degree and large girth" (he also gives a construction of K-regular graphs of girth "at least something")
Nathann
The easiest way to do this is as said the probabilistic method. However, for those who prefer non-random constructions, here is a greedy method.
Choose some large $n$ (you can calculate what is needed easily enough).
Start with the empty $n$-vertex graph. Add edges greedily between vertices subject to two conditions. First, the vertices you join should always have distance at least $K$ in the current graph (if not connected, then assume distance is infinite). Second, both vertices should have degree at most $K-1$.
When this procedure is forced to terminate for lack of such pairs, you have a graph with maximum degree $K$ and girth at least $K$. Now take any vertex $v$ of degree less than $K$. Look at all the vertices at distance less than $K$ from $v$ (including $v$). This set must include all the vertices of degree less than $K$, or you would not have terminated. But the set has at most $1+K+K(K-1)+K(K-1)^2+..+K(K-1)^{K-1}=C$ vertices, since the maximum degree is $K$. Similarly, the set of vertices at distance at most $2K$ from $v$ is bounded, and we can presume there are at least $KC^2$ vertices at distance more than $2K$ from $v$. Now joining greedily vertices of degree less than $K$ to these far-away vertices greedily without creating short cycles must succeed (each edge added blocks at most $C$ vertices, and there are certainly not more than $CK$ edges required).
To make this have girth exactly $K$, start with a $K$-cycle. To make it regular is a little harder: one option is to run the first procedure (starting with a $K$-cycle which we insist on preserving forever, to fix the girth) with a much higher distance requirement to join two edges (say $3K$), then after termination, identify a low-degree vertex $u$ and adding an edge to some far-away $v$ (as before) then removing some edge $vw$. Now $w$ cannot have been (before edge removal) a low degree vertex (it is too far away from the first low degree vertex) and furthermore it cannot be within distance $K$ of any remaining low degree vertex, so you can join it to a remaining low degree vertex. Rinse, repeat, assuming $n$ satisfies the parity condition for a $K$-regular graph to exist (and is large enough) you will succeed.
In this paper http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190070210/abstract even more strict theorem is proved. If I remember well, the example you are asking about belongs to Tutte.
