¡¡Estoy estudiando para mi examen final y el profe me sugirió este problema.. así que agradecería mucho la ayuda!! ¡Gracias!
Dejemos que $G$ ser no nulo, simple y plano, sin ningún vértice de grado menor o igual a $4$ .
a) ¿Es cierto que $G$ debe tener dos vértices de grado $5$ que están unidas por un camino de longitud $< 10^6$ ?
b) ¿Es cierto que si el número de vértices de $G$ es mayor que $10^6$ entonces $G$ tiene mayor o igual que $13$ vértices de grado $5$ ?
Parte a.)
No es cierto. Empieza con el gráfico del icosaedro - un gráfico planar de 5 regulares, además una triangulación. Luego subdivide todos los segmentos añadiendo un vértice. Conecta los nuevos vértices de cada cara, mediante un ciclo. Los nuevos vértices tienen grado 6. Los antiguos vértices de grado 5 tienen ahora distancia 2. Ahora repite esta construcción. Cada vez duplicas la distancia entre los vértices originales de grado 5. Así que puedes hacer que la distancia entre estos vértices sea arbitrariamente larga.
La imagen muestra el primer paso de la construcción. 
Parte b.)
No es cierto. Por la fórmula de Euler y el lema del apretón de manos se puede demostrar que tiene que haber al menos 12 vértices de grado 5. Pero esto sí es suficiente. He aquí una construcción que demuestra que hay grafos planos infinitamente grandes con 12 vértices de grado 5 y todos los demás vértices de grado 6: Tomemos un triángulo $m\times 6$ y envolverlo identificando el $m$ -borde de vértice. A continuación, inserta una pirámide en cada uno de los dos pentágonos restantes. El gráfico de la parte a sería también un ejemplo.
(Imagen extraída de la tesis doctoral de Ares Ribó).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
