Demostrar que ningún gráfico plano conectado con $\lt 12$ rostros y $\gt 3$ grado cada vértice tiene una cara con %\le 4$ aristas delimitadoras

Question

He pasado las últimas 7 horas tratando de resolver este problema, no es broma. El libro de texto es absolutamente inútil y no hay nada útil en Internet.

Dejemos que $G$ sea un gráfico plano simple con menos de $12$ caras, en las que cada vértice tiene un grado al menos $3$ . Utilice la fórmula de Euler para demostrar que $G$ tiene una cara delimitada como máximo por cuatro aristas.

Fórmula de Euler:

$$n - m + f = 2$$

Así que:

$$f \le 11$$ Para cada vértice $v$ , $deg(v) \ge 3$

Hasta ahora he averiguado que probablemente debería demostrar (el contrapositivo) que es imposible que toda cara esté limitada por $\ge 5$ bordes. En ese caso, habría al menos $5$ bordes, y por extensión, al menos $5$ vértices. Además, el gráfico completo $K3$ tiene $4$ vértices y $8$ bordes, por lo que también son mínimos. También que $5f \le 2m$ ya que cada cara está rodeada por $\ge 5$ aristas y cada arista está rodeada por $2$ caras.

¿A dónde voy a partir de ahí? He cubierto 4 páginas de cuaderno en ecuaciones inútiles tratando de resolver algo, pero no he hecho ningún progreso en absoluto.

Por favor, ayúdame.

Answer 1

Cada arista tiene dos vértices, por lo que la suma de los grados de todos los vértices es $2m$ . En particular, $2m \ge 3n.$

Por lo tanto, $$2 = n - m + f \le -\frac{1}{3}m + f.$$

Cada arista limita dos caras. Así que la suma del número de aristas que limitan cada cara es también $2m$ . Si cada cara estuviera delimitada por al menos cinco aristas, entonces $5f \le 2m$ . Junto con la desigualdad anterior, $$f \ge 2 + \frac{1}{3}m \ge 2 + \frac{5}{6}f,$$ o en otras palabras $f \ge 12.$