En este post presento algunos resultados básicos y teoremas sencillos que surgen a partir de la estructura matemática que conocemos como gráficas, o grafos en otros países.

Asumiré que el público tiene un conocimiento básico (o por lo menos intuitivo) de lo que son las gráficas. De no ser así, te invito a leer mi post anterior: Introducción a la Teoría de Gráficas.

Si $G \cong H$, entonces $|V(G)|=|V(H)|$, $|E(G)|=|E(H)|$, y la sucesión de grados de $G$ es igual a la sucesión de grados de $H$.

Recordando que $V(G)$ se refiere al conjunto de vértices de $G$, queremos demostrar que si dos gráficas son isomorfas, tales gráficas tienen la misma cantidad de vértices.

Decimos que dos gráficas son isomorfas cuando:

  1. Existen las biyecciones $\theta : V(G) \longrightarrow V(H)$ y $\phi : E(G) \longrightarrow E(H)$

  2. Se cumple que $\psi_{G}(e) = uv$ si y solo si $\psi_{H}(\phi(e))=\theta(u)\theta(v)$.

Por lo tanto, se sigue que como $G \cong H$, existen las biyecciones $\theta$ y $\phi$. Sabemos que las biyecciones tienen dominio y codominio de la misma cardinalidad. Por lo tanto, se cumple que $|V(G)|=|V(H)|$ y $|E(G)|=|E(H)|$.

Solo queda demostrar que la sucesión de grados es la misma para ambas gráficas. Por el punto 2 de la definición de isomorfismo, sabemos que las aristas de las gráficas van de los vértices relacionados bajo la biyección $\theta$, por lo tanto tienen los mismos grados. Al ordenarlos de menor a mayor, tenemos que la sucesión para ambas gráficas es igual, y queda demostrada la proposición.

Si $G$ no es conexa, entonces $G^{c}$ es conexa.

Sean $u, v \in V(G)$. Luego, tenemos dos casos:

  • Caso $uv \notin E(G)$: Como $uv$ no son adyacentes en G, $uv \in E(G^{c})$.

  • Caso $uv \in E(G)$: Como existe arista en $G$ entre $u$ y $v$ sabemos que ambos vértices están en el mismo componente. Sea $w \in V(G)$ en un componente distinto al de $u$ y $v$ en $G$. Sabemos que $uw, vw \in E(G^{c})$, por lo tanto existe el camino $(u,w,v)$ y sabemos que los vértices están conectados en $G^{c}$.

De los dos casos anteriores, sabemos que se cumple la proposición.

Una gráfica simple $G$ es autocomplementaria si $G \cong G^{c}$. Si $G$ es autocomplementaria, entonces alguno de $|V(G)|$ o $|V(G)|-1$ es múltiplo de $4$.

Dado que $G$ es autocomplementaria, sabemos que $G$ es isomorfa con su complemento. Por comodidad, digamos que $n = |V(G)|$ (el número de vértices).

Tenemos entonces que:

$$ |E(G)|=|E(G^{c})|=\frac{|E(K_{n})|}{2} $$

El número de aristas que tiene una gráfica autocomplementaria (y su complemento) es la mitad que el número de aristas de la gráfica completa con $n$ vértices.

Una de las propiedades que cumplen las gŕaficas completas, es que tienen la misma cantidad de aristas que las combinaciones de sus vértices en 2. Escrito en notación:

$$ |E(K_{m})| = \binom m 2 = \frac{m!}{2!(m-2)!}=\frac{m(m-1)}{2} $$

Con lo anterior, sabemos que el número de aristas de $G$ y de $G^{c}$ es igual a:

$$ \frac{|E(K_{n})|}{2} = \frac{1}{2}\frac{n(n-1)}{2} = \frac{n(n-1)}{4} $$

Finalmente, dado que nuestras gráficas viven en un universo discreto, sabemos que el resultado anterior debe dar un número entero, por lo que $n$ o $n-1$ debe ser múltiplo de $4$, para que nuestro resultado sea un número entero.

$G$ es conexa si y solo si para cada partición de $V(G)$ en dos conjuntos $V_{1}$ y $V_{2}$ existe una arista conectando un vértice de $V_{1}$ a un vértice de $V_{2}$.

Si $G$ es conexa, sabemos que entre cualesquiera dos vértices $u, v$ existe un camino $(u, \dots, v)$. Por lo tanto, en cualquier bipartición con $V_{1}$ y $V_{2}$ debe haber al menos dos vértices (uno en cada partición) conectados entre sí. De otra manera, existirían $v_{1} \in V_{1}$ y $v_{2} \in V_{2}$ tal que no hay camino $(v_{1}, \dots, v_{2})$ entre ellos.

