Gráfico plano bipartito

Question

Demostrar que un grafo plano bipartito (es decir, bicoloreable) con $E$ bordes y $V$ vértices satisface: $E\leq 2V-4$ para $V\geq 3$ .

Answer 1

Consideremos una incrustación de $G$ . Tenga en cuenta que $G$ es bipartita entonces es libre de triángulos. Obsérvese que el recorrido alrededor de cualquier cara debe tener una longitud de al menos 3 (suponiendo que el grafo sea simple). Ahora, observa que si el paseo alrededor de una cara tiene longitud 3, entonces debe ser un triángulo. Por lo tanto, el paseo alrededor de cualquier cara tiene una longitud de al menos 4. Ahora $\mathcal{F}$ denota el conjunto de caras en la incrustación dada y sea $l(f)$ denota la longitud de la cara de paseo $f\in\mathcal{F}$ . Observe que $2E=\sum_{f\in\mathcal{F}}l(f)\geq 4F$ . Por lo tanto $E\geq 2F$ . Ahora, por la fórmula de Euler $2=V-E+F\leq V-E+\frac{E}{2}$ . Esto se puede reordenar para obtener la desigualdad deseada.

Actualización: Suponía que cada cara estaba delimitada por un ciclo. El nuevo argumento funciona incluso después de eliminar esta suposición.