$G$ es un simple gráfico, a continuación, $d(G) = \frac{2e(G)}{|G|}$ ser el grado promedio de un simple gráfico.
Lema 1
Si $G$ es un grafo conexo, entonces contiene un camino de longitud $\min(2\delta(G), |G|-1)$ donde $\delta(G)$ es el mínimo grado de $G$. (ejercicio 1.7. en la Teoría de grafos por Diestel)
Lema 2
Cada gráfico de $G$ tiene un componente $H$, de tal manera que $d(H)\geq d(G)$.
Prueba
Hecho: Si $x_i,y_i>0$ $\frac{x_i}{y_i} < t$ todos los $1\leq i\leq k$,$\frac{\sum_{i=1}^k x_i}{\sum_{i=1}^k y_i} < t$. Asumir el lema es falso, después de considerar todos sus componentes $H_1,\ldots,H_k$, $d(H_i) = \frac{2e(H_i)}{|H_i|} < d(G)$, a continuación,$d(G) = \frac{\sum_{i=1}^k 2e(H_i)}{\sum_{i=1}^k |H_i|} < d(G)$, una contradicción.
Teorema de
Un simple gráfico de $G$ debe contener una ruta de acceso de la longitud de, al menos,$d(G)$.
Prueba
Prueba por inducción. Es cierto que para el gráfico de 1 vértice. Supongamos que es cierto para todos los gráficos con $k$ vértices, $k < n$. Considere la gráfica de $G$ $n$ vértices. Si el gráfico tiene más de 1 componente, entonces usamos [Lema 2] y mostrar existe un subgrafo $H$ estrictamente menor número de vértices, tal que $d(H)\geq d(G)$, y sólo hay que aplicar la hipótesis de inducción.
De lo contrario, el gráfico está conectado. Si existe un vértice $v$ con grado en la mayoría de las $\frac{1}{2}d(G)$, nos lo puede quitar, y $d(G-v) \geq d(G)$, luego por hipótesis inductiva, en $d(G-v)$ no será un camino de longitud de, al menos,$d(G)$. Si no hay tal vértice. a continuación, debemos tener $\delta(G) > \frac{1}{2} d(G)$. Por [Lema 1], tenemos que tiene un camino de longitud $\min(2 \delta(G) ,|G|-1)$. $2\delta(G) \geq d(G)$ y $d(G)\leq |G|-1$, por lo que contienen un camino de longitud de, al menos,$d(G)$.
