Restricciones sobre los grados de los vértices de un grafo | Tangente

Para todo conjunto S = { X₁, X₂… X*_n *} con X₁ > X₂… > X*_n* > 0, debemos construir un grafo G que tenga exactamente X₁ + 1 vértices y tal que deg(G) = S. La construcción se realiza por inducción sobre el número n de enteros de S.

El caso base es sencillo. Sea un conjunto compuesto por un único número entero: S = {x}, con x > 0. Consideremos el grafo completo K*_x*₊₁. Cada uno de sus x +1 vértices tiene grado x y es adyacente a los otros x vértices. K*_x*₊₁ satisface las condiciones cuando la cardinalidad de S es 1.

Para todo conjunto S de cardinalidad n, escribimos S = {X₁, X₂… X*_n *} con X₁ > X₂… > X*_n* > 0. Nuestra hipótesis de inducción es que existe un grafo G con X₁ + 1 vértices y deg(G) = S. Tomemos ahora un conjunto cualquiera T = {Y₁, Y₂… Y*_n , Y_n*₊₁ } de cardinalidad n + 1, con Y₁ > Y₂… > Y*_n > Y_n*₊₁ > 0.

Construyamos S’ = {Y₁ – Y*_n*₊₁, Y₁ – Y*_n *… Y₁ – Y₂ } a partir de T. Se tiene Y₁ – Y*_n*₊₁ > Y₁ – Y*_n* >… > Y₁ – Y₂ > 0; por tanto, S’ es un conjunto de n números enteros positivos. Por hipótesis de inducción, existe entonces un grafo H que tiene Y₁ – Y*_n*₊₁ + 1 vértices y satisface deg(H) = S’. Añadamos a este grafo H un conjunto C de Y*_n*₊₁ nuevos vértices, sin ninguna arista. El grafo así obtenido, denotado H⁺, tiene Y₁ – Y*_n*₊₁ + 1 + Y*_n*₊₁ = Y₁ + 1 vértices.

Para obtener el grafo G buscado, basta con considerar el complementario del grafo H⁺. ¿Cuáles son las características de G? Al igual que H⁺, tiene Y₁ + 1 vértices. Calculemos sus grados. Por construcción, cada uno de los Y*_n*₊₁ vértices de C está conectado con todos los demás vértices de G, es decir, con Y₁ vecinos. G contiene al menos un vértice de grado Y₁.

Mostremos que, para todo j en {2, 3… n+1}, G también contiene al menos un vértice de grado Y*_j*. El grafo H (y por tanto H⁺) contiene al menos un vértice u de grado Y₁ – Y*_j . En el complementario G, este vértice u* es adyacente a los Y₁ + 1 vértices, salvo a u mismo y a sus «antiguos» Y₁ – Y*_j* vecinos.

El grado de u en G es, por tanto, Y₁ + 1 – 1 – ( Y₁ – Y*_j ), es decir, Y_j *.

Para concluir, solo queda comprobar que G no contiene ningún vértice cuyo grado no pertenezca a T. Por tanto, G reúne todas las características requeridas.

El complementario de un grafo ------------------------------

Para todo grafo H, el complementario G de H es el grafo definido de la siguiente manera. G posee exactamente los mismos vértices que H y, para cada par {u, v } de vértices, si H contiene una arista entre u y v, G no la contiene; y si H no contiene esa arista, G sí la contiene.