Un problema de grafo plano

Question

El problema es el siguiente:

Sea $G$ un grafo conectado y plano cuyo número de vértices es múltiplo de $8$. $5/8$ de los vértices tienen grado $3$, $1/4$ tienen grado $4$ y $1/8$ tienen grado $5$. Todas las caras de $G$ son triángulos o cuadriláteros. Encuentra el número de caras triangulares, el número de caras cuadriláteras, el número de vértices y el número de aristas de $G$. Dibuja al menos un grafo de este tipo.

Es un problema de un examen antiguo. (Estoy intentando prepararme para el mío.)

He visto a gente resolver problemas como este utilizando una fórmula que tenía algún tipo de suma ponderada (y creo que los pesos eran los grados, probablemente de los vértices), y parecía estar relacionada con la fórmula de Euler. Recuerdo que la gente decía que eran de trámite, con un procedimiento algorítmico para resolverlos. Desafortunadamente, no entendí la fórmula en ese momento, y no la puedo encontrar ahora, ni en mis apuntes ni en internet.

He estado intentando derivar algo útil a partir de lo que sé sobre el teorema de Euler, pero estoy fracasando rotundamente.

¿Podrías ayudarme con esto, por favor?

Answer 1

Desde el conteo de incidencias vértice-arista, tenemos $$\tag1 2e = 3\cdot\frac58v+4\cdot\frac14v+5\cdot \frac18v=\frac72v.$$ Desde el conteo de incidencias cara-arista, tenemos $$\tag2 2e = 3f_3+4f_4.$$ Desde la fórmula de Euler $v+f=e+2$, tenemos $$\tag3 v+f_3+f_4=e+2.$$ Así $7(3)$ nos da usando $(1)$: $7e+14=7v+7f_3+7f_4=4e+7f_3+7f_4=6e+4f_3+3f_4$ o $$e=4f_3+3f_4-14.$$ Usando $(2)$ nuevamente, encontramos $3f_3+4f_4=2e=8f_3+6f_4-28$ o $$5f_3+2f_4=28.$$ Como $f_3,f_4\ge0$, esto solo permite $(f_3,f_4,e,v)\in\{(0,14,28,16),(2,9,21,12),(4,4,14,8)\}$. Un ejemplo con la última tupla se obtiene tomando un grafo de cubo y agregando dos diagonales de cara con un punto final común (que asumen grado 5 de esta manera). Releyendo la declaración original del problema (en oposición a la ecuación $(1)$ que obtuvimos de ella), vemos que $v$ debe ser un múltiplo de $8$, por lo tanto, $(2,9,21,12)$ no funciona.

---

De acuerdo, "fotos, o no pasó":