La otra implicación es un poco menos trivial, pero tampoco es difícil. Sean $V_{1}$ y $V_{2}$ los conjuntos de una bipartición arbitraria de los vértices de $G$.

Veamos qué sucede con la siguiente bipartición:

$$ V_{1}=\lbrace v_{1} \rbrace $$

$$ V_{2}=V(G) \setminus V_{1} $$

Por hipótesis tenemos que $v_{1}$ está conectado con algún vértice en $V_{2}$. Si repetimos el mismo argumento para todos los vértices de $G$, tenemos que todos los vértices están en el mismo componente, y por lo tanto $G$ es conexa.

¿Cuál es la mayor cantidad de aristas que puede tener una gráfica disconexa?

Es evidente que la gráfica disconexa con mayor cantidad de aristas, es la gráfica con solo un vértice desconectado.

Por lo tanto, si nuestra gráfica tiene $n$ vértices, la gráfica disconexa con mayor cantidad de aristas tendría:

$$ \frac{1}{2} \sum_{i=1}^{n-1} deg(v_{i}) $$

Donde $deg(v)$ es el grado del vértice $v$. Además, tenemos que el grado de cualquier vértice (excepto el que no estamos contando, que tiene grado 0) es $n-2$. Por lo tanto:

$$ \frac{1}{2} \sum_{i=1}^{n-1} n-1 = \frac{1}{2}(n-2)(n-1) = \binom{n-1}{2} $$

Si $|V(G)|$ es par y todos los vértices tienen grado al menos $\frac{|V(G)|}{2}$, entonces $G$ es conexa.

Tenemos que el número de vértices de la gráfica es par, es decir, $|V(G)|=2x$. Luego, todos los vértices tienen grado al menos $x$:

$$ \forall v \in V(G)\left( deg(v) \geq x \right) $$

A manera de contradicción, supongamos que lo anterior se cumple, pero $G$ no es conexa.

Entonces, debe existir un componente en $G$ que tiene a lo más $x$ vértices por no ser conexa. Se sigue que entonces, hay un vértice en ese componente que tiene grado menor a $x$, por el principio del palomar. Y esa es nuestra contradicción, que viene de suponer que $G$ no es conexa.

Cualesquiera dos trayectorias de longitud máxima en una gráfica conexa tienen un vértice en común.

Sea $l$ la longitud de las dos trayectorias de longitud máxima:

$$ P_{1} = (u_{1}, \dots, u_{l}) $$

$$ P_{2} = (v_{1}, \dots, v_{l}) $$

Para proceder por contradicción, supongamos que $P_{1}$ y $P_{2}$ no comparten vértices.

Como $G$ es conexa, podemos encontrar un vértice $u_{i}$ y un vértice $v_{j}$ de manera que podemos formar la trayectoria $P_{3}$ entre ellos, sin que $P_{3}$ comparta vértices con $P_{1}$ y $P_{2}$ además de $u_{i}$ y $v_{j}$.

Si $i\geq \frac{l}{2}$, entonces diremos que $P_{1}^{\prime}=(v_{1}, \dots, v_{i})$, de otra manera $P_{1}^{\prime}=(v_{i}, \dots, v_{l})$. Para $j$ hacemos lo mismo: si $j\geq \frac{l}{2}$ entonces $P_{2}^{\prime}=(v_{1}, \dots, v_{j})$ y si no $P_{2}^{\prime}=(v_{j}, \dots, v_{l})$

Ahora, vamos a crear la trayectoria $P_{1}^{\prime} \cup P_{3} \cup P_{2}^{\prime}$. Esta trayectoria va a tener longitud mayor a $l$, y he ahí nuestra contradicción.

Una gráfica es bipartita si y solo si no tiene ciclos de longitud impar.

Sea $G$ una gráfica bipartita, y a manera de contradicción, supongamos que tiene un ciclo $C$ de longitud impar.

$$ C=(v_{1}, v_{2}, \dots, v_{2n+1}, v_{1}) $$

Luego, veamos cómo estarían ordenados los vértices en los dos conjuntos $V_{1}$ y $V_{2}$ de la bipartición.

Diremos que todos los vértices impares van en $V_{1}$ y los vértices con índice par en $V_{2}$. No obstante, el vértice $v_{2n+1}$ a pesar de ser impar, no puede ir en $V_{1}$ pues es adyacente al vértice $v_{1}$ que también es impar. De la misma manera es adyacente al vértice $v_{2n}$ que es par, por lo que no puede ir en $V_{2}$. Llegamos a una contradicción, pues no podemos generar una bipartición.

