# Girth of undirected $k$- regular graph has number d of vertices more than $k^{2} + 1$

I have found this: Graph with girth 5 and exactly $k^2+1$ vertices

The author however does not say how he proved the lemma (my title). Trying to work this out from (#3) here:

http://cse.iitkgp.ac.in/~agupta/graph/Sol-H2.pdf

the latter is very insightful. However applying what I think is going on I take there to be, starting with a chain of 5 edges with the ends vertices which I call u and v. Now if u and v are connected we would have a graph with 5 vertices and a girth of 5; a pentagon. Now if u and v are not connected we have that there are k-1 vertices that u could be connected and the same with v. Now either way u and v have to be connected to something so as to create a cycle hence there are k-2 edges coming out of each u and v. So if I multiply $(k-2)(k-2)$ and add the number of vertices already in the graph (5) we would have the equation $(k-2)^{2}+5 = k^{2}-4k+4+5= k^{2}-4k+9$.

Now if we have the 2-regular graph with girth 5 (the pentagon) then I plug in k=2 and get $2^{2}-4(2)+9 = 5$ which is precisely equal to $k^2 + 1 = (2)^{2}+1 = 5$. This however is not greater than the original proposition of $k^{2} + 1$ instead it equals it. I don't know what is going on here and also I am not sure how to work out a "formal" proof of this - if I am even on the right track.

Brian

• Your title should be $k^2+1$, not $k_2 + 1$. Also, the "more than" is actually "more than or equal to"; the original phrasing was "at least $k$ vertices", which is "more than or equal to $k$ vertices". – Calvin Lin Jul 20 '13 at 18:29

You are misquoting the original statement. It states that "a graph with girth 5 and degree of at least $k$ has at least $k^2+1$ vertices."

The "at least" should be translated into "more than or equal to"

For a proof of this general lemma, consider the case where the graph has girth $2n+1$ and degree at least $k$.

Pick 1 vertex, call it $A$. It is connected to $k$ other vertices. Call these vertices $A_{1}$ to $A_{k}$.
These vertices are connected to $A$, and to $k-1$ other vertices. Call these vertices $A_{1,1}$ to $A_{k, k-1}$.
Continue this procedure for $n$ times, so that we have vertices labelled up to $A_{a_1, a_2, \ldots a_n}$ where $1 \leq a_1 \leq k$ and $0 \leq a_i \leq k-1$ for $2\leq i \leq n$.

Claim: These vertices are distinct. If they are not distinct, then the girth is less than $2n+1$.

We have $k^n +1$ distinct vertices labelled, so the graph has at least $k^n+1$ vertices.

• Thanks for the answer, I accepted it but don't understand how one got from having a girth of 2n + 1 to having $k^n + 1$ distinct vertices labeled. – Relative0 Jul 30 '13 at 15:45
• Which part of the answer did you not understand? Do you understand the construction of the vertices? Do you know how to show that these vertices are distinct? – Calvin Lin Jul 30 '13 at 17:17
• I see that the vertices are distinct as they are chosen/labeled that way. I however don't see why the girth would be less than 2n + 1, and also I don't see how that means we have $k^n + 1$ distinct vertices labeled. Thanks for the help. – Relative0 Jul 31 '13 at 6:20
• @Relative0 You've got it slightly wrong. After labeling the vertices, there needs to be an argument that they are distinct (which lies in the claim). If there are any 2 vertices that are actually the same vertex, do you see how we get a chain of length less than $2n+1$? Finally, count the number of such vertices; there are $k$ possibilities for each of the indices, so $k^n$ in total. Add the initial distinguished vertex $A$, for a total of $k^n+1$. – Calvin Lin Jul 31 '13 at 14:49