¿El grafo planar de 4 caras es único?

Question

Estoy trabajando en un proyecto para una clase y como parte de ese proyecto decidí (previamente) hacer el siguiente problema de nuestro libro de texto, Combinatoria y teoría de grafos 2ª ed. de Harris, Hirst y Mossinghoff.

Encuentre un grafo planar de 4 regularidades, y demuestre que es único.

(Ahora que estoy publicando esto, usaré un problema diferente para mi proyecto, tanto si consigo ayuda en esto como si no). El problema que tengo es que no me creo esto. "4-regular" significa que todos los vértices tienen grado 4. Una representación "planar" de un gráfico es aquella en la que las aristas no se cruzan (excepto técnicamente en los vértices). A continuación se muestran dos grafos planares de grado 4 que no parecen ser iguales, ni siquiera isomorfos. El primero viene de este post y el segundo viene de este post .

¿Qué ocurre? ¿Me estoy perdiendo algo trivial?

Answer 1

Incluso si fijamos el número de vértices, la $4$ -grafo plano regular de ese orden (número de vértices) puede no ser único. Según obra de Markus Meringer , autor de GENREG los únicos pedidos para los que existe un único gráfico de este tipo son probablemente $n=6,8,9$ .

Un gráfico antiprisma con $2n$ vértices se puede dar como ejemplo de un grafo poliédrico (y por tanto regular) transitivo de vértices (y por tanto plano).

El antiprisma pentagonal tiene este aspecto:

Hay una diferente (no isomorfa) $4$ -regular con diez vértices, es decir, el dipirámide cuadrada alargada :

El no isomorfismo de los grafos puede demostrarse contando aristas de barrios abiertos en los dos gráficos. La vecindad abierta de cada vértice del antiprisma pentagonal tiene tres aristas que forman un camino simple. En la dipirámide cuadrada alargada algunas vecindades abiertas tienen dos aristas que forman un camino y otras tienen cuatro aristas que forman un ciclo.

Notas sobre los pequeños casos de vértice impar

El único $4$ -grafo regular en cinco vértices es $K_5$ que, por supuesto, no es planar.

Inexistencia de cualquier $4$ -grafo planar regular en siete vértices fue el tema de esta pregunta anterior .

Singularidad de la $4$ -grafo planar regular en nueve vértices se mencionó en esta respuesta anterior . La elegante ilustración de abajo, el dual de el gráfico Herschel es de un artista/blogger que se hace llamar 11011110 :

Answer 2

Sé que lo pregunté hace tiempo, pero como esta pregunta parece llamar la atención de vez en cuando, pensé que debía publicarla.

He encontrado un enlace de erratas que funciona para este libro (Antes no podía) y resulta que a la pregunta le faltaba algo de información. http://www.appstate.edu/~hirstjl/bib/CGT_HHM_2ed_errata.html

Aquí está la parte relevante del enlace, el énfasis en las partes que faltan es mío:

• p. 80, el ejercicio 10 de la sección 1.5.2 debe decir "Hallar un gráfico planar de 4 regularidades con regiones triangulares y demostrar que es único".