Para la implicación de regreso suponemos que no existen ciclos de longitud impar. Tomamos un vértice arbitrario de la gráfica $u$, y vamos a utilizarlo para gener nuestra bipartición:

$$ V_{1} = \lbrace v \in V(G) | \text{la trayectoria más corta entre } v \text{ y } u \text{ es de longitud impar} \rbrace $$

$$ V_{2} = \lbrace v \in V(G) | \text{la trayectoria más corta entre } v \text{ y } u \text{ es de longitud par} \rbrace $$

Además, $u \in V_{2}$ pues su distancia a sí mismo es $0$, que es par. Podemos realizar el proceso anterior con todos los componentes de $G$. Entonces, hemos formado nuestra bipartición $V(G) = V_{1} \uplus V_{2}$.

Además, veamos que no pueden existir $v, w \in V_{1} \vee v,w \in V_{2}$ tal que $vw \in E(G)$. Supongamos que sí existen, entonces el camino:

$$ C = (u, \dots, v, w, \dots, u) $$

es un ciclo, y además es de longitud impar. Esto es porque la suma de dos números pares es siempre par, y la suma de dos números impares siempre es par. Por lo tanto, la distancia de $u$ a $v$ y de $u$ a $w$ siempre es par, más la arista entre $v$ y $w$, nos da un camino de longitud impar, contradiciendo nuestra suposición original.

Una gráfica bipartita con $n$ vértices tiene a lo más $\frac{n^{2}}{4}$ aristas.

Como nuestra gráfica tiene $n$ vértices, los conjuntos de la partición tienen cardinalidad $a$ y $b$ donde $a+b=n$. Además, la máxima cantidad de aristas que puede tener nuestra gráfica por ser bipartita será $a \cdot b$.

Fácilmente podemos verificar que el valor de esta función se maximiza cuando $a=b=\frac{n}{2}$ si $n$ es par, o cuando $a=\frac{n-1}{2}, b=\frac{n}{2}$ si $n$ es impar. La optimización se puede comprobar fácilmente haciendo uso de cálculo, aunque en realidad solo toma realizar un par de ejemplos para convencerse del comportamiento de la función (esta parte queda como ejercicio al lector).

Luego, si $n$ es par, y tomando en cuenta que $a\leq \frac{n}{2}$ y $b\leq\frac{n}{2}$:

$$ |E(G)| = a \cdot b \leq \frac{n}{2} \cdot \frac{n}{2} = \frac{n^{2}}{4} $$

Si $n$ es impar, $a\leq \frac{n-1}{2}$ y $b\leq \frac{n}{2}$:

$$ |E(G)|=a \cdot b < \frac{n-1}{2} \cdot \frac{n}{2} < \frac{n^{2}}{4} $$

Por lo tanto, se cumple la proposición que buscábamos demostrar.

Si una arista $e$ está en un paseo cerrado de $G$, entonces $e$ está en un ciclo de $G$.

La definición de paseo nos dice que este es una secuencia de vértices adyacentes en donde no se repiten aristas. Además, por ser cerrado, comienza en el mismo vértice en el que comenzó. Mientras tanto, un ciclo no puede repetir aristas.

Podemos describir nuestro paseo como:

$$ P = (v_{1}, v_{2}, \dots, v_{i}, v_{j}, \dots, v_{1}) $$

Recordemos que los vértices pueden estar repetidos en $P$. Además, $e=v_{1}v_{2}$

Haremos lo siguiente. Cada vez que encontremos el siguiente patrón:

$$ P =(\dots, v_{x}, v_{y} \dots, v_{z}, \dots) $$

Donde $y=z$, lo vamos a reducir de la siguiente manera comenzando por los vértices de menor índice:

$$ P=(\dots, v_{x}, v_{z}, \dots) $$

Al final, vamos a terminar con un ciclo, pues eliminamos todos los vértices repetidos, y $e$ sigue en el ciclo, pues al comenzar por los vértices de menor índice, nos aseguramos de que $v_{1}$ continúe siendo adyacente a $v_{2}$, formando la arista $e$.


Estos son algunos resultados básicos de teoría de gráficas. Para poder entender la notación, te recomiendo leer mi otro post Introducción a la Teoría de Gráficas, en donde te presento lo que son las gráficas y algunos conceptos que son de utilidad al momento de estudiar los teoremas presentados.