Relação entre o raio de um grafo e o seu número de vértices
Teorema
Seja $G$ um grafo de raio máximo $k$ e grau máximo no máximo $d \geq 3$,então $V(G)$ tem menos que $\frac{d}{d-2}(d-1)^k$ vértices.
Demonstração:
Vamos tomar $z$ como o vértice central de $G$ e tomemos $D_i$ os conjuntos dos vértices que distam $i$ arestas de $z$. Podemos ver isso como “círculos” em torno de $z$, como um sonar. É simples visualizar que $V(G)=\bigcup_{i=0}^k D_i$, e claramente $|D_0| = 1$ e $|D_1| \leq d$.
Para $i \geq 1$ temos que $|D_{i+1}| \leq (d-1)|D_i|$, pois cada vértice em $D_{i+1}$ é vizinho de um vértice de $D_i$ e cada vértice $D_i$ possui no máximo $(d-1)$ vizinhos em $D_{i+1}$ (pois pode haver outro vizinho em $D_{i-1}$). Portanto, $|D_{i+1}| \leq d(d-1)^i$ para todos $i<k$ por indução. Isso nos dá:
$$|V| \leq 1 + d \sum_{i=0}^{k-1} (d-1)^i = 1 + \frac{d}{d-2}((d-1)^k - 1) < \frac{d}{d-2}(d-1)^k.$$ $$\Downarrow$$ $$|V| < \frac{d}{d-2}(d-1)^k$$
Assim sendo, o Teorema segue.
$\square$
Da mesma forma, podemos limitar a ordem de $G$ de baixo para cima assumindo que tanto seu grau mínimo quanto sua circunferência são grandes. Para $d \in \mathbb{R}$ e $g \in \mathbb{N}$ deixe
$$n_0(d,g) := \begin{cases} 1+d \sum_{i=0}^{r-1}(d-1)^{i},& \mbox{se } g =: 2r+1 &\mbox{é ímpar;}\\ \\ 2 \sum_{i=0}^{r-1}(d-1)^{i}, & \mbox{se } g =: 2r & \mbox{é par.} \end{cases}$$
Não é difícil provar que um grafo de grau mínimo $\delta$ e circunferência $g$ tem pelo menos $n_0(\delta,g)$ vértices. Curiosamente, pode-se obter o mesmo limite para seu grau médio:
Teorema
Seja $G$ um grafo. Se $d(G) \geq d \geq 2$ e $g(G) \geq g \in \mathbb{N}$, então $|G| \geq n_0(d,g)$.
Um aspecto do Teorema acima é que ele garante a existência de um ciclo curto em comparação com $|G|$.
Corolário
Se $\delta(G) \geq 3$, então $g(G) < 2 \log |G|$.
Demonstração:
Se $g := g(G)$ é par, então:
$$n_0(3,g) =2 \frac{2^{g/2}-1}{2-1} = 2^{g/2} + (2^{g/2}-2) > 2^{g/2},$$
enquanto se $g$ é ímpar, temos:
$$n_0(3,g) = 1 + 3 \frac{2^{(g-1)/2}-1}{2-1} = \frac{3}{\sqrt{2}}2^{g/2} -2 > 2^{g/2}.$$
Como $|G| \geq n_0(3,g)$, o resultado segue.
$\square$