Ejercicio de teoría de grafos para encontrar un subgrafo con grado mínimo.

Question

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$

Answer 1

Para (2), ¿qué sucede si descartas todos los vértices que tienen un grado menor que $\frac{m}{n}$? ¿Obtienes un grafo vacío? Si no es así, ¿puedes demostrar por qué este grafo no está vacío? (Quizás debas proceder por inducción.)

Answer 2

Para la parte (4), hay un error bastante inocente en la pregunta: debería decir $$\frac{m}{n} \le n^{1/k} + 1.$$

Después de la parte (3), has encontrado un árbol $T$ dentro del subgrafo $H$. Imagina esto como un árbol enraizado que comienza desde $v$, y es fácil ver cuántos hijos tiene $v. ¿Cuántos hijos tiene cada hijo de$v? También puedes obtener un límite inferior ligeramente diferente aquí. ¿Cuántos niveles tiene $T$?

¿Puedes usar esto para dar un límite inferior para el número de vértices de $T$?