¿Cuál es el número máximo de aristas de un gráfico plano?

Esta es una pregunta bastante interesante.

Primero, aclaremos que consideramos un gráfico simple, es decir, prohibimos bucles y múltiples aristas.

Así que supongamos que tenemos un gráfico plano simple en vértices [matemática] v [/ matemática] y queremos maximizar [matemática] e [/ matemática]. En primer lugar, si tenemos un gráfico plano con el número máximo de vértices, entonces cada cara es un triángulo *, porque de lo contrario podríamos agregar un nuevo borde de tal manera que el gráfico permanezca plano. Esto significa que [matemáticas] 3f = 2v [/ matemáticas]. Insertemos esto en la fórmula de Euler [matemáticas] v-e + f = 2 [/ matemáticas] para obtener [matemáticas] e = 3v-6 [/ matemáticas].

Tenga en cuenta que esta es una igualdad para cualquier gráfico triangulado, por lo que se logra el límite.

* Este no es el caso cuando tenemos 0, 1 o 2 vértices, y las respuestas para ellos son 0, 0 y 1 respectivamente.