Estaba haciendo algunos problemas prácticos en teoría de grafos y agradecería algo de ayuda en este. Este problema es de un examen de práctica del curso de matemáticas discreta en Princeton.
Considera un grafo $G$ con $n$ vértices que no tiene ciclos de longitud $\le 2k+1$. Sea $m$ el número de aristas en el grafo. El objetivo del problema es demostrar que $m \le n^{1 + \frac{1}{k}} + n.
1) ¿Cuál es el grado promedio en $G$?
Dado que hay $m$ aristas, el grado total es $2m$. Por lo tanto, el grado promedio es $\frac{2m}{n}$.
2) Demuestra que existe un subgrafo $H$ de $G$ con grado mínimo $\frac{m}{n}$. La pista dada es: Piensa en los vértices que tienen un grado menor que $\frac{m}{n}$.
No tengo idea de cómo proceder con este. Estoy bastante seguro de que esta parte del problema no requiere la condición del ciclo mínimo. Creo que se requiere algún tipo de límites.
3) Sea $v$ un vértice en $H$. Considera el subgrafo de $H$ inducido por los vértices a una distancia de al menos $k$ desde $v$. Demuestra que este subgrafo es un árbol.
Si el subgrafo no fuera un árbol, existiría un ciclo. Sin embargo, todos los vértices están a una distancia de al menos $k$ y por lo tanto el ciclo tendría una longitud de al menos $2k +1$, lo que contradice la hipótesis inicial.
4) Demuestra que $\frac{m}{n} \le n^{\frac{1}{k}}$ + 1. (Pista: Da límites en el número de vértices en el subgrafo construido en la parte 3.)
Nuevamente, no estoy muy seguro de cómo encontrar un límite apropiado.
Agradecería mucho algo de orientación para este problema, especialmente para la parte 2 con la existencia del subgrafo. Gracias por tu tiempo.
Edición: Solución a la parte 2 obtenida gracias a la ayuda de Code-Guru y Erick Wong.
Inducimos en el número de vértices. Sea $\nu$ el grado promedio del grafo. Dado un grafo de un vértice, tenemos un grado promedio $\nu=0$. Existe trivialmente un subgrafo con grado mínimo $\frac{\nu}{2}$, es decir, el propio grafo de un solo vértice. Este forma nuestro caso base.
Supongamos entonces que cada grafo de $n-1$ vértices tiene un subgrafo con grado mínimo $\frac{\nu}{2}$. Considera un grafo $G$ con $n$ vértices. Si el grafo no contiene vértices $v$ con $\deg{v} < \frac{\nu}{2}$ entonces hemos terminado.
De lo contrario, fija un $v$ de este tipo y retíralo. Dado que $\deg{v} < \frac{\nu}{2}$ eliminamos a lo sumo $\nu$ grados del grado total del grafo. El grado promedio del grafo de $n-1$ vértices es entonces $$\nu_{n-1} \ge \frac{n\nu - \nu}{n-1} = \nu$$ Más específicamente, el grado promedio no decrece. Por lo tanto, por la hipótesis inductiva, existe un subgrafo de $G\backslash\{v\}$ con grado mínimo al menos $\frac{\nu_{n-1}}{2} \ge \frac{\nu}{2}$ que es también el subgrafo deseado de $G$ en sí mismo.
El resultado se cumple por inducción matemática. $\square$
Edición 2: Solución a la parte 4 gracias a Erick Wong
Consideramos el árbol obtenido en la parte 3 como enraizado en $v$. $v$ tiene al menos $\frac{m}{n}$ hijos debido a su límite de grado. Similarmente, cada hijo posterior tiene al menos $\frac{m}{n} - 1$ hijos. Por lo tanto, obtenemos un límite inferior para el número de vértices como $$v_T \ge 1 + \frac{m}{n} + \frac{m}{n}\left(\frac{m}{n}-1\right) + \cdots + \frac{m}{n}\left(\frac{m}{n} - 1\right)^{k-1}$$ Evaluamos la suma como una serie geométrica $$v_T \ge 1 + \frac{m}{n}\left(\frac{\left(\frac{m}{n}-1\right)^k - 1}{\frac{m}{n}-2}\right)$$ Si $\frac{m}{n} \le 2$ entonces el límite requerido es trivial. Así que considera $\frac{m}{n} > 2$. Nuestra desigualdad se convierte en $$n \ge v_T \ge 1 + \frac{m}{n}\left(\frac{\left(\frac{m}{n}-1\right)^k - 1}{\frac{m}{n}-2}\right)$$ $$m - 2n \ge \frac{m}{n}\left(\frac{m}{n}-1\right)^k - 2$$ $$n - 2n\cdot\frac{n - 1}{m} \ge \left(\frac{m}{n}-1\right)^k$$ $$n \ge \left(\frac{m}{n}-1\right)^k$$ $$n^{\frac{1}{k}} + 1 \ge \frac{m}{n}$$ como se requiere. $\square$
