Sea G un grafo simple con n vértices y m aristas. ¡Demostrar que se cumple lo siguiente!

Question

Sea G un grafo simple con n vértices y m aristas. Demostrar que lo siguiente se cumple utilizando el Teorema del Apretón de manos:

$$\frac{m}{\Delta} \leq \frac{n}{2} \leq \frac{m}{\delta}$$

donde: $\Delta$ es el grado máximo de V(G) y $\delta$ es el grado mínimo de V(G)

Estoy preparando mi final y esta es una pregunta que debería poder resolver. La teoría de los gráficos es tal vez 3 días de edad para mí en este punto y por lo que estoy realmente sólo atascado en esto.

Agradecería cualquier ayuda. Lo que más ayudará es una explicación exhaustiva de por qué una prueba para esto es como es. Probar cosas en la teoría de grafos se siente... impar... hasta ahora.

Answer 1

Comience con $\Delta \ge$ grado medio $\ge \delta$ para cualquier gráfico.

Sabemos que el grado total es $2m$ por el lema del apretón de manos, por lo que el grado medio es $=\frac{2m}{n}$ . Así que $\Delta \ge\frac{2m}{n}\ge \delta$ .

Ahora, dejemos que m divida los tres lados, cambiando el $\ge$ a $\le$ : $$\frac{m}{\Delta}\le\frac{n}{2}\le\frac{m}{\delta}$$