Teoría de grafos: teoremas y conceptos sobre planaridad, Hamilton y bipartición

Ejercicio 1. Verdadero/Falso razonado

a) Si G es un grafo plano con 14 aristas, es regular y tiene un vértice de grado 4, entonces G tiene necesariamente 9 caras.

Respuesta: Cierta.

Por la ley de los emparejamientos de grados (suma de los grados igual a dos veces el número de aristas) se tiene 2|E| = 28. Si G es regular de grado 4, entonces 4n = 28, donde n es el número de vértices. De ello n = 7.

Aplicando el teorema de Euler para grafos planos: n - m + f = 2, donde m = 14 y f es el número de caras. Así, 7 - 14 + f = 2, por lo que f = 9. Por tanto, la afirmación es verdadera.

b) Si n ≥ 3 y K_n es el grafo completo de n vértices, entonces es hamiltoniano siempre y nunca es bipartido.

Respuesta: Cierta.

Si los vértices son v1, v2, …, v_n, al ser K_n completo existe siempre el ciclo v1 v2 … v_n v1, que es un ciclo hamiltoniano (se necesita n ≥ 3 para que sea un ciclo). Por tanto, K_n es hamiltoniano para n ≥ 3.

Además, en K_n siempre aparece el triángulo v1 v2 v3 v1 (un ciclo de longitud 3), que es un ciclo de longitud impar; por el criterio de bipartición (un grafo es bipartito si y sólo si no contiene ciclos de longitud impar), K_n no puede ser bipartito cuando n ≥ 3. Así que la segunda parte también es cierta.

c) Todo grafo conexo tiene un número impar de vértices de grado par.

Respuesta: Falsa.

Contraejemplo: sea G = (V,E) con V = {1,2,3,4} y aristas {1,2}, {1,3}, {1,4}, {2,4} y {2,3}. El camino 2-3-1-4 conecta todos los vértices, luego G es conexo. Los vértices 3 y 4 son los únicos de grado par (grado 2 cada uno), es decir, hay dos vértices de grado par; por tanto, el número de vértices de grado par no es necesariamente impar. Otro ejemplo: un cuadrado tiene 4 vértices de grado 2 y es conexo.

Observación: por la fórmula del apretón de manos, el número de vértices de grado impar en cualquier grafo es siempre par; esto implica que la paridad del número de vértices de grado par puede variar según el grafo (no tiene por qué ser siempre impar).

d) Toda arista de un árbol es una arista separadora.

Respuesta: Cierta.

Sea T un árbol y sea ab una arista de T. Si al eliminar la arista ab los vértices a y b permanecieran conectados, existiría un camino distinto de a a b en T; uniendo ese camino con la arista ab obtendríamos un ciclo, lo cual contradice la definición de árbol (un árbol no contiene ciclos). Por tanto, la eliminación de cualquier arista en un árbol aumenta el número de componentes conexas: cada arista es una arista separadora (también llamada puente).

Ejercicio 2. Definiciones

• Grafo dirigido conexo: Un grafo dirigido se llama fuertemente conexo (o, en algunos contextos, simplemente dirigido conexo) si existe un camino dirigido desde cualquier vértice i hasta cualquier otro vértice j. Es decir, para todo par (i,j) hay un camino dirigido de i a j.
• Subárbol generador de un grafo: Un subárbol generador (o árbol generador, spanning tree) de un grafo conexo G es un árbol T que es subgrafo de G y que contiene todos los vértices de G.
• Matriz de adyacencias de un grafo: Para un grafo G con vértices {1,2,…,n}, la matriz de adyacencias es la matriz cuadrada A de orden n tal que la entrada A_{i,j} indica el número de aristas que van del vértice i al vértice j. En grafos simples no dirigidos A_{i,j} ∈ {0,1} y A es simétrica.
• Componente conexa de un grafo: Una componente conexa de un grafo G es un subgrafo conexo maximal de G, es decir, un subgrafo conexo que no está contenido en ningún otro subgrafo conexo propio de G.

Ejercicio 3. Enunciados

a) Teorema de caracterización de grafos bipartidos

Enunciado corregido: Un grafo G es bipartido si y sólo si no contiene ciclos de longitud impar. (Para grafos desconexos, esto se verifica en cada componente conexa.)

b) Teorema de Kuratowski

Enunciado corregido: Un grafo finito es plano si y sólo si no contiene ningún subgrafo que sea una subdivisión (homeomorfo) de K5 ni de K3,3. Aquí, K5 es el grafo completo sobre 5 vértices y K3,3 es el grafo bipartido completo con dos partes de 3 vértices cada una.

Nota sobre contracciones y subdivisiones: una contracción elemental de una arista consiste en identificar sus extremos en un único vértice (eliminando la arista y fusionando los dos vértices); un grafo es contráctil a otro si el segundo puede obtenerse del primero mediante una sucesión finita de contracciones elementales. La formulación clásica de Kuratowski utiliza subdivisiones (homeomorfismos); existe un resultado relacionado (el teorema de Wagner) que caracteriza planitud mediante menores (contracciones) prohibiendo K5 y K3,3 como menores.