Teorema

Todo grafo $G$ tem um subgrafo $H$ cujo grau mínimo é maior que seu $\varepsilon(H)$, e cujo $\varepsilon(H)$ é maior do que $\varepsilon(G)$ do grafo inteiro. Matematicamnete temos que, para todo grafo $G$, de pelo menos uma aresta, há um subgrafo $H$ tal que $$\delta (H) > \varepsilon (H) \geq \varepsilon (G)$$ onde:

• $\delta(H)$ é o grau mínimo de H;
• $\varepsilon (G)$ é a quantidade média de arestas por vértices de G; e;
• $\varepsilon(H)$ quantidade média de arestas por vértices de H.

Demonstração: Façamos por construção. Para construir esse subgrafo $H$, vamos remover vértices de grau pequeno um a um de um grafo $G$ qualquer, de forma que restem somente os vértices de grau grande, para que seja interesante trabalhar com o grau minimo do subgrafo.

Primeiro, vamos calcular qual deve ser o grau de um vértice $v$ qualquer removido, para que a quantidade média de arestas por vértices do novo grafo $H_0$, seja maior que a quantidade média de $G$, isto é, tal que, $\varepsilon (H_0) \geq \varepsilon (G)$.

Para tanto, sejam $|A(G)|$ o número de arestas e $|V(G)|$ o número de vértices de $G$, e seja ainda $d(v)$ o grau que queremos calcular, temos:

$$\varepsilon (G)=\frac{|A(G)|}{|V(G)|} \leq \frac{|A(G)|-d(v)}{|V(G)|-1} = \varepsilon (H_0)$$ \[\Updownarrow\] $$|A(G)|(|V(g)|-1) \leq (|A(G)|-x)|V(G)|$$ \[\Updownarrow\] $$d(v) \leq \frac{|E(G)|}{|V(G)|} = \varepsilon (G)$$

Ou seja, se removermos um vértice tal que $v$ acima, de grau menor ou igual a $\varepsilon (G)$, o novo grafo, $H_0$, teremos $\varepsilon (H_0) \geq \varepsilon (G)$. Assim, se existir $v_{0} \in G$ de forma que $d(v_{0}) \leq \varepsilon (G)$, onde $d(v_0)$ é o grau de $v_0$, definimos $H_0 = G \setminus \{v_0\}$.

Além disso, se existir $v_{1} \in H_{0}$ tal que $d(v_{1}) \leq \varepsilon (H_{0})$, definimos $H_1 = H_0\setminus \{v_1\}$. E assim por diante. Se fizermos isso sucessivamente, chegaremos ao último conjunto que conseguimos construir, denotemos tal conjunto por $H$. E ainda podemos ecrever:

$$\varepsilon (H) \geq \varepsilon (H_n) \geq \dots \geq \varepsilon (H_1) \geq \varepsilon (H_0) \geq \varepsilon (G)$$ \[\Downarrow\] $$\varepsilon (H) \geq \varepsilon (G)$$

Portanto, se não conseguirmos construir o conjunto seguinte, então não existe vértice em $H$ cujo grau é menor ou igual a $\varepsilon(H)$, incluindo o vértice cujo grau é mínimo. Logo, $\delta(H) \geq \varepsilon(H)$. Mas como removemos somente vértices de grau menor que $\varepsilon (G)$, $\varepsilon(H) \geq \varepsilon(G)$.

Portanto, segue que $\delta(H) \geq \varepsilon(H) \geq \varepsilon(G)$.

$\square$