¿Hay un gráfico planar que (casi) todos sus vértices tienen grado 6?

Question

¿Es cierto que para cualquier $N_0\in\mathbb N$ allí existe un gráfico planar $G=(V,E)$ en (al menos) $N_0$ vértices tal que al menos $$|V|(1-o(1))$ vértices de $ tiene grado 6?

¿Es fácil demostrar que ningún gráfico planar 6-regular existe, pero hay un gráfico planar "casi-6-regular"?

Answer 1

Considere la posibilidad de un hexagonal mosaico del plano, y subdividir cada hexágono en seis triángulos equiláteros. Ahora todos los vértices tienen grado seis, aunque con un infinito número de vértices.

Si usted está dispuesto a conformarse con simplemente una alta proporción de los vértices con grado seis, considere la posibilidad de truncar el mosaico en un gran radio de $R$ desde el origen. Los vértices dentro de este radio todavía tienen un grado de seis, y sólo el límite de los vértices tienen menos de seis vecinos. Pero el número de vértices en el interior es proporcional al área de cobertura, por lo $O(R^2)$, mientras que el número de vértices en el límite proporcional al perímetro, y que sea fácilmente visible a ser $O(R)$.

Así como $R$ aumenta sin límite, la proporción de grado seis vértices tiende a 1.

---

Esto puede ser menos de la mano "ondulado" para considerar un único hexágono regular, que se subdividen en seis triángulo equilátero, luego se somete a sucesivos refinamientos en la que cada triángulo se subdivide en cuatro sub-triángulos (con el acompañamiento de la interseccion de los lados). El número de triángulos que crece por un factor de 4 con cada uno de refinamiento, que el número de vértices del perímetro sólo se duplica con cada paso.

Answer 2

Tomar un icosaedro regular cuyas aristas son de longitud de unidad.

Cualquier $n > 1$, subdividir cada uno de su rostro en triángulo equilátero de la $n^2$ % de la longitud de borde $1/n$. Se puede obtener un poliedro con $10 n^2 + 2$ vértices, bordes de #% de #% % y $30n^2$ caras.

Mediante la proyección estereográfica desde el centro de una de su cara, es fácil ver los vértices y aristas de esta figura es un gráfico planar. Además de los vértices originales de $20 n^2$, el otro $12$ los vértices tienen grado $10(n^2 - 1)$.