Gráfico cerrado a partir de una colección de vértices

Question

Digamos que tengo dos tipos de vértices:

• (D) los vértices tienen dos aristas
• (T) los vértices tienen tres aristas

Dada una colección de estos vértices, ¿hay alguna manera de demostrar si se pueden unir borde a borde para formar un grafo cerrado (es decir, sin aristas libres) en el espacio 3?

Por ejemplo, digamos que tengo 3 vértices (T) y 1 vértice (D). (A no ser que me haya perdido algo obvio) no hay manera de unir estos vértices en un grafo cerrado en el espacio, pero no soy capaz de encontrar una prueba. Por otro lado, 4 vértices (T) y 0 vértices (D) forman un tetraedro simple.

¿Qué pasa con los ejemplos de orden superior, como 12 (T) vértices y 4 (D) vértices? Lo ideal sería poder construir un ejemplo de grafo en los casos en que existen, al menos para colecciones pequeñas como éstas, pero esto no está etiquetado para constructive-mathematics porque no considero que la construcción sea un requisito absoluto.

Answer 1

Afirmación: Un gráfico compuesto exactamente por $t$ vértices de grado $3$ y $d$ vértices de grado $2$ y ningún otro vértice existe si y sólo si se cumplen las siguientes condiciones:

• $t$ es incluso
• $t+d\geq 4$

o

• $t=0,d=3$

Un esbozo de una prueba:

La condición de que $t$ debe ser uniforme se ve inmediatamente desde el lema del apretón de manos . Que $t=0,d=3$ funciona se ve en el ejemplo $K_3$ . Que ningún otro gráfico con menos de cuatro vértices funciona es obvio.

Lo que queda es demostrar que cualquier otro puede ser creado. Lo hacemos por inducción. $K_4$ , $C_4$ y el gráfico del diamante $K_4-e$ funcionan como ejemplos de casos base.

Dado un gráfico con $t$ vértices de grado tres y $d$ vértices de grado $2$ podemos aumentar el número de vértices de grado $2$ por uno, sustituyendo cualquier arista $\{u,v\}$ con dos nuevas aristas y un vértice entre ellas: $\{u,x\},\{x,v\}$ como en la foto de abajo:

se convierte:

Para aumentar el número de vértices de grado $3$ por dos, podemos tomar dos aristas distintas cualesquiera y reemplazarlas ambas como en el caso anterior, con el paso adicional de conectar los dos vértices recién creados, como se muestra a continuación:

se convierte en

( Nota: sólo exigimos que las aristas sean distintas, pero pueden compartir un vértice si se desea. No pueden compartir dos vértices ya que, de lo contrario, las aristas no habrían sido distintas en primer lugar. )

Debe quedar claro que los grafos recién creados utilizando cualquiera de estas modificaciones serán un grafo con el número deseado de vértices de grado $3$ y $2$ y los grados de los vértices del gráfico original no se modifican con el proceso.

Se deduce entonces por inducción que toda elección de $t,d$ posible cuando $t$ es par y $t+d\geq 4$ conduce a la construcción de un gráfico con $t$ vértices de grado $3$ y $d$ vértices de grado $2$ sin otros vértices.

---

Como ejemplo de la puesta en práctica de las ideas anteriores, usted pregunta por $d=4,t=12$ . El siguiente gráfico se ha creado con $C_4$ como base, y aplicando repetidamente las modificaciones descritas en el argumento de inducción. ( incluso puedes ver exactamente el orden en el que se aplicaron si te fijas en cómo están etiquetados los vértices, ya que sólo utilicé los nombres por defecto para los vértices tal y como fueron creados )

Por supuesto, este no es el único ejemplo de un gráfico con $d=4$ y $t=12$ pero es de esperar que ponga de manifiesto cómo podría producirse esa construcción.