Why is the number of vertices in a graph $\geq n_0(d,g)$?

(Reinhard Diestel Graph Theory, GTM 173, edition 3)

Theorem 1.3.4 (Alon, Hoory, Linial 2002): Let $G$ be a graph. If $d(G) \geq d \geq 2$ and $g(G) \geq g \in \mathbb N$, then $|G| \geq n_0(d,g)$, where $n_0(d,g) : = 1 + d \sum_{i=0}^{r-1} (d-1)^i$ if $g=: 2r+1$ is odd, or $n_0(d,g): = 2 \sum_{i=0}{r-1}(d-1)^i$ if $g=:2r$ is even.

Here, $d(G)$ is the average degree of $G$, and $g(G)$ is the girth of $G$ (the minimum length of a cycle in $G$).

As far as I see, no prove is given on this textbook.

There is an exercise on page 30 (the 6th),

Prove the weakening of Theorem 1.3.4 obtained by replacing average with minimum degree. Deduce that $|G| \geq n_0(d/2,g)$ for every graph $G$ as given the theorem.

I think this is equivalent to

(*) For $c$ the minimum degree of $G$, and $g$ the girth of $G$, $|G| \geq n_0(c,g)$. For $d$ the average degree of $G$, and $g$ the girth of $G$, $|G| \geq n_0(d,g)$.

Is it alright for me to equal the exercise to ()? Would anyone please give me some advice on the proof of the exercise or ()?

-

1 Answer

$g = 2r+1$, $r\in N$: Let $v\in V$ and $D_i=\{u\in V\mid d(v,u)=i\}$ be the set of vertices at distance $i$ from $v$. Clearly we have $D_i \bigcap D_j = \emptyset$, for $i\neq j$. Claim: $\mid D_i\mid \geq \delta(\delta-1)^{i-1}$ for $1\leq i\leq r$. The vertex $v$ is not contained in a cycle of length less than $g$. The graph contains a cycle of length at most $2r$. From this immediately follows the claim: Each vertex in $D_i$, $1\leq i\leq r$, is connected to exactly one vertex in $D_{i-1}$ and at least $\delta-1$ vertices in $D_{i+1}$. By a simple inductive argument we have $|D_0|$ = 1, $|D_1| \geq \delta$ and $|D_i| \geq \delta(\delta-1)^{i-1}$. We can therefore conclude that G contains at least $1+\sum_{i=1}^{r}\delta(\delta-1)^{i-1}$ vertices, and claim of Theorem 1.3.4 follows.

$g = 2r$, $r\in N$: For the case of even girth we use the same idea as before, but instead of starting at a vertex $v$, we start at an edge $\{v,u\}\in E$. For i$\in$N, consider the sets $D_i^{(u)}=\{x\mid \hat{d}(u,x) = i\}$ and $D_i^{(v)}=\{x\mid \hat{d}(v,x) = i\}$, where $\hat{d}(x,y):=d_{G-\{v,u\}}(x,y)$. Again $D_i^{(x)}\bigcap D_j^{(x)} = \emptyset$ for $i\neq j, x\in \{u,v\}$. Clearly $\mid D_0^{(x)}\mid = 1$ and $\mid D_i^{(x)}\mid \geq (\delta-1)^i$ for $i>0$.

Claim: $D_i^{(v)} \bigcap D_j^{(u)} = \emptyset$, for all $i,j\in [0,r-1]$. The number of vertices in $G$ are at least $2\sum_{i=0}^{r-1}(\delta-1)^{i}$, and claim of Theorem 1.3.4 follows.

-