Sobre grafos y palomas

Hablemos sobre palomas.

El principio del palomar establece que tengo algunas palomas y algunos nidos para ubicarlas. Si la cantidad de palomas supera a la cantidad de nidos, al menos dos palomas tendrán que compartir habitáculo.

En términos matemáticos, si
\( A=\{a_1,a_2, \ldots,a_n\} \) y \( B=\{b_1,b_2, \ldots, b_m\} \) con \( m < n \), y si \( f: A \to B \), entonces existen \( 1 \leq i,j \leq n \) con \( i \neq j \) tales que \( f(a_i)=f(a_j) \). Para terminar de cerrar la analogía, \( a_i, a_j \) son las palomas y la imagen por \( f \) es el nido que comparten.

En otras palabras, la función \( f \) no es inyectiva, ya que a puntos distintos del dominio corresponden idénticas imágenes.

Principio del palomar. El enunciado se sintetiza de la siguiente forma. Si \( f: A \to B \) con \( |A|=n > m = |B| \), entonces \( f \) no es inyectiva.

Veremos cómo usar este resultado para probar la siguiente propiedad de los grafos simples.

Enunciado. Consideremos \( G=\langle V, A \rangle \) un grafo simple con \( |V|>1 \). Llamamos \( A \) al conjunto de aristas y \( V \) al conjunto de vértices. Afirmamos entonces que existen al menos dos vértices que poseen la misma valencia.

Observación. Analicemos la situación para grafos no dirigidos. Las aristas del grafo son subconjuntos de dos vértices. Por lo tanto, \( A \subseteq \mathcal{P}_2(V) \), donde el subíndice indica que, de entre toda la colección de subconjuntos de \( V \), sólo me quedo con los subconjuntos que tienen exactamente dos elementos.

Una pregunta válida es cuántas aristas puede tener un grafo. Si suponemos que \( A = \mathcal{P}_2(V) \), y el grafo posee \( n \) vértices, la cantidad de aristas es la cantidad de subconjuntos de dos elementos tomados de un conjunto de \( n \) elementos. Es decir, \( |A|=\binom{n}{2} \).

Veamos que esto se relaciona de alguna forma con las valencias de los vértices.

\[ \binom{n}{2} = \frac{n!}{2!(n-2)!} = \frac{n(n-1)(n-2)!}{2!(n-2)!} = \frac{n(n-1)}{2} \]

Cada vértice \( v \) puede estar conectado a los restantes \( n-1 \) vértices, y como esto vale para los \( n \) vértices tenemos en total \( n(n-1) \). Pero cada vez que conecto un vértice \( v \) con otro \( w \) y recorro el conjunto de todos los vértices, estoy contando dos veces la arista que los conecta. Por lo tanto, he de partir todo en dos para obtener la cantidad real de aristas del grafo.

Esto me da una muy buena indicación. Cada vértice puede conectarse como mucho con \( n-1 \) vértices. ¿Podría no conectarse con ningún otro vértice? Como estamos en el caso de un grafo simple, no existen vértices aislados (con valencia nula).
Así, para cada \( v \in V \) estamos en la condición de \( 1 \leq \deg(v) \leq n-1 \). Estamos en condiciones de dar la prueba.

Demostración. Llamemos \( \mathrm{Gr}(V) \) al conjunto de valencias de vértices de un grafo simple; tenemos \( \mathrm{Gr}(V)=\{1,2,3,\ldots,n-1\} \), mientras que \( V=\{v_1,v_2,v_3,\ldots,v_n\} \) es el conjunto de vértices del grafo.
Tomemos entonces \( f \) que asigna a cada vértice su valencia. Es decir, \( f:V \to \mathrm{Gr}(V) \). Como \( |V|=n > n-1 = |\mathrm{Gr}(V)| \), en virtud del principio del palomar, se tiene que \( f \) no es inyectiva. Luego existen \( v_i \neq v_j \) vértices tales que \( f(v_i)=f(v_j) \). Y como \( f \) asigna a cada vértice su valencia, observamos que hay al menos dos vértices que tienen la misma, como queríamos probar.