Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

(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 ()?

share|improve this question
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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