Exercise 2.1.19 in An introduction to expander graphs by E. Kowalski

Question

I am trying to prove an exercise saying that the girth of a finite graph Γ with minimum valency $\geq 3$ is $≪ log(|Γ|)$. But I have no idea to do that.

Could please help me to prove it.

Answer 1

We prove a more general and explicit claim. Let $\Gamma$ be a finite undirected graph with the set of vertices $V$, with $|V|=|\Gamma|=n$, minimum valency $\delta\ge 3$, and girth $g$. Fix any vertex $v$ of $\Gamma$. Let $g’=\lfloor (g-1)/2\rfloor$ be the largest positive integer which is less than $g/2$. For each $0\le k\le g’$ by $V_k$ denote the set of all vertices $u$ of $\Gamma$ such that path distance from $v$ to $u$ is $k$. Then $V_0=\{v\}$ and $V_1=N(v_0)$ is the set of neighbors of the vertex $v_0$. Let $k\ge 2$. Each vertex of $V_k$ has exactly one neighbor in $V_{k-1}$, because otherwise it belongs to a cycle of length at most $2k<g$, which is impossible. Similarly we can show that each vertex of $V_{k-1}$ has no neighbors in $V_{k-1}$. Therefore it has at least $\delta-1$ neighbors in $V_k$, which implies that $|V_k|\ge (\delta-1)|V_{k-1}|$. Since $|V_1|\ge \delta$, by induction we obtain we have $|V_k|\ge (\delta-1)^{k-1}\delta$. Thus

$$n=|V|\ge \left|\bigcup_{k=0}^{g’} V_k\right|=\sum_{k=0}^{g’}|V_k|\ge 1 +\sum_{k=1}^{g’} (\delta-1)^{k-1}\delta=$$ $$1+\delta\frac{(\delta-1)^{g’}-1}{\delta-2}=\frac{\delta(\delta-1)^{g’}-2}{\delta-2}.$$

Thus $g\le 2g’+1\le 2\log_{\delta-1}\left(\frac {(\delta-2)n+2}\delta\right)+1=O(\log n)$.