En un grafo plano conectado finito $G$ , de tal manera que $\delta(G)\geq 3$ , demuestran que al menos $2$ las caras tienen como máximo $5$ bordes. He intentado escribir la suma de grados a partir del lema de Handshaking y luego sustituirla por la fórmula de Euler, pero me he quedado atascado.
Respuesta
¿Demasiados anuncios?
Utilizando el hecho $\delta(G)\geq 3$ se podría demostrar que cada arista forma parte de un ciclo y, por lo tanto, limita exactamente dos caras.
Denota por $e,v,f$ el número de aristas, vértices y caras en $G$ respectivamente.
Intuición
Como la prueba es bastante técnica, intentaré resumir la proposición que utilizo:
- $(f-1)\leq \frac{e}{3}$
- $2e\geq 3v$ lo que implica $v-\frac{2e}{3}\leq 0$
- Fórmula de Euler $v-e+f=2$
Prueba
Supongamos ahora, por contradicción, que la afirmación es falsa y, por tanto, al menos $f-1$ de las caras tienen al menos $6$ bordes.
Esto implica: $$2e=\sum\limits_{i=1}^{f} \text{#edges if the face } f_i\geq 6(f-1)\implies \\ 2e\geq 6(f-1)\implies (f-1)\leq \frac{e}{3}$$
Utilizando la fórmula de Euler $v-e+f = 2$ obtenemos $$v-e+f\leq v-e+\frac{e}{3} +1=v-\frac{2e}{3} + 1 =2 $$
Desde
$$2e = \sum\limits_{u\in V(G)}deg(u) \geq 3v\implies \frac{2e}{3}\geq v$$
y finalmente obtenemos una contradicción: $$v-\frac{2e}{3}\leq 0 \implies v-\frac{2e}{3} + 1 \leq 1$$ y porque $$v-e+f \leq v-\frac{2e}{3} + 1 $$ obtenemos
$$2 = v-e+f \leq 1 $$
que es una contradicción.
