4
$\begingroup$

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.

Thanks for your thoughts,

Brian

$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – Calvin Lin Jul 20 '13 at 18:29
2
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Relative0 Jul 30 '13 at 15:45
  • $\begingroup$ 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? $\endgroup$ – Calvin Lin Jul 30 '13 at 17:17
  • $\begingroup$ 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. $\endgroup$ – Relative0 Jul 31 '13 at 6:20
  • $\begingroup$ @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$. $\endgroup$ – Calvin Lin Jul 31 '13 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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