¿Existen grafos planos conectados de tamaño $N$ con un grado mínimo $\left( N−2 \right)$ para cualquier $N \in \mathbb{N}$ ?

Question

Hoy estuve haciendo un poco de garabatos con grafos de N vértices, tratando de que cada vértice tuviera un grado mínimo de $\left( N-2 \right)$ sin ningún cruce. Pude formar gráficos para $N=3$ , $N=4$ , $N=5$ y $N=6$ casos, pero no encuentro la manera de hacerlo para los $N=7$ caso. A continuación se presentan las soluciones para el $N=4$ a través de $N=6$ casos:

Aquí hay algunas preguntas que tengo:

1. ¿Es imposible dibujar un gráfico de este tipo con $N=7$ ¿y no hay cruces?
2. Si no es así, ¿cuál es el número mínimo de cruces $C(N)$ ¿es necesario?
3. ¿Existe una generalización sencilla para $N$ puntos y grado mínimo de $\left( N-m \right)$ por vértice? Sobre todo tengo curiosidad por saber si existe una expresión de forma cerrada para el límite superior en función de $m$ .

Un problema algo relacionado:

• Puzzle de agua, gas y electricidad

Answer 1

Contratando dos pares de vértices se obtiene un menor que es un $K_5$ gráfico. Entonces Teorema de Wagner estados:

Un gráfico finito es planar si y sólo si no tiene $K_5$ o $K_{3,3}$ como menor de edad.

Answer 2

Puedo responder a la pregunta $1$ para ti. A partir de esto verás cómo responder a la pregunta $3$ por ti mismo.

Supongamos que tenemos un grafo simple, conectado y plano con $N$ vértices y $e$ aristas con grado de vértice mínimo $N-2$ .

Entonces el lema del apretón de manos dice:

$N(N-2)\leq 2e$

Pero también sabemos para tales gráficos que si $N\geq 3$ entonces $e\leq 3N-6$ (ver http://en.wikipedia.org/wiki/Planar_graph ).

Así, para nuestro gráfico tenemos:

$N(N-2) \leq 6N - 12$ .

La resolución da $N \leq 6$ como has notado en tu experimento.

ACTUALIZACIÓN:

Para responder a la pregunta $2$ hacer uso de la desigualdad $\text{cr}(G) \geq e-3N+6$ (véase la prueba de la desigualdad del número de cruce en http://en.wikipedia.org/wiki/Crossing_number_(teoría_gráfica) ).

Esta desigualdad más nuestra desigualdad anterior sobre $2e$ nos dice que $\text{cr}(G) \geq \frac{N(N-2)}{2} - 3N + 6$ que para $N=7$ sugiere que nunca se dibujará un gráfico de este tipo sin necesitar $3$ o más cruces. No sé si esto es óptimo.

Obsérvese que esta desigualdad numérica de cruce sólo nos dice que $\text{cr}(G)\geq 0$ para $N\leq 6$ ¡como se esperaba!

De nuevo esta desigualdad es siempre cierta y por tanto se puede hacer lo mismo para el número mínimo de cruces para el grado mínimo $(N-m)$ .