todos los valores posibles de vértices, dado el número de caras y que todos los vértices tengan el mismo grado en un grafo plano conexo?

Question

Un grafo plano conectado tiene 26 caras y una cantidad desconocida de vértices (denominados "V"). Todos los vértices tienen el mismo grado. ¿Cuáles son todos los valores posibles de V?

Lo que tengo hasta ahora:

V + F = E + 2 (Euler) --> V + 26 = E + 2 --> V -E = -24

Los he probado al azar para diferentes valores de grado.

Cada vértice tiene grado 3, V = 48

Cada vértice tiene grado 4, V = 24

Cada vértice tiene grado 5, V = 16

Cada vértice tiene grado 6, V = 12

¿Cuál de estos casos puede darse? V = 12, 16, 24, 48? ¿Me he perdido algo? Me he dado cuenta de que a medida que aumenta el grado, el valor de V también disminuye (así que dudo que haya valores enteros después de V = 12).

Answer 1

Caso 1: grado 3. Construimos una secuencia de grafos con sólo caras ``triangulares''. Sea $G_0$ es un triángulo, tiene 3 vértices y 2 caras triangulares. Habiendo construido $G_n$ tomamos una cara triangular arbitraria, añadimos un vértice en el centro y conectamos a las tres esquinas del triángulo. Este procedimiento añade 1 vértice y 2 caras. Concluimos que $G_{23}$ tiene $3+23=26$ vértices y $2+46=48$ caras triangulares. El dual de este grafo tiene 26 caras y 48 vértices de grado 3. Nótese que esto produce muchas realizaciones, ya que hay muchas maneras de elegir la cara para el siguiente paso.

Caso 2: grado 4. Construimos una secuencia de grafos con sólo caras de longitud 4. Empezamos con un ciclo de 6, trazamos una cuerda entre dos vértices opuestos por el interior y otra por el exterior. Llamamos a este grafo $G_0$ tiene 6 vértices y 4 caras de longitud 4. Habiendo construido $G_n$ tomamos una cara arbitraria y la sustituimos por una copia de $G_0$ . Esto añade 2 vértices y 2 caras. Concluimos que $G_{10}$ tiene $6+20=26$ vértices y $4+20=24$ caras. El dual de este grafo tiene 26 caras, y 24 vértices de grado 4. De nuevo: esto produce muchas realizaciones.

Caso 3: grado 5. Partimos de un octaedro, llamamos polos a dos vértices independientes y ecuador al ciclo de 4 restante. Tienes 6 vértices y 8 caras. Subdivide cada arista a lo largo del ecuador y dibuja 8 nuevas aristas desde los 4 nuevos vértices hasta los 2 polos. Ahora tienes 10 vértices y 16 caras. Añade dos nuevos vértices a cada una de las 8 aristas creadas en el paso anterior. Ahora tienes 26 vértices y 16 caras, cada una de ellas tiene longitud 5. El dual de este grafo tiene 26 caras y 16 vértices de grado 5.

Caso 4: grado >5. Esto es imposible. Todo grafo plano tiene un vértice de grado 5 como máximo.