Gráfico planar de alta valencia

Question

Un resultado clásico de la teoría de grafos nos dice que todo grafo plano debe tener al menos un vértice con valencia no mayor que 5. Por otro lado, existen ejemplos de grafos planos que son 5-regulares (por ejemplo, el esqueleto del icosaedro). Mi pregunta es si existe un grafo plano $G$ Satisfaciendo a

1. no existen aristas múltiples en $G$ ;
2. $G$ tesela un polígono;
3. todos los vértices internos (los contenidos en el interior del polígono) tienen valencia par $\geq 6$ .
4. todos los vértices tienen valencia $\geq 5$ (incluyendo los vértices del polígono).

Tenga en cuenta que si tal $G$ existe, algunos vértices del polígono deben ser 5-valentes. Gracias de antemano por cualquier idea útil.

Answer 1

No. Si tesela un $k$ -y el número de vértices internos es $m$ entonces el número de aristas es al menos $$e\geqslant (5k+6m)/2=3m+\frac52 k. \quad \quad (A) $$ Si el número de caras internas es $f-1$ , entonces contando las aristas por caras obtenemos $$2e\geqslant 3(f-1)+k.\quad \quad (B)$$ Pero $e=f+(k+m) -2$ por el teorema de Euler, por lo que $f-1=e-k-m+1$ y por (B) tenemos $2e\geqslant 3e-3k-3m+3+k$ Es decir, $$3m+2k-3\geqslant e. \quad \quad (C) $$

(A) se contradice con (C).

Answer 2

He aquí otra solución, con supuestos más débiles. Supongamos que G tesela un $k$ -donde todos los vértices internos tienen valencia al menos 6, y los vértices del $k$ -tienen valencia al menos 4. Tome 2 copias de G y etiquete los vértices del más externo $k$ -ciclos como $u_1,\ldots, u_k$ y $v_1,\ldots, v_k$ . A continuación, añada las aristas de $u_i$ a $v_i$ y de $u_i$ a $v_{i+1}$ para cada $1\leq i\leq k$ y donde $v_{k+1}\equiv v_1$ . Esto produce un gráfico plano simple en el que cada vértice tiene una valencia de al menos 6, lo cual es imposible.