Capítulo 4

Teoría de grafos
Los grafos son modelos matemáticos utilizados para representar relaciones entre objetos de un
conjunto, generalizando el concepto de relación binaria. Utilizamos grafos para estudiar conexiones
entre objetos, datos o fuentes de información. Un ejemplo de grafo lo encontramos en las redes de
carreteras, dónde las poblaciones se enlazan o conectan con una o varias carreteras. Las redes de
ordenadores también se pueden representar y estudiar mediante grafos.

4.1. Conceptos elementales de la teoría de grafos

La teoría de grafos surge en el siglo XVIII de la mano de Euler tras dar solución al problema de
los puentes de Königsberg, el cual consistía en encontrar un camino que recorriera los siete puentes
del río Pregel, en la ciudad de Königsberg (Kaliningrado actualmente), de modo que se cruzaran
todos los puentes pasando una sola vez por cada uno de ellos.

Este problema puede plantearse a partir de un esquema del mapa anterior

62
CAPÍTULO 4. TEORÍA DE GRAFOS 63

que Euler representó de la siguiente forma

dando lugar al nacimiento de la teoría de grafos.

4.1.1. Grafos, digrafos y multigrafos

Denición 4.1.1. Un grafo simple G G = (V, E), donde V es un conjunto
es un par ordenado
cuyos elementos se denominan vértices y E es un conjunto de subconjuntos de dos elementos de
V , es decir, E ⊆ {{u, v} : u, v ∈ V, u =
̸ v} (E es un conjunto de pares no ordenados de vértices
distintos). A los elementos de E se les denominan aristas (no dirigidas o no orientadas).

Observación 4.1.2. Que E sea un conjunto signica que no hay aristas repetidas. Además, la
condición u≠ v en el conjunto {{u, v} : u, v ∈ V, u ̸= v}, nos indica que en G no existen aristas
de la forma {u, u}, con u ∈ V .

Ejemplo 4.1.3. Consideremos G = (V, E), con V = {1, 2, 3, 4} y E = {{1, 2}, {1, 3}, {1, 4}}.
Entonces G es un grafo simple.

Observación 4.1.4. Podemos representar los vértices como puntos del plano y las aristas {u, v} como
el segmento uv dando una representación gráca del grafo. Conviene observar que la representación
no es necesariamente única. Por ejemplo podemos ver a continuación dos representaciones distintas
del grafo del ejemplo anterior.

Denición 4.1.5. Un multigrafo G es un par ordenado (V, E), donde V es un conjunto cuyos
elementos se denominan vértices y E es una familia de familias formadas por dos elementos de V.
A los elementos de E se les llaman arista s (no orientadas).
CAPÍTULO 4. TEORÍA DE GRAFOS 64

Observación 4.1.6. En un multigrafo, E es una familia (no un conjunto), con lo que G puede tener
varias aristas entre dos vértices. Además, un multigrafo G admite lazos (o bucles ), es decir, aristas
de la forma {u, u}, con u∈V.
Ejemplo 4.1.7.
1. Consideremos G = (V, E), donde V = {1, 2, 3} y E = {{1, 1}, {1, 2}, {1, 2}, {2, 3}}. En este
caso, G es un multigrafo.

2. El siguiente multigrafo G representa el problema de los puentes de Königsberg

V = {A, B, C, D} y E = {a, b, c, d, e, f, g}, donde a = {A, B},

donde el conjunto de vértices es
b = {A, B}, c = {A, C}, d = {C, A}, e = {A, D}, f = {B, D} y g = {D, C}.
Denición 4.1.8. Un digrafo G es un par ordenado (V, E) donde V es un conjunto y E ⊆ V ×V \∆,
siendo ∆ = {(u, u) : u ∈ V }. A los elementos de V se les denomina vértices y a los de E aristas
orientadas (o dirigidas ).

Observación 4.1.9. Como E ⊆ V ×V \∆, entonces cada arista es orientada por ser un par ordenado.
Además, al ser E un subconjunto de V × V \ ∆, entonces un digrafo no tiene lazos o bucles.
Ejemplo 4.1.10. G = ({a, b, c}, {(a, b), (a, c), (b, c), (c, b)}) es un digrafo que podemos representar
utilizando puntos para representar los vértices y echas para representar las aristas orientadas.
Nótese que la arista (b, c) es distinta de la arista (c, b), ya que se tratan de aristas orientadas.
CAPÍTULO 4. TEORÍA DE GRAFOS 65

Denición 4.1.11. Un multidigrafo G es un par (V, E), formado por un conjunto de vértices V
y una familia E formada por elementos de V ×V. A los elementos de E se les denominan arista s
orientadas.

Observación 4.1.12. Un multidigrafo G puede tener varias aristas orientadas entre dos vértices, ya
que E es una familia. Además, también puede tener lazos o bucles, es decir, aristas orientadas de
la forma (u, u), con u∈V.

Ejemplo 4.1.13. G = ({1, 2, 3}, {(1, 1), (1, 2), (2, 1), (3, 2)}) es un ejemplo de multidigrafo.

En lo que sigue, el término grafo se empleará en sentido general, para describir grafos con
aristas dirigidas o no dirigidas, con o sin lazos y con o sin aristas múltiples. Por otro lado, el
término grafo no dirigido se entenderá como sinónimo de multigrafo, admitiendo, por tanto, la
eventual existencia de aristas múltiples y lazos. De igual manera, el término grafo dirigido se
entenderá como multidigrafo.

Salvo especicación previa, trataremos con grafos nitos, es decir, el conjunto de vértices V
será un conjunto nito.

Dado un grafo G, es usual denotar al conjunto de vértices por V (G) y por E(G) al conjunto
de aristas de G.
CAPÍTULO 4. TEORÍA DE GRAFOS 66

Denición 4.1.14. Sea G = (V, E) un grafo no dirigido y sean u, v ∈ V . Diremos que los vértices
u y v son adyacentes si {u, v} ∈ E . En ese caso se dice que la arista e = {u, v} conecta los vértices
u y v , que e es incidente con los vértices u y v , y que los vértices u y v son los extremos de la
arista e.

Denición 4.1.15. Sea G = (V, E) un grafo no dirigido y sea u ∈ V. Denimos el grado del
vértice u, y lo denotamos por gr(u), como el número de aristas incidentes con u. Si gr(u) = 0
diremos que u es un vértice aislado.

Observación 4.1.16. Si en u tenemos un lazo, entonces este lazo contribuye dos veces al grado del
vértice u.

Ejemplo 4.1.17. Consideremos los grafos G y H de la siguiente gura:

En el grafo G se verica que gr(a) = 3 = gr(c), gr(b) = 2 = gr(e) y gr(d) = 4.

En el grafo H, tenemos que gr(f ) = 3, gr(g) =2 y gr(h) = 5.

Teorema 4.1.18. Sea G = (V, E) un grafo no dirigido. Entonces

X
gr(v) = 2 |E| .
v∈V

Demostración. Consideremos, para cada v ∈ V, el conjunto Ev = {{v, u} ∈ E : u ∈ V }. Así,

tenemos que |Ev | = gr(v) para todo v ∈V.

Además, si
P{v1 , v2 } ∈ E , entonces {v1 , v2 } ∈ Ev1 ∩ Ev2 , con lo que la arista {v1 , v2 } se cuenta
dos veces en gr(v), una vez en gr(v1 ) y otra en gr(v2 ).
v∈V

Como esto ocurre para cada arista de E, entonces tenemos que

X
gr(v) = 2 |E| .
v∈V
CAPÍTULO 4. TEORÍA DE GRAFOS 67

Ejemplo 4.1.19. El número de apretones de manos que se dan en una esta es par.

En efecto, si tratamos a los invitados de una esta como los vértices de un grafo simple y cada
P
arista representa dos personas que se dan un apretón de manos, entonces gr(v) representa todos
v∈V
los apretones de manos que se han dado en la esta.

Por el teorema anterior, tenemos que el número de apretones de manos que se dan en una esta
es par.

Corolario 4.1.20. Cualquier grafo no dirigido tiene un número par de vértices de grado impar.

Demostración. Por reducción al absurdo. Supongamos que G = (V, E) es un grafo no dirigido con
un número impar de vértices de grado impar, es decir, existen v1 , v2 , ..., v2k−1 ∈ V , con k ∈ N, tales
que gr(vi ) = 2ki − 1, con ki ∈ N, para todo i = 1, 2, ..., 2k − 1.

2k−1
P
Por una parte, como el grado de cada vi es un número impar, entonces gr(vi ) es un número
i=1
impar.

Por otra parte, tenemos que el grado de cualquier vértice de

P V \ {v1 , v2 , ..., v2k−1 } es par, con
lo que gr(v) es un número par.
v∈V \{v1 ,v2 ,...,v2k−1 }

Luego
X 2k−1
X X
gr(v) = gr(vi ) + gr(v)
v∈V i=1 v∈V \{v1 ,v2 ,...,v2k−1 }

es un número impar.

P
Pero esto es una contradicción, ya que gr(v) es par, por ser
v∈V
X
gr(v) = 2 |E| ,
v∈V

con |E| ∈ N.

Luego G tiene un número par de vértices de grado impar.

Ejemplo 4.1.21. Nueve amigas acordaron enviar cada una postales navideñas a 3 de ellas. ¾Es
posible que cada amiga reciba una postal precisamente de las amigas a quienes envió postal?

Supongamos que es posible y representemos con un vértice a cada una de las 9 amigas. Así,
conectaremos a dos de ellas con una aristas si entre ellas se enviaron postales. De esta forma,
tenemos un grafo simple G con 9 vértices, donde cada uno de ellos tiene grado 3.

Sin embargo, por el corolario anterior, esto no es posible, ya que tenemos un número impar de
vértices de grado impar.

Luego no es posible que cada amiga reciba una postal precisamente de las amigas a quienes
envió postal.
CAPÍTULO 4. TEORÍA DE GRAFOS 68

Denición 4.1.22. Sea G = (V, E) es un grafo dirigido y sea (u, v) ∈ E . Se dice que u es el vértice
inicial de la arista (u, v) es el vértice nal de dicha arista. Del mismo modo, dado u ∈ V ,
y que v
+
se denomina grado de entrada de u, y lo denotaremos por gr (u), al número de aristas que tienen
−
a u como vértice nal y, se denominará grado de salida de u, denotado por gr (u), al número de
aristas que tienen a u como vértice inicial.

Observación 4.1.23. Un lazo en un vértie u suma uno al grado de entrada y uno al grado de salida.

Ejemplo 4.1.24. Consideremos los grafos G y H de la siguiente gura:

En el grafo G, se verica que

+ −
gr (a) =3 y gr (a) = 0,
+ −
gr (b) =1 y gr (b) = 1,
+ −
gr (c) =1 y gr (c) = 2,
+ −
gr (d) =2 y gr (d) = 2,
+ −
gr (e) =0 y gr (e) = 2.
Por otra parte, en el grafo H tenemos

+ −
gr (f ) =2 y gr (f ) = 1,
+ −
gr (g) =0 y gr (g) = 2,
+ −
gr (h) =3 y gr (h) = 2.

Teorema 4.1.25. Sea G = (V, E) un grafo dirigido. Entonces

X X
+ −
|E| = gr (v) = gr (v).
v∈V v∈V
CAPÍTULO 4. TEORÍA DE GRAFOS 69

Demostración. Consideremos Ev− = {(v, u) ∈ E : u ∈ V } para todo v ∈ V. Así, para todo v ∈ V,

− −
se tiene que gr (v) = |Ev |.

Además, tenemos que E = ∪ Ev− , con Eu− ∩ Ev− = ∅ si u, v ∈ V con u ̸= v . Por lo tanto,
v∈V

X X
|E| = ∪ Ev− = Ev− = −
gr (v)
v∈V
v∈V v∈V

aplicando el Principio de adición generalizado.

Análogamente, si tomamos Ev+ = {(u, v) ∈ E : u ∈ V } para todo v ∈ V , entonces gr+ (v) = |Ev+ |
para todo v ∈V.

Como E = ∪ Ev+ , +
con Eu ∩ Ev+ = ∅ para todo u, v ∈ V tales que u ̸= v entonces, por el
v∈V
Principio de adición generalizado,

X X
|E| = ∪ Ev+ = Ev+ = +
gr (v).
v∈V
v∈V v∈V

Luego
X X
+ −
|E| = gr (v) = gr (v).
v∈V v∈V

4.1.2. Algunos grafos relevantes

Presentaremos ahora algunos grafos con nombre propio a los que haremos referencia con cierta
frecuencia.

Denición 4.1.26. Sea n ∈ N, con n ≥ 2, denimos el grafo completo de n vértices, y lo denotamos

por Kn , como el grafo simple Kn = (V, E), donde V = {1, 2, ..., n} y E = {{i, j} ∀ i, j ∈ V : i ̸= j}.

Ejemplo 4.1.27. Algunos ejemplos de grafos completos son los siguientes:

1. El grafo completo de 2 vértices, K2 :

CAPÍTULO 4. TEORÍA DE GRAFOS 70

2. El grafo completo de 3 vértices, K3 :

3. El grafo completo de 4 vértices, K4 :

4. El grafo completo de 5 vértices, K5 :

Denición 4.1.28. Sea n ∈ N, con n ≥ 3. Llamaremos ciclo de longitud n, y lo denotamos por

Cn , al grafo simple Cn = (V, E) cuyo conjunto de vértices es V = {1, 2, ..., n} y cuyas aristas son
E = {{k, k + 1} ∀ k ∈ {1, 2, ..., n − 1}} ∪ {1, n}}.
Ejemplo 4.1.29. Los siguientes grafos son algunos ejemplos de ciclos:

1. El ciclo de longitud de 3, C3 :
CAPÍTULO 4. TEORÍA DE GRAFOS 71

2. El ciclo de longitud de 4, C4 :

3. El ciclo de longitud de 5, C5 :

Denición 4.1.30. Sea n ∈ N. Llamaremos camino de longitud n, y los denotamos por Pn , al

grafo simplePn = (V, E) tal que su conjunto de vértices es V = {0, 1, 2, ..., n} y sus aristas son
E = {{k − 1, k} ∀ k = 1, 2, ..., n}.

Ejemplo 4.1.31. Algunos ejemplos de caminos son los siguientes:

1. El camino de longitud 1, P1 :

2. El camino de longitud 2, P2 :
CAPÍTULO 4. TEORÍA DE GRAFOS 72

3. El camino de longitud 3, P3 :

4. El camino de longitud 4, P4 :

Denición 4.1.32. Sean n, m ∈ N. denimos el grafo bipartito completo, y lo denotamos por Kn,m ,
como el grafo simple Kn = (V, E) donde V = V1 ∪V2 , con V1 = {u1 , u2 , ..., un } y V2 = {v1 , v2 , ..., vm },
y sus aristas son E = {{ui , vj } : 1 ≤ i ≤ n, 1 ≤ j ≤ m}.

Ejemplo 4.1.33. A continuación encontramos representaciones de los grafos bipartitos completos

K2,3 y K3,3 :

Observación 4.1.34. Existen otros grafos con nombre aunque menos relevantes. Algunos de ellos
son

el grafo nulo, G = (V, E), donde V = E = ∅,

un grafo vacío, G = (V, E) tal que E=∅ o

el grafo trivial, G = (V, E), con |V | = 1 y E = ∅.

CAPÍTULO 4. TEORÍA DE GRAFOS 73

4.1.3. Subgrafos
De forma análoga a otras estructuras como anillos, espacios vectoriales o grupos, en los grafos
también encontramos el concepto de subestructura correspondiente, los subgrafos.

Denición 4.1.35. Sean G = (V, E) y G′ = (V ′ , E ′ ) dos grafos. Diremos que G′ es un subgrafo

de G, y lo denotamos por G′ ≤ G, si V ′ ⊆ V y E ′ ⊆ E ′ .
Ejemplo 4.1.36. Si consideremos el grafo G = (V, E) dado por la siguiente representación:

Algunos subgrafos de G son:

1. G1 = (V1 , E1 ), con V1 = {A, B, E} y E1 = {{A, B}}

2. G2 = (V2 , E2 ), con V2 = V y E2 = {{A, B}, {C, D}, {C, E}, {D, E}, {E, F }, {E, G}, {F, G}}

3. G3 = (V3 , E3 ), con V1 = {C, D, E, G} y E3 = {{C, D}, {C, E}, {E, G}}

CAPÍTULO 4. TEORÍA DE GRAFOS 74

Denición 4.1.37. Sean G = (V, E) y G′ = (V ′ , E ′ ) dos grafos. Diremos que G′ es un subgrafo

′
inducido (por V ) de G si V ′ ⊆ V y E ′ es el conjunto de todas las aristas de G cuyos vértices
pertenecen a V ′.

Ejemplo 4.1.38. Del grafo G del ejemplo anterior,

tenemos que G1 es un grafo inducido de G, las aristas de G1 son todas las aristas de G cuyos
vértices están en V1 .

Sin embargo, el subgrafo G2 no es un subgrafo inducido

ya que {A, B}, {B, C} ∈

/ E2 . Lo mismo ocurre con el subgrafo G3

Para que G3 fuera un grafo inducido, necesitaríamos que la arista {D, E} estuviera en E3 .

Denición 4.1.39. Sean G = (V, E) y G′ = (V ′ , E ′ ) dos grafos. Diremos que G y G′ son iguales
(o idénticos ) si V = V ′ y E = E ′.
CAPÍTULO 4. TEORÍA DE GRAFOS 75

4.1.4. Isomorsmo de grafos

Acabamos de ver que dos grafos son iguales si tienen el mismo conjunto de vértices y aristas.
Sin embargo, hay veces en las que dos grafos solo dieren en los nombres de sus vértices pero siguen
teniendo la misma estructura. Es aquí donde entra el concepto de isomorsmo de grafos.

Denición 4.1.40. Sean G = (V, E) y G′ = (V ′ , E ′ ) dos grafos simples. Se dirá que G y G′ son
grafos isomorfos, y se denota por G ∼ = G′ , si existe una función biyectiva f : V −→ V ′ tal que,
′
para todo u, v ∈ V , se verica que {u, v} ∈ E si, y solo si, {f (u), f (v)} ∈ E . A la función f que
′
satisface esta condición se le denomina isomorsmo de grafos entre los grafos G y G .

Observación 4.1.41. En otras palabras, dos grafos simples son isomorfos si tienen el mismo número
de vértices y existe una función biyectiva entre los dos conjuntos de vértices que preserva las
adyacencias. Esta denición puede extenderse a multigrafos y multidigrafos teniendo en cuenta el
número de aristas entre cada par de vértices y, en su caso, la orientación de las aristas.

Ejemplo 4.1.42.
1. Los dos grafos de la siguiente gura son isomorfos

Para verlo, basta comprobar que la función f : {a, b, c, d} −→ {u, v, w, p}, denida por
f (a) = u, f (b) = v , f (c) = w y f (d) = p, es un isomorsmo entre estos grafos.

En efecto, se tiene que E = {{a, b}, {a, d}, {b, c}, {d, c}} y

f (a) = u, f (b) = v ⇒ {f (a), f (b)} ∈ E ′ ,

f (a) = u, f (d) = p ⇒ {f (a), f (d)} ∈ E ′ ,

f (b) = v, f (c) = w ⇒ {f (b), f (c)} ∈ E ′ ,
f (d) = p, f (c) = w ⇒ {f (d), f (c)} ∈ E ′ ,
y viceversa.

2. La aplicación f : {1, 2, 3, 4, 5, 6} −→ {A, B, C, D, E, F } denida por f (1) = A, f (2) = B ,

f (3) = E , f (4) = D, f (5) = C y f (6) = F es un isomorsmo entre los grafos
CAPÍTULO 4. TEORÍA DE GRAFOS 76

ya que
E = {{1, 2}, {1, 4}, {1, 6}, {2, 3}, {2, 5}, {3, 4}, {3, 6}, {4, 5}, {5, 6}},
y se verica que
f (1) = A, f (2) = B ⇔ {A, B} ∈ E ′ ,
f (1) = A, f (4) = D ⇔ {A, D} ∈ E ′ ,
f (1) = A, f (6) = F ⇔ {A, F } ∈ E ′ ,
f (2) = B, f (3) = E ⇔ {B, E} ∈ E ′ ,
f (2) = B, f (5) = C ⇔ {B, C} ∈ E ′ ,
f (3) = E, f (4) = D ⇔ {E, D} ∈ E ′ ,
f (3) = E, f (6) = F ⇔ {E, F } ∈ E ′ ,
f (4) = D, f (5) = C ⇔ {D, C} ∈ E ′ y

f (5) = C, f (6) = F ⇔ {C, F } ∈ E ′ .

A menudo es difícil determinar si dos grafos simples son isomorfos. Existen varios criterios para
determinar si dos grafos simples son o no isomorfos sin realizar una comprobación exhaustiva.
Estos criterios se apoyan en el hecho de que hay ciertas propiedades invariantes por isomorsmos,
es decir, si un grafo las verica, cualquier otro grafo isomorfo a él las debe vericar también. Por
ejemplo:

1. Dos grafos isomorfos deben tener el mismo número de vértices y de aristas.

2. Sif : V −→ V ′ es un isomorsmo entre dos grafos G y G′ , entonces gr(u) = gr(f (u)) para
todo u ∈ V .

Este tipo de resultados sirve para comprobar con facilidad que algunos grafos no son isomorfos.

Ejemplo 4.1.43. Los siguientes grafos no son isomorfos ya que, aunque ambos tienen el mismo
número de vértices y aristas, en el primero gr(a) = 4, mientras que en el segundo no hay ningún
vértice cuyo grado sea 4.
CAPÍTULO 4. TEORÍA DE GRAFOS 77

Denición 4.1.44. Sea n∈N y sea G un grafo no dirigido. Diremos que un subgrafo G′ de G es
′
un camino de longitud n del grafo G si G es isomorfo a Pn .

Ejemplo 4.1.45. Consideremos el grafo completo de 5 vértices K5 . Vamos a marcar en rojo dos
caminos de distinta longitud dentro de K5 :

Observación 4.1.46. Nótese que un camino nunca pasa más de una vez por un mismo vértice, ya
que el conjunto de aristas de Pn estaba denido como E = {{k − 1, k} ∀ k = 1, 2, ..., n}.

Denición 4.1.47. Sea n ∈ N, con n ≥ 3, y sea G un grafo no dirigido. Un subgrafo G′ de G se

dirá que es un ciclo de longitud n del grafo G si G′ es isomorfo a Cn .

Ejemplo 4.1.48. Vamos a marcar en rojo ahora dos ciclos de distinta longitud dentro de K5 :

4.1.5. Conexión y componentes conexas

Deniremos ahora los conceptos de grafo conexo y componentes conexas de un grafo. Estos
conceptos son fundamentales en la teoría de grafos.
CAPÍTULO 4. TEORÍA DE GRAFOS 78

Denición 4.1.49. Sea G = (V, E) un grafo no dirigido y sean u, v ∈ V . Diremos que u y v

están conectados si existe algún camino de longitud n en G, P = e1 e2 ...en , con ei ∈ E para todo
i = 1, 2, ..., n, tal que u es adyacente a e1 y v es adyacente a en . En este caso, decimos que P es un
camino que conecta a u con v .
Ejemplo 4.1.50. Consideremos el grafo bipartito completo K2,3

En este caso, se tiene que v1 está conectado con v3 , ya que e1 e2 , con e1 = {v1 , u2 } y e2 = {u2 , v3 },
es un camino que conecta a v1 con v3 .
Denición 4.1.51. Diremos que un grafo no dirigido G = (V, E) es conexo si para cualquier par
de vértices u, v ∈ V existe un camino en G que conecta u con v .
Ejemplo 4.1.52.
1. El grafo completo de 5 vértices es conexo

ya que para cada par de vértices de K5 existe un camino que los conecta.

2. El siguiente grafo no es conexo

ya que, por ejemplo, no existe ningún camino que conecte los vértices 2 y 3.
Denición 4.1.53. G = (V, E) un grafo no dirigido y sean v0 , v1 , ..., vk ∈ V , con k ∈ N,
Sea
tales que {vi−1 , vi } ∈ E para todo i = 1, 2, ..., k . Denimos un paseo de longitud k en G como la
secuencia de vértices P = (v0 , v1 , v2 , ..., vk ). En ese caso, diremos que el paseo P conecta a v0 con
vk (o que P es un paseo de v0 a vk ). Si P = (v0 ) diremos que P es un paseo de longitud 0.
CAPÍTULO 4. TEORÍA DE GRAFOS 79

Observación 4.1.54. Dos vértices u y v pueden estar conectados mediante un camino o mediante
un paseo. De hecho, podemos ver un camino en G como un paseo en el que no se repite ningún
vértice.

Ejemplo 4.1.55. En el grafo completo de 5 vértices teníamos el camino de longitud 4

que puede verse como un paseo si lo expresamos como (4, 1, 5, 3, 2).

También podemos conectar 4 con 2 mediante el paseo (4, 1, 5, 3, 1, 3, 2). Este último paseo en
K5 no es un camino en K5 .

Gracias al concepto de paseo vamos a poder denir una relación de equivalencia en el conjunto
de vétrices de un grafo no dirigido.

Proposición 4.1.56. G = (V, E) un grafo

Sea no dirigido y consideremos la relación ∼ en V
dada por u ∼ v , con u, v ∈ V , si y solo si existe un paseo en G que conecta a u con v. Entonces
∼ es una relación de equivalencia en V .

Demostración. Veamos que ∼ es reexiva, transitiva y simétrica.

Ver que ∼ es reexiva es inmediato, ya que para todo u∈V se tiene que (u) es un paseo que
conecta a u con u.

Veamos ahora que ∼ es transitiva. Sean u, v, w ∈ V tales que u∼v y v ∼ w. Tenemos que ver
que u ∼ w.

Por una parte, como u ∼ v, existe entonces un camino P1 = (u, u1 , u2 , ..., uk , v) que conecta a
u con v, donde k ∈ N ∪ {0}.

Por otra parte, como v ∼ w, existe un camino que conecta a v con w, P2 = (v, v1 , v2 , ..., vm , w),
con m ∈ N ∪ {0}.

Por lo tanto, P3 = (u, u1 , u2 , ..., uk , v, v1 , v2 , ..., vm , w) es un camino que conecta a u con w y,

por tanto, u ∼ w, obteniendo así que ∼ es transitiva.

Por último, si dos vértices u, v ∈ V están relacionados, entonces existe un camino P =

(u, u1 , u2 , ..., un , v), con n ∈ N ∪ {0} que conecta a u con v , con lo que P ′ = (v, un , un−1 , ..., u1 , u)
es un camino que conecta a v con u, es decir, v ∼ u, con lo que ∼ es simétrica.

Luego la relación ∼ denida en V es una relación de equivalencia.

CAPÍTULO 4. TEORÍA DE GRAFOS 80

Denición 4.1.57. G = (V, E) un grafo no dirigido y sea ∼ la relación de equivalencia dada

Sea
por la proposición anterior. Seak ∈ N y sean V1 , V2 , ..., Vk las clases de equivalencia de la relación
de equivalencia ∼. A los subgrafos de G inducidos por cada una de estas clases de equivalencia las
llamaremos componentes conexas de G, y las denotaremos por G ei , con i = 1, 2, ..., k .

Observación 4.1.58. Recordemos las clases de equivalencia de una relación de equivalencia es una
partición del conjunto, es decir, son disjuntas dos a dos y la unión de todas las clases de equivalencia
coincide con lo total. En nuestro caso, tendremos que Vi ∩ Vj = ∅, si i, j ∈ {1, 2, ..., k}, con i ̸= j y
k
∪ Vi = V .
i=1

Ejemplo 4.1.59. En el grafo G = (V, E)

tenemos 2 clases de equivalencias en V , V1 = {1, 3, 5} y V2 = {2, 4, 6}.

Por lo tanto, las componentes conexas de G son

Vimos que G era un grafo no conexo. Sin embargo, sus componentes conexas sí son conexas.

Proposición 4.1.60. Sea G = (V, E) Gei = (Vi , Ei ), con i = 1, 2, ..., k ,

un grafo no dirigido y sean
k ∈ N, sus componentes conexas. Entonces G
ei es un subgrafo conexo de G para todo i ∈ {1, 2, ..., k}.

Demostración. Sea γ ∈ {1, 2, ..., k}, tenemos que demostrar que G

eγ es conexo. Para ello, tomemos
u, v ∈ Vγ , con u ̸= v , y veamos que existe un camino que conecta a u con v .

Como u, v ∈ Vγ , entonces u ∼ v , es decir, existe un paseo en G que conecta a u con v,

P = (v0 , v1 , v2 , ..., vk−1 , vk ), con k ∈ N, v0 = u y vk = v .

Por ser P un paseo en G, se tiene que ei = {vi−1 , vi } ∈ E para todo i = 1, 2, ..., k , con lo que
podemos expresar P como

P = e1 e2 ...ek = {v0 , v1 }{v1 , v2 } · · · {vk−2 , vk−1 }{vk−1 , vk }.

CAPÍTULO 4. TEORÍA DE GRAFOS 81

Así, si tenemos que existen i, j ∈ {1, 2, ..., k − 1}, con i ̸= j , tales que vi = vj , entonces en el
paseo P
se pueden suprimir todas las aristas intermedias a las aristas en las que aparecen vi y vj
′
por primera y última vez, formando así un paseo P que conecta a u con v , pero con menos vértices
en su secuencia, es decir, si

P = (v0 , v1 , v2 , ..., vk−1 vk ) = e1 e2 ...ek =

{v0 , v1 }{v1 , v2 } · · · {vi−1 , vi }{vi , vi+1 } · · · {vj−2 , vj−1 }{vj−1 , vj }{vj , vj+1 } · · · {vk−2 , vk−1 }{vk−1 , vk },
entonces
P ′ = {v0 , v1 }{v1 , v2 } · · · {vi−1 , vi }{vj , vj+1 } · · · {vk−2 , vk−1 }{vk−1 , vk } =
(v0 , v1 , v2 , ..., vi−1 , vi , vj+1 , ..., vk−2 , vk−1 , vk )
es un paseo que conecta a u con v, ya que vi = vj .

Como podemos repetir este argumento hasta obtener un paseo

Q = (u0 , u1 , u2 , ..., un−1 , un ),

con ui ̸= uj para todo i, j ∈ {1, 2, ..., n − 1}, con i ̸= j , entonces tenemos que Q
u0 = u, un = v y
es un paseo que conecta a u con v y cuyos vértices son todos distintos, con lo que Q es un camino
que conecta a u con v .

Luego G
eγ es conexo y, por lo tanto, ei es un subgrafo conexo de G para todo i ∈ {1, 2, ..., k}.
G
Observación 4.1.61. De la demostración de la proposición anterior tenemos que, si existe un paseo
en G que conecta dos vértices u, v ∈ V , entonces existe un camino en G que conecta a u con v.
Corolario 4.1.62. Sea G un grafo no dirigido. Entonces G es conexo si y solo si G tiene una
única componente conexa.

Demostración. Supongamos primero que G es conexo. Tenemos que ver que G tiene una única
componente conexa.

ComoG es conexo, entonces para cualquier par de vértices u, v ∈ V existe un camino que
conecta a u con v . Ahora bien, como todo camino es un paseo, entonces existe un paseo que
conecta a u con v para todo u, v ∈ V , es decir, u ∼ v para todo u, v ∈ V , con lo que ∼ tan solo
tiene una clase de equivalencia, V1 = V y, por tanto, el subgrafo de G inducido por V1 = V es G.

Luego G=G
e1 es la única componente conexa de G.

Supongamos ahora que G tiene una única componente conexa, G

e1 .

Como las componentes conexas de G son subgrafos inducidos por las clases de equivalencia de
∼ y G tiene una única componente conexa, entonces ∼ tiene una única clase de equivalencia, V1 .

Al tener ∼ tan solo una clase de equivalencia y V coincide con la unión de todas las clases de
equivalencia de ∼, entonces V = V1 , con lo que G=Ge1 , ya que G
e1 es el subgrafo de G inducido
por V1 = V .

Por último, como G

e1 es conexo por la proposición anterior, entonces G es un grafo conexo.
CAPÍTULO 4. TEORÍA DE GRAFOS 82

4.1.6. Matriz de adyacencia de un grafo simple

Acabaremos esta sección con una de las aplicaciones de grafos que concierne a otro tipo de
representación de grafos distinta al uso de dibujar puntos y líneas, pudiendo representar un grafo
simple mediante una matriz.

Denición 4.1.63. n ∈ N y sea G = (V, E) un grafo simple. Si |V | = n y ordenamos los

Sea
elementos de V como V = {v1 , v2 , ..., vn }, denimos la matriz de adyacencia de G (respecto al
n
orden establecido en V ) como la matriz AG = (aij )i,j=1 ∈ Mn×n (R) , donde

(
1 si {vi , vj } ∈ E
aij = .
0 si {vi , vj } ∈
/E
Observación 4.1.64. La matriz de adyacencia de un grafo simple es una matriz simétrica cuya
diagonal es nula. Además, si AG es la matriz de adyacencia de un grafo simple G, entonces el
k
elemento que ocupa la posición (i, j) en la matriz AG , con k ∈ N, nos indica el número de paseos
de longitud k que existen de vi a vj .

Ejemplo 4.1.65. Consideremos el grafo simple G = (V, E), donde V = {a, b, c, d, e} y E =

{{a, b}, {a, c}, {a, d}, {a, e}, {b, c}, {c, d}, {d, e}}

En este caso, si tomamos V = {a, b, c, d, e}, la matriz de adyacencia de G es

 
0 1 1 1 1
 1 0 1 0 0 
 
AG =   1 1 0 1 0 .

 1 0 1 0 1 
1 0 0 1 0
Como     
0 1 1 1 1 0 1 1 1 1 4 1 2 2 1

 1 0 1 0 0 
 1 0 1 0 0  
  1 2 1 2 1 

A2G =
 1 1 0 1 0 
 1 1 0 1 0 =
  2 1 3 1 2 

 1 0 1 0 1  1 0 1 0 1   2 2 1 3 1 
1 0 0 1 0 1 0 0 1 0 1 1 2 1 2
y el elemento (1, 1) de la matriz A2G es 4, entonces existen 4 paseos de longitud 2 de a a a, que son
(a, b, a), (a, c, a), (a, d, a) y (a, e, a).

Análogamente, como el elemento (4, 3) de la matriz A2G es 1, entonces solo tenemos un paseo
de longitud 2 de d a c, (d, a, c).
CAPÍTULO 4. TEORÍA DE GRAFOS 83

4.2. Circuitos eulerianos

En esta sección vamos a estudiar la generalización del problema de los puentes de Königsberg
a cualquier multigrafo, es decir, dado un grafo no dirigido G = (V, E), veremos cuándo es posible
encontrar un paseo de la forma (v0 , v1 , ..., vn−1 , v0 ) que contenga a todos los vértices (permitiendo
repeticiones de vértices) y a todas las aristas de G una sola vez.

Denición 4.2.1. Sea G = (V, E) un grafo no dirigido y sea P = (v0 , v1 , ..., vk ) un paseo de
longitud k en G, con k ∈ N ∪ {0}. Diremos que P es un paseo cerrado si vk = v0 .

Observación 4.2.2. Recordemos que, si P = (v0 , v1 , ..., vk ) es un paseo de longitud k , con k ≥ 1,

entonces ei = {vi−1 , vi } ∈ E para todo i = 1, 2, ..., k , con lo que P puede expresarse como una
secuencia de vértices, como una secuencia de aristas o como una secuencia de vértices y aristas, es
decir,
P = (v0 , v1 , ..., vk−1 , vk ) = e1 e2 ...ek =
(v0 , e1 , v1 , ..., ek−1 , vk−1 , ek , vk ).
De esta forma, podremos decir que P contiene a los vértices v0 , v1 , ..., vk y también que P contiene
a las aristas e1 , e2 , ..., ek .

Denición 4.2.3. Sea G = (V, E) un grafo no dirigido y sea P un paseo cerrado en G. Diremos que
P es un circuito euleriano si P contiene a todos los vértices de G y a cada arista de G exactamente
una sola vez. Se dirá que G es un grafo euleriano si G posee un circuito euleriano.

Ejemplo 4.2.4. El siguiente grafo G es un grafo euleriano

ya que (1, 2, 3, 4, 2, 6, 4, 5, 6, 1, 3, 5, 1) es un circuito euleriano en G.

Teorema 4.2.5. Sea G = (V, E) un grafo no dirigido. Entonces G es euleriano si y solo si G es

conexo y cada vértice tiene grado par.

Demostración. Supongamos primero que G es euleriano. Veamos entonces que G es conexo y que
todo vértice de G tiene grado par.

Si G es el grafo trivial, entonces es inmediato, ya que |V | = 1 y E = ∅.

Supongamos entonces que |V | > 1 y E ̸= ∅ y sea

P = (v0 , v1 , ..., vk ) = (v0 , e1 , v1 , ..., ek−1 , vk−1 , ek , vk )

CAPÍTULO 4. TEORÍA DE GRAFOS 84

un circuito euleriano de longitud k ≥ 1 en G, es decir, v0 , v1 , ..., vk ∈ V , con v0 = vk , y ei =

{vi−1 , vi } ∈ E para todo i = 1, 2, ..., k .

Claramente tenemos que G es conexo, ya que dos vértices cualesquiera de V van a ser parte
de P y cada tramo de P es un paseo en G, con lo que para cada par de vértices de G existe un
camino en G que los conecta.

Sea v∈V y veamos que gr(v) es un número par. Para ello, deniremos dos conceptos previos.

Diremos que una arista e∈E es una arista entrante de v en P si existe i ∈ {1, 2, ..., k} tal que
e = ei y v = vi . Análogamente, diremos que una arista e ∈ E es una arista saliente de v en P si
existe i ∈ {1, 2, ..., k} tal que e = ei y v = vi−1 .

Denotemos por AE al conjunto de todas las aristas entrantes de v en P y como AS al conjunto

de todas las aristas salientes de v en P. Vamos a establecer una biyección entre AE y AS .

Sea f : AE −→ AS denida por


ei+1 , si e = ei , con i<k
f (e) =
e1 , si e = ek

para todo e ∈ AE .

No es difícil ver que f está bien denida ya que, si e ∈ AE , entonces existe i ∈ {1, 2, ..., k} tal
que e = ei y v = vi , con lo que f (e) = ei+1 y v = v(i+1)−1 , si i ̸= k , o f (e) = e1 y v = vk = v0 si
i = k , es decir, f (e) ∈ AS .

Por otra parte, la aplicación g : AS −→ AE dada por


ei−1 , si e = ei , con 1 < i
g(e) =
ek , si e = e1

para todo e ∈ AS es la aplicación inversa de f ya que, si i ̸= k , entonces

(g ◦ f )(ei ) = g(f (ei )) = g(ei+1 ) = ei

y
(g ◦ f )(ek ) = g(f (ek )) = g(e1 ) = ek .
Además, si 1 < i, entonces

(f ◦ g)(ei ) = f (g(ei )) = f (ei−1 ) = ei

y
(f ◦ g)(e1 ) = f (g(e1 )) = f (ek ) = e1 .
Luego f : AE −→ AS es biyectiva y, por tanto, |AE | = |AS |.

Ahora bien, como toda arista de G pertenece al circuito euleriano P, entonces gr(v) = |AE | +
|AS | = 2 |AE |, es decir, gr(v) es un número par.
CAPÍTULO 4. TEORÍA DE GRAFOS 85

Supongamos ahora que G es un grafo no dirigido conexo y tal que el grado de cada uno de sus
vértices es un número par. Tenemos que ver que G es un grafo euleriano.

Como G es conexo, podemos encontrar en G un paseo

P = (v0 , v1 , ..., vk ) = (v0 , e1 , v1 , ..., ek−1 , vk−1 , ek , vk )

tal que ei ̸= ej para todo i, j ∈ {1, 2, ..., k}, con i ̸= j (nótese que un camino es un paseo vericando
tal condición). A este tipo de paseos se les conoce con el nombre de recorrido.

Supongamos además que la longitud del recorrido P en G es máxima, es decir, cualquier otro
recorrido en G tiene longitud menor o igual que k. Veamos entonces que v0 = vk y que P contiene
a todas las aristas de G.

Por reducción al absurdo. Supongamos que v0 ̸= vk .

v0 ̸= vk , entonces v0 es adyacente a
Como
un número impar de aristas de P . Sin embargo, tenemos que gr(v0 ) es par, con lo que existe u ∈ V
tal que la arista e = {u, v0 } no pertenece a P y, por tanto,

P ′ = (u, v0 , v1 , ..., vk ) = (u, e, v0 , e1 , v1 , ..., ek−1 , vk−1 , ek , vk )

es un recorrido en G de longitud k + 1, lo cual es una contraducción, ya que P era un recorrido en
G de longitud máxima k y k < k + 1.

Por lo tanto, v0 = vk , teniendo así que P es un paseo cerrado.

Veamos ahora que P contiene a todas las aristas de G. Argumentaremos de nuevo por reducción
al absurdo.

Supongamos que existen u1 , u2 ∈ V tales que e = {u1 , u2 } es una arista de G que no pertenece
a P.

Si existe i ∈ {1, 2, ..., k} tal que vi = uj , para algún j ∈ {1, 2}, entonces

P ′ = (uj , uj = vi , vi+1 , ..., vk = v0 , v1 , ..., vi ) = (uj , e, uj = vi , ei+1 , vi+1 , ..., ek , vk , e1 , v1 , ..., ei , vi ),

donde j ∈ {1, 2} \ {j}, es un recorrido en G de longitud k + 1, lo que contradice la longitud máxima
del recorrido P , con lo que u1 , u2 no pertenecen a P .

Al ser G conexo, existe un camino en G, T = f1 f2 ...fm , que conecta u2 con v0 y, como u2 no

pertenecen a P, existe j ∈ {1, 2, ..., m} tal que uno de los vértices adyacentes de fj pertenece a P
y otro no, con lo fj no pertece a P.

Razonando como antes, podemos llegar a una contradicción con la longitud máxima del reco-
rrido P, obteniendo así que P contiene a todas las aristas de G.

Por último, como P es un paseo cerrado y contiene a todas las aristas de G, entonces debe
contener a todos los vértices de P, con lo que P es un circuito euleriano en G.

Luego G es un grafo euleriano.

CAPÍTULO 4. TEORÍA DE GRAFOS 86

Ejemplo 4.2.6. El siguiente grafo simple G no es euleriano

ya que hay dos vértices en G con grado impar.

Observación 4.2.7. En el ejemplo anterior, como gr(D) = gr(C) = 3, si añadimos otra arista entre
′
C y D, obtendríamos un multigrafo G euleriano, ya que sería conexo y con todos sus vértices de
′
grado par. Si de un circuito euleriano de G eliminamos la arista que hemos añadido a G para
′
obtener G , obtenemos un paseo en G que conecta a C con D y que contiene a todos los vértices
de G y a todas las aristas de G una sola vez, por ejemplo,

P = (D, C, E, B, D, E, A, B, C).

Es por eso que podemos dibujar el grafo G del ejemplo anterior sin levantar el lápiz del papel
y sin pasar dos veces por la misma arista.

Denición 4.2.8. Sea G un grafo no dirigido. Diremos que G es un grafo semieuleriano si G no

es euleriano y existe un paseo en G que contiene todos los vértices de G y todas las aristas de G
una sola vez cada una de ellas.

Ejemplo 4.2.9. El grafo simple G del ejemplo anterior es un grafo semieuleriano

por ser un grafo no euleriano que posee un paseo que contiene todos los vértices de G y todas
las aristas de G una sola vez cada una de ellas, P = (D, C, E, B, D, E, A, B, C).
Observación 4.2.10. Un paseo en un grafo semieuleriano que contenga a todos los vértices de G
y a todas las aristas de G una sola vez cada una de ellas, debe comenzar en un vértices de grado
impar y acabar en el otro vértice de grado impar.

Proposición 4.2.11. Sea G = (V, E) un grafo no dirigido. Entonces G es semieuleriano si y solo

si G es conexo y tiene exactamente dos vértices de grado impar.

Demostración. Sea G un grafo no dirigido semieuleriano. Veamos que G es conexo y tiene exacta-
mente dos vértices de grado impar.

Como G es semieuleriano, entonces existe un paseo en G,

P = (v0 , v1 , ..., vk ) = (v0 , e1 , v1 , ..., ek , vk ),

CAPÍTULO 4. TEORÍA DE GRAFOS 87

con v0 ̸= vk , que contiene a todos los vértices de G G una sola vez cada una
y todas las aristas de
de ellas, con lo que solo puede haber dos vértices de P cuyos grados sean números impares, v0 y
vk . Además, como P contiene a todos los vértices de G, entonces G tiene una única componente
conexa, con lo que G es un grafo conexo.

Supongamos ahora que G es conexo y tiene exactamente dos vértices de grado impar, u1 y u2 .
Es claro entonce que G no es un grafo euleriano, aplicando la proposición anterior.

Consideremos ahora el grafo G′ = (V, E ∪ {u1 , u2 }). Como G′

es un grafo conexo con todos sus
′
vértices de grado par entonces, por la proposición anterior, tenemos que G es un grafo euleriano
′ ′ ′
y, por tanto, podemos encontrar un circuito euleriano P = (v0 , v1 , ..., vk ) en G , con lo que P
contiene a todos los vértices de G.

Como u1 y u2 pertenecen a P ′ y {u1 , u2 } es una arista de G′ , entonces existe i ∈ {1, 2, ..., k},
tal que vi = ur1 y vi+1 = ur2 , con r1 , r2 ∈ {1, 2} y r1 ̸= r2 .

Así, tenemos que

P ′ = (v0 , v1 , ..., vi−1 , vi = ur1 , ur2 = vi+1 , vi+2 , ..., vk−1 , vk )

y, por tanto,
P = (ur1 = vi , vi−1 , ..., v0 = vk , vk−1 , ..., vi+2 , vi+1 = ur2 )
es un paseo en G que contiene todos los vértices de G y todas las aristas de G una sola vez cada
una de ellas.

Luego G es un grafo semieuleriano.

4.3. Circuitos hamiltonianos

El origen de los circuitos hamiltonianos reside en un juego inventado en 1857 por el matemático
irlandés Sir William Rowan Hamilton. Considerando los vértices de un dodecaedro como ciudades
distintas del mundo, se daba un dodecaedro de madera con un aller saliendo de cada uno de sus
vértices y un trozo de cuerda. El juego consistía en, comenzando por una ciudad, viajar siguiendo
las aristas del dodecaedro visitando cada una de las otras 19 ciudades una sola vez y terminar el
viaje en la ciudad de partida. El circuito seguido se marcaba utilizando la cuerda y los alleres.

La solución del juego es equivalente a la respuesta de la pregunta ¾hay algún ciclo en el siguiente
grafo que pase por cada vértice exactamente una vez?
CAPÍTULO 4. TEORÍA DE GRAFOS 88

Así nace el concepto de ciclo hamiltoniano en un grafo no dirigido.

Denición 4.3.1. Sea G = (V, E) un grafo no dirigido y sea C un ciclo en G. Diremos que C es un
ciclo hamiltoniano si C contiene a todos los vértices de G. Se dirá que G es un grafo hamiltoniano
si G posee un ciclo hamiltoniano.

Observación 4.3.2. No se debe confundir los conceptos de circuito y ciclo. Un ciclo en un grafo G
′
es un subgrafo G de G isomorfo a Cn , para algún n ≥ 3, con lo que un ciclo no nunca pasa más
de una vez por un mismo vértice. Sin embargo, en un circuito sí se permite pasar más de una vez
por un mismo vértice.

Ejemplo 4.3.3.
1. Los grafos platónicos son hamiltonianos, es decir, los grafos simples que representan a los
sólidos platónicos son hamiltonianos:

2. El siguiente grafo simple (denominado grafo de Petersen) no es hamiltoniano

Observación 4.3.4. Hasta la fecha, no se conoce ninguna caracterización para grafos hamiltonianos.

4.4. Árboles
En esta sección vamos a estudiar un tipo de grafos que aparecen en problemas de distintas
áreas de conocimiento. Los árboles son especialmente útiles en lo que a aplicaciones informáticas
se reere. Estos grafos se emplean, entre otras cosas, para consruir algoritmos ecientes destinados
a localizar items en una lista, para construir redes de ordenadores con coste mínimo, para cons-
truir códigos ecientes destinados a almacenar y transmitir datos o para analizar algoritmos de
ordenación.
CAPÍTULO 4. TEORÍA DE GRAFOS 89

Denición 4.4.1. Sea G = (V, E) un grafo no dirigido. Diremos que G es un árbol si G es conexo
y no tiene ciclos.

Observación 4.4.2. Como un árbol no tiene ciclos, entonces no puede tener lazos o aristas múltiples,
por lo tanto cualquier árbol es un grafo simple.

Ejemplo 4.4.3. Los siguientes grafos son ejemplos de árboles

Lema 4.4.4. Sea G = (V, E) un grafo no dirigido. Si G es conexo, entonces |V | ≤ |E| + 1.

Demostración. Supongamos que G es conexo y jemos u∈V.

Como G es conexo entonces, para cada vértice v ∈ V \ {u}, existe un camino e1 e2 ...en , con
ei ∈ E para todoi = 1, 2, ..., n, que conecta a v con u. Por lo tanto, para cada v ∈ V \ {u},
podemos considerar el conjunto Ev formado por todas las aristas que forman parte de un camino
de longitud mínima que conecta a v con u y tales que v es adyacente a estas aristas, es decir,

Ev = {e ∈ E : e es la primera arista de un camino de longitud mínima que conecta a v con u}.

Claramente, se tiene que ∪ Ev ⊆ E . Veamos que si v1 , v2 ∈ V \ {u}, con v1 ̸= v2 , entonces

v∈V \{u}
Ev1 ∩ Ev2 = ∅.

Por reducción al absurdo. Supongamos que existe e ∈ Ev1 ∩ Ev2 .

Como e ∈ Ev1 , existe entonces v′ ∈ V tal quee = {v1 , v ′ } ∈ E es la primera arista de un

camino de longitud mínima P1 que conecta a v1 con u.

Análogamente, al ser e ∈ Ev2 , existe v ′′ ∈ V tal quee = {v2 , v ′′ } ∈ E es la primera arista de

un camino P2 , de longitud mínima, que conecta a v2 con u.

En este caso, la única opción posible es que v ′ = v2

v ′′ = v1 , con lo que e = {v1 , v2 }. Sean
y
k1 , k2 ∈ N tales que la longitud de P1 es k1 y la longitud de P2 es k2 . Como v1 ̸= v2 y e = {v1 , v2 }
es la arista inicial tanto de P1 como de P2 , entonces o bien k1 ≥ k2 + 1, o bien k2 ≥ k1 + 1, ya que
P1 y P2 son caminos de longitud mínima que conectan a v1 con u y a v2 con u, respectivamente.
Supongamos sin pérdida de generalidad que k1 ≥ k2 + 1.
CAPÍTULO 4. TEORÍA DE GRAFOS 90

Ahora bien, si eliminamos el vértice v2 y la arista e del camino P2 , obtenemos un camino P1′
′
que conecta a v1 con u y cuya longitud, k1 ∈ N, es menor que k2 , pero mayor o igual que k1 , ya
′ ′
que P1 es un camino que conecta a v1 con u de longitud minimal, es decir, k1 < k2 y k1 ≥ k1 , con
′
lo que k1 ≤ k1 < k2 y, por tanto, k1 < k2 , lo cual es una contradicción, ya que k2 + 1 ≤ k1 y estas
dos desigualdades juntas implican que k2 + 1 < k2 , que es imposible

Luego Ev1 ∩ Ev2 = ∅ para todo v1 , v2 ∈ V \ {u}, con v1 ̸= v2 y, por tanto, tenemos que

X
∪ Ev = |Ev | ,
v∈V \{u}
v∈V \{u}

aplicando el Principio de adición generalizado.

Además, como |Ev | ≥ |{v}| = 1 para todo v ∈ V \ {u}, entonces

X X
|Ev | ≥ |{v}| = |V \ {u}| = |V | − 1.
v∈V \{u} v∈V \{u}

Por último, como teníamos que ∪ Ev ⊆ E , entonces

v∈V \{u}

|E| ≥ ∪ Ev ≥ |V | − 1,
v∈V \{u}

por lo que |V | ≤ |E| + 1.

Corolario 4.4.5. Sea G = (V, E) un grafo no dirigido. Si |V | > |E| + 1, entonces G posee al
menos dos componentes conexas.

Demostración. Como |V | > |E| + 1 entonces, aplicando el lema anterior, tenemos que G no es
conexo y, por tanto, G no puede tener una única componente conexa.

Luego G posee al menos dos componentes conexas.

Teorema 4.4.6. (Caracterización de un árbol). Sea G = (V, E) un grafo no dirigido. Los

siguientes enunciados son equivalentes:

1. G es un árbol.

2. G verica la propiedad de unicidad de caminos, es decir, para cualquier par de vértices

u, v ∈ V , existe un único camino en G que conecta a u con v .

3. G es conexo minimal, esto es, el grafo G es conexo y, al suprimir cualquiera de sus aristas,
obtenemos un grafo no conexto.

4. G es un grafo sin ciclos maximal, es decir, G no tiene ciclos y, si construimos un nuevo

′ ′
grafo G añadiendo una arista nueva a G, entonces G contiene ciclos.

5. G es conexo y satisface la denominada fórmula de Euler, |V | = |E| + 1.

CAPÍTULO 4. TEORÍA DE GRAFOS 91

Demostración. Para realizar esta demostración primero demostraremos la equivalencia de las cua-
tro primeras condiciones del teorema probando las implicaciones 1 ⇒ 2, 2 ⇒ 3, 3 ⇒ 4 y 4 ⇒ 1.

Posteriormente, realizaremos la prueba de las implicaciones 2 ⇒ 5 y 5 ⇒ 3, quedando así

demostrada la equivalencia de la quinta condición con las cuatro anteriores.

1 ⇒ 2| Supongamos que G es un árbol y sean u, v ∈ V . Tenemos que ver que existe un único
camino que conecta a u con v .

Como G es conexo, es claro que existe al menos un camino que conecta a u con v . Supongamos
entonces que existen dos caminos distintos,

P1 = (u = u0 , e1 , u1 , ..., ek , uk = v)

y
P2 = (u = v0 , f1 , v1 , ..., fm , vm = v)
que conectan a u con v.

Como P1 y P2 son dos caminos distintos en G que unen a u con v , existe entonces r ∈ {1, 2, ..., k}
tal que ui = vi para todo i = 1, 2, ..., r − 1 y ur ̸= vr , ya que ambos caminos comienzan en u.
Análogamente, existen s ∈ {r + 1, r + 2, ..., k} y t ∈ {r + 1, r + 2, ..., m} tales que us = vt , pero
ui ̸= vj para todo i = r, r + 1, ..., s − 1 y para todo j = r, r + 1, ..., t − 1, ya que los dos caminos
acaban en v .

De esta forma, tenemos que

C = (ur−1 , er , ur , ..., us = vt , et−1 , vt−1 , ..., vr−1 )

es un ciclo en G, lo cual es una contradicción, ya que G no posee ciclos por ser un árbol.

Por lo tanto, existe un único camino que conecta a u con v.

2 ⇒ 3| Supongamos ahora que, para cualquier par de vértices u, v ∈ V , existe un único camino
en G que conecta a u con v . Tenemos que demostrar que G es conexo minimal.

Que G es un grafo conexo es inmediato, ya que para cualquier par de vértices existe un camino
en G que los conecta. Veamos entonces que si eliminamos una arista cualquiera de G, entonces el
grafo obtenido ya no es conexo.

Sean u, v ∈ V tales que e = {u, v} ∈ E . En ese caso, el único camino que conecta a u con v es
(u, e, v).

Por lo tanto, si suprimimos la arista e en G, en el grafo resultante nos será imposible encontrar
un camino que conecte a u con v, con lo que G es un grafo conexo minimal.

3 ⇒ 4| Si ahora partimos de que nuestro grafo G es conexo minimal, tenemos que probar en
este caso que G es un grafo sin ciclos maximal, es decir, G no tiene ciclos y, si construimos un
′ ′
grafo G añadiendo una nueva arista a G, entonces G contiene ciclos.
CAPÍTULO 4. TEORÍA DE GRAFOS 92

Veamos primero que G no tiene ciclos. Por reducción al absurdo. Supongamos que

C = (v0 , e1 , v1 , ..., ek , vk )

es un ciclo en G.

Sea i ∈ {1, 2, ..., k} y consideramos Gi = (V, E \ {ei }). Como G es conexo minimal, entonces
Gi debe ser un grafo no conexo, con lo que existen u, v ∈ V tales que u y v no están conectados
en Gi .

Ahora bien, como G es conexo, existe un camino

P = (u = u0 , f1 , u2 , ..., fm , um = v)

en G que conecta a u con v . Como este camino P es un camino de G pero no de Gi , esto implica
que ei debe ser una de las aristas de la secuencia de P , es decir, existe j ∈ {1, 2, ..., m} tal que
fj = ei , con lo que

P = (u = u0 , f1 , u1 , ..., uj−1 , fj = ei , uj+1 , ..., fm , um = v)

y, por tanto, tenemos que o bien vj−1 = ui−1 y vj = uj , o bien vj−1 = ui y vj = ui−1 .

Supongamos sin pérdida de generalidad que vj−1 = ui−1 y vj = ui .

Si en la secuencia de P sustituimos el camino (uj−1 , fj , uj ) = (vi−1 , ei , vi ) por el camino

C ′ = (uj−1 = vi−1 , ei−1 , ..., v1 , e1 , v0 = vk , ek , vk−1 , ..., vi+1 , ei+1 , vi = uj ),

entonces
C′
′ z }| {
P = (u = u0 , f1 , u1 , ..., fj−1 , vi−1 , ei−1 , ..., ei+1 , vi , fj+1 , ..., fm , um = v)
obtenemos un paseo en Gi que une a u con v, lo cual es una contradicción.

Por lo tanto, G es un grafo sin ciclos.

Sean u1 , u2 ∈ V tales que e = {u1 , u2 } ∈

/E y consideremos G′ = (V, E ∪ {e}). Veamos entonces
que G posee al menos un ciclo.

Como G es conexo, existe entonces un camino

P = (u1 = v0 , e1 , v2 , ..., ek , vk = u2 )

que conecta a u1 con u2 , con lo que

C = (u1 = v0 , e1 , v2 , ..., ek , vk = u2 , e, u1 )

es un ciclo en G′ .

Por lo tanto, G es un grafo sin ciclos maximal.

CAPÍTULO 4. TEORÍA DE GRAFOS 93

4 ⇒ 1| Tenemos que demostrar que, si G es un grafo sin ciclos maximal, entonces G es un árbol.
Para ello, bastará demostrar que G es conexo.

Sean u1 , u2 ∈ V . Si {u1 , u2 } ∈ E , es claro que u1 y u2 están conectados. Supongamos entonces

que u1 , u2 ∈ V son tales que e = {u1 , u2 } no es una arista de G y consideremos G′ = (V, E ∪ {e}).

Al ser G sin ciclos maximal, entonces G′ posee al menos un ciclo C. Además, tal ciclo en G′
debe contener a la arista e ya que, en caso contrario, C sería un ciclo de G, y esto no es posible.

Por lo tanto, tenemos que

C = (v0 , e1 , v1 , ..., ei , vi = ur1 , ei+1 = e, ur2 = vi+1 , ..., ek , vk ),

donde r1 , r2 ∈ {1, 2}, con r1 ̸= r2 . Reordenando la secuencia de aristas y vértices que aparecen en
el ciclo C , obtenemos que

C ′ = (ur1 = vi , e = ei+1 , vi+1 = ur2 , ..., ek , vk = v0 , e1 , v1 , ..., ei , vi = ur1 )

es un ciclo en G′ .

Al suprimir en C′ el vértice vi y la arista e, obtenemos el camino

P = (ur2 = vi+1 , ei+2 , vi+2 , ..., ek , vk = v0 , e1 , v1 , ..., ei , vi = ur1 ),

que es un camino en G que conecta a u1 con u2 .

Luego G es conexo y, por tanto, G es un árbol.

2 ⇒ 5| Vamos a demostrar ahora que si G es un grafo satisfaciendo la propiedad de unicidad

de caminos, entonces G es conexo y |V | = |E| + 1.

La conexión de G es evidente, ya que para cada par de vértices de G existe un camino que
los conecta. Veamos entonces que |V | = |E| + 1. Para ello, jado u ∈ V, vamos a establecer una
biyección entre V \ {u} y E.

f : V \ {u} −→ E tal
Sea que, para cada v ∈ V \ {u}, f (v) es la primera arista del único
camino que conecta a v con u.

Se tiene que f está bien denida, ya que G verica la propiedad de unicidad de caminos. Veamos
que f es inyectiva. Para ello, dados v1 , v2 ∈ V \ {u} tales que f (v1 ) = f (v2 ), tenemos que ver que
v1 = v2 .

Por reducción al absurdo. Supongamos que v1 ̸= v2 , con f (v1 ) = f (v2 ).

Como f (v1 ) es la primera arista de P1 , el único camino que conecta a v1 con u, existe entonces
v ∈ V tal que f (v1 ) = {v1 , v ′ }. De forma análoga, existe v ′′ ∈ V tal que f (v2 ) = {v2 , v ′′ }, ya que
′

f (v2 ) es la primera arista de P2 , el único camino que conecta a v2 con u.

CAPÍTULO 4. TEORÍA DE GRAFOS 94

Tal y como ocurre en la demostración del lema anterior, la única opción posible es que v ′ = v2
′′
y v = v1 , ya que f (v1 ) = f (v2 ), es decir,

{v1 , v2 } = {v1 , v ′ } = f (v1 ) = f (v2 ) = {v2 , v ′′ } = {v2 , v1 }.

Ahora bien, como v1 ̸= v2 entonces, si eliminamos el vértice v2 y la arista f (v2 ) del camino P2 ,
′
obtenemos un camino P1 que conecta a v1 con u. Claramente este camino es diferente de P1 , ya
′
que f (v2 ) = f (v1 ) es la primera arista de P1 , pero f (v2 ) no es una arista de P1 , lo que contradice
la propiedad de la unicidad de caminos de G.

Luego v1 debe ser igual a v2 y, por tanto, f es inyectiva. Veamos ahora que f es sobreyectiva.

Sea e ∈ E . Si e = {v, u}, para algún v ∈ V \ {u}, entonces (v, e, u) es el único camino que
conecta a v con u, con lo que f (v) = e. Supongamos ahora que e = {v, w}, con v, w ∈ V \ {u}.

Si e es la primera arista del único camino que une a v con u, entonces f (v) = e.

En caso contrario, sea P = (v = v0 , e1 , v1 , ..., ek , vk = u) el único camino que une a v con u. En

este caso, añadiendo el vértice w y la arista e al camino P , tenemos que

P ′ = (w, e, v = v0 , e1 , v1 , ..., ek , vk = u)

debe ser el único camino que conecta a w con u, con lo que f (w) = e, teniendo así que f es
sobreyectiva.

Por lo tanto, f es biyectiva.

Como f : V \ {u} −→ E es una aplicación biyectiva, entonces |V \ {u}| = |E|, es decir,

|V | − 1 = |E| y, por tanto, |V | = |E| + 1, con lo que se verica la fórmula de Euler.

5 ⇒ 3| Por último, supongamos que G es conexo y verica la fórmula de Euler, |V | = |E| + 1.

Vamos a probar que G es conexo minimal.

Sean u, v ∈ V tales que e = {u, v} ∈ E y consideremos G′ = (V ′ , E ′ ), con V ′ = V y E ′ = E\{e}.

Como |E ′ | = |E| − 1 y G verica que |V | = |E| + 1, entonces

|V ′ | = |V | = |E| + 1 = (|E ′ | + 1) + 1 = |E ′ | + 2 > |E ′ | + 1,

es decir, |V ′ | > |E ′ | + 1.

Aplicando el lema corolario, tenemos que G′ no es conexo, ya que posee al menos dos compo-
′ ′
nentes conexas por ser |V | > |E | + 1.

Luego G es un grafo conexo minimal.

CAPÍTULO 4. TEORÍA DE GRAFOS 95

4.5. Grafos planares

Los grafos planares son aquellos grafos que se pueden representar en el plano de tal forma que
sus aristas no se corten entre ellas.

Denición 4.5.1. Sea G = (V, E) un grafo tal que |V | > 0 y |E| ≥ 0. Diremos que G es un
grafo planar si es posible representar G en el plano mediante vértices y aristas de modo que las
aristas de G tan solo se intersequen en los vértices. A una representación de G que verique estas
propiedades se le denomina representación plana del grafo G (o incrustación del grafo G en el
plano).

Ejemplo 4.5.2. El grafo completo de 4 vértices, K4 , es un grafo planar

y una representación plana de K4 sería

Proposición 4.5.3. Sean G = (V, E) y G′ = (V ′ , E ′ ) dos grafos tales que G′ es un subgrafo de G.

Si G es planar, entonces G′ es planar.
Demostración. Como G es un grafo planar, existe entonces una representación plana de G.

Ahora bien, como G′

es un subgrafo de G, entonces la representación plana de G debe contener
′
a una representación plana de G .

Luego G′ es un grafo planar.

Denición 4.5.4. Sea G un grafo planar y consideremos una representación plana de G. A cada
una de las secciones en las que queda dividida el plano se le denomina región (o cara ) de la
representación plana de G.
Teorema. (Fórmula de Euler). Sea G = (V, E) un grafo simple, conexo y planar y sea r el
número de regiones de una representación plana de G. Entonces |V | − |E| + r = 2.

Demostración. Como G = (V, E) es un grafo planar, entonces |V | > 0 y |E| ≥ 0. Vamos a

demostrar que |V | − |E| + r = 2 por inducción sobre el número de aristas de G.

Si |E| = 0, entonces |V | = 1, ya que G es conexo. Además, al ser |E| = 0, se tiene que r = 1.

Luego es claro que
|V | − |E| + r = 1 − 0 + 1 = 2.
CAPÍTULO 4. TEORÍA DE GRAFOS 96

n ≥ 0 y supongamos que |V | − |E| + r = 2 es cierto para todo grafo simple, conexo y

Sea
planar con n aristas. Tenemos que ver que, si G = (V, E) es un grafo simple, conexo y planar con
|E| = n + 1, entonces |V | − |E| + r = 2. Para ello, vamos a distinguir dos casos.
1. Si G no tiene ciclos, entonces G es un árbol y r = 1, con lo que |V | = |E| + 1 y, por tanto,
|V | − |E| + r = 2.
2. Si G posee algún ciclo C, entonces podemos considerar G′ = (V, E \ {e}), donde e∈E es
una arista del ciclo C.
Así, tenemos que G′ es un grafo simple, conexo y planar tal que G′ tiene una representación
plana con r−1 regiones, ya que e es una arista de C.
Por lo tanto, aplicando la hipótesis de inducción al grafo G′ , obtenemos que

|V | − |E \ {e}| + (r − 1) = 2
o, equivalentemente,
|V | − (|E| − 1) + (r − 1) = 2,
con lo que |V | − |E| + r = 2.
Por lo tanto, todo grafo simple, conexo y planar verica que |V | − |E| + r = 2.
Observación 4.5.5. El teorema anterior nos indica que el número de caras no depende de la repre-
sentación plana elegida.

Proposición 4.5.6. Sea G = (V, E) un grafo simple, conexo y planar tal que |V | ≥ 3. Entonces
|E| ≤ 3 |V | − 6.
Demostración. Si G no tiene ciclos, entonces G es un árbol y, por tanto, se tiene que |V | = |E| + 1,
con lo que |E| = |V | − 1.

Ahora bien, como |V | ≥ 3, entonces 2 |V | ≥ 6 > 5, con lo que

3 |V | − 6 = |V | + 2 |V | − 6 > |V | + 5 − 6 = |V | − 1 = |E| ,
es decir,
|E| < 3 |V | − 6.
G posee algún ciclo, entonces cada región denida por una representación plana de G estará
Si
acotada por, al menos, 3 aristas de G.

Supongamos que cada representación plana de G tiene r regiones y, para cada i = 1, 2, ..., r,
sea ki el número de aristas que conforman la frontera de la región i.
r
P
Como ki ≥ 3 para todo i ∈ {1, 2, ..., r}, entonces ki ≥ 3r. Además, como cada arista divide
i=1
r
P
a lo sumo a dos regiones, se tiene que ki ≤ 2 |E|, con lo que 3r ≤ 2 |E|.
i=1

Aplicando la fórmula de Euler, tenemos que r = 2 + |E| − |V | y, por tanto,

2 |E| ≥ 3r = 3(2 + |E| − |V |) = 6 + 3 |E| − 3 |V | ,

de donde obtemos que |E| ≤ 3 |V | − 6.
CAPÍTULO 4. TEORÍA DE GRAFOS 97

Ejemplo 4.5.7.
1. El grafo completo de 5 vértices K5 no es un grafo planar.

Tenemos que K5 es un grafo simple y conexo, con 5 vértices y 10 aristas. Como se tiene que
|E| = 10 > 3 |V | − 6 = 3 · 5 − 6 = 9, entonces K5 no es un grafo planar.
2. El grafo bipartito completo K3,3 no es un grafo planar.

En este caso no podemos proceder como en el ejemplo anterior, ya que el grafo bipartito
completo K3,3 es un grafo conexo con 6 vértices y 9 aristas vericando que 9 < 3 · 6 − 6 = 12.
Procederemos entonces por reducción al absurdo, argumentando como en la demostración de
la proposición anterior.

Supongamos que K3,3 es planar y sea r el número de regiones de cualquier representación

plana de K3,3 .
Como K3,3 es un grafo simple, conexo y planar entonces, aplicando la fórmula de Euler,
tenemos que
r = 2 + |E| − |V | = 2 + 9 − 6 = 5.
Ahora bien, como K3,3 no tiene ciclos de longitud 3, entonces la frontera de cada región
estará acotada por, al menos, 4 aristas de K3,3 .
Sea ki el número de aristas que conforman la frontera de la región i, para i ∈ {1, 2, 3, 4, 5}.
Como cada arista de K3,3 forma parte de la frontera de, como mucho, 2 regiones, entonces
P5
tenemos que ki ≤ 2 |E| = 18.
i=1
5
P
Por otra parte, como ki ≥ 4 para todo i = 1, 2, 3, 4, 5, entonces ki ≥ 4 · 5 = 20.
i=1
5
P
De esta forma, obtenemos que 20 ≤ ki ≤ 2 |E| = 18, lo cual es una contradicción.
i=1
Luego K3,3 no es un grafo planar.
CAPÍTULO 4. TEORÍA DE GRAFOS 98

Lema 4.5.8. Sea G = (V, E) un grafo simple, conexo y planar. Entonces existe v ∈ V tal que
gr(v) ≤ 5.

Demostración. Por reducción al absurdo. Supongamos que gr(v) ≥6 para todo v ∈V.

Como gr(v) ≥6 para todo v ∈V, entonces

X X
2 |E| = gr(v) ≥ 6 = 6 |V | ,
v∈V v∈V

con lo que |E| ≥ 3 |V |.

Por otra parte, aplicando la proposición anterior, tenemos que |E| ≤ 3 |V | − 6 y, por tanto,
|E| + 6 ≤ 3 |V |.

Luego, tenemos que

3 |V | ≤ |E| < |E| + 6 ≤ 3 |V | ,
es decir, 3 |V | < 3 |V |, lo cual es una contradicción.

Por lo tanto, existe v∈V tal que gr(v) ≤ 5.

Denición 4.5.9. Sea G = (V, E) un grafo no dirigido y sean u, v ∈ V tales que e = {u, v} ∈ E .
Dado w∈
/ V, una subdivisión de la arista e es un camino (u, {u, w}, w, {w, v}, v) de longitud 2.

Observación 4.5.10. Al subdividir una arista e = {u, v} de un grafo G = (V, E), obtenemos un
nuevo grafo
G′ = (V ∪ {w}, (E \ {e}) ∪ {{u, w}, {w, v}}).

Denición 4.5.11. Sean G1 = (V1 , E1 ) y G2 = (V2 , E2 ) dos grafos no dirigidos. Diremos que G2
es una subdivisión de G1 si G2 es isomorfo a G1 o un grafo que se obtiene de G1 mediante una
sucesión de subdivisiones de aristas.

Proposición 4.5.12. Sean G1 = (V1 , E1 ) y G2 = (V2 , E2 ) dos grafos no dirigidos tales que G2 es
una subdivisión de G1 . Si G1 es no planar, entonces G2 es no planar.

Demostración. Como G1 es un grafo no planar, entonces ninguna subdivisión de G1 puede ser

planar, ya que una representación de una subdivisión de G1 puede verse como una representa-
ción de G1 al eliminar los vértices añadidos y sustituir sus caminos de longitud 2 por la arista
correspondiente de G1 .
Observación 4.5.13. Usando esta proposición junto con la proposición 4.5.3, tenemos que si un
′
grafo G , que sea subdivisión de K5 o de K3,3 , es subgrafo de un grafo G, entonces G no es planar.
Es decir, si un grafo G es planar, entonces G no puede tener ningún subgrafo que sea subdivisión
de K5 o de K3,3 .

De hecho, esta condición necesaria resulta ser una caracterización de los grafos planares.

Teorema 4.5.14. (de Kuratowski). Sea G = (V, E) un grafo no dirigido. Entonces G es un

grafo planar si y solo si G no contiene a ningún subgrafo que sea subdivisión de K5 o de K3,3 .
CAPÍTULO 4. TEORÍA DE GRAFOS 99

4.6. Coloración de grafos

Uno de los problemas más conocidos de Teoría de Grafos es el problema de coloración de los
vértices de un grafo simple.

El objetivo en estos problemas es asignar colores a los vértices de un grafo simple de tal forma
que vértices adyacentes no compartan el mismo color. Este problema es usualmente conocido como
el problema de los cuatro colores.

El teorema de los cuatro colores arma que basta con cuatro colores para colorear un mapa
geopolítico plano, sin que dos países con frontera común tengan el mismo color.

Como podemos considerar un mapa como un plano dividido en regiones conexas (es decir,
dos puntos de una misma región siempre pueden unirse mediante una curva cuyos puntos están
dentro de esa región), entonces todo mapa puede ser representado por un grafo planar G, donde
los vértices de G representan las distintas regiones del mapa, uniendo dos vértices mediante una
arista si las regiones representadas por tales vértices comparten frontera

De esta forma, el problema de colorear un mapa sin que dos países con frontera común tengan
el mismo color es equivalente al de colorear los vértices de un grafo planar de manera que dos
vértices que forman una arista sean de distinto color.

En esta sección enunciaremos y demostraremos una versión más relajada del teorema de los
cuatro colores, probando que con cinco colores es suciente para para colorear cualquier grafo
planar.

Denición 4.6.1. Sea n ∈ N y sea G = (V, E) un grafo simple tal que |V | ≥ 1. Una coloración
de G con n colores es una aplicación c : V −→ {1, 2, ..., n} tal que, si u, v ∈ V son tales que
{u, v} ∈ E , entonces c(u) ̸= c(v). Llamaremos número cromático de G, y lo denotaremos por
χ(G), al menor número natural n tal que existe una coloración en G con n colores.
CAPÍTULO 4. TEORÍA DE GRAFOS 100

Teorema 4.6.2. (de los cinco colores). Sea G = (V, E) un grafo simple y planar. Entonces
χ(G) ≤ 5.

Demostración. Supongamos que G es conexo ya que, en caso contrario, podemos colorear sus
componentes conexas de forma independiente.

Como G es planar, entonces |V | > 0 y |E| ≥ 0. Vamos a demostrar el resultado por inducción
sobre el número de vértices.

Si |V | = 1 entonces el resultado es evidente. Sea entonces m ∈ N y supongamos que el resultado

es cierto para cualquier grafo simple y planar con m vértices. Veamos que si G = (V, E) es un
grafo simple y planar con m + 1 vértices, entonces χ(G) ≤ 5.

Como G es planar, existe v ∈V ≤ 5. Sea Ev es el conjunto de las aristas que

tal que gr(v)
tienen a v como uno de sus vértices incidentes, es decir, Ev = {{v, u} ∈ E : u ∈ V }, y consideremos
G′ = (V \ {v}, E \ Ev ).

Así, tenemos que G′

es un grafo simple y planar con m vértices luego, aplicando la hipótesis
′
de inducción, se tiene que χ(G ) ≤ 5.

Si todos los vértices que comparten arista con v están coloreados con menos de 5 colores
o gr(v) < 5, entonces podemos utilizar un color distinto para colorear v, obteniendo así una
coloración para G con cinco colores a lo sumo, es decir, χ(G) ≤ 5.

Si tenemos que gr(v) =5

y los vértices que comparten arista con v está coloreados de distintos
′
colores, tenemos que modicar la coloración de G .

Sean v1 , v2 , ..., v5 los cinco vértices adyacentes a v en G. En una representación plana de G, v

y estos cinco vértices estarán conectados de una forma similar a

Consideremos G′13 , el subgrafo de G′ inducido por los vértices coloreados con los mismos colores
′ ′
que v1 y v3 . Nótese que G13 puede tener varias componentes conexas, ya que G = (V \{v}, E \Ev ).
Por ello, consideraremos dos casos.

Si v1 y v3 pertenecen a distintas componentes conexas de G′13 , entonces permutamos los colores

′
de las componente conexa de v3 , obteniendo así una coloración de G con el mismo número de
colores, pero teniendo ahora v1 y v3 el mismo color, con lo que podremos colorear a v del color
CAPÍTULO 4. TEORÍA DE GRAFOS 101

que tenía originalmente v3 y, por tanto, obtenemos en G una coloración que no usa más de cinco
colores.

Si resulta que v1 y v3 pertenecen a la misma componente conexa de G′13 , entonces existirá un

′
camino en G13 ,
P = (v1 = u0 , e1 , ..., ek , uk = v3 ),
que conecta a v1 con v3 y cuyos vértices serán del mismo color que v1 y v3 , ya que G′13 es el subgrafo
′
de G inducido por los vértices coloreados con los mismos colores que v1 y v3 .

Este camino en G′13 formará un ciclo en G si añadimos el vértice v, es decir,

C = (v, {v, v1 }, v1 = u0 , e1 , ..., ek , uk = v3 , {v3 , v}, v),

es un ciclo en G. Este ciclo C acotará en su interior a una región de una represetación plana de G
que contendrá o bien al vértice v2 o bien a los vértices v4 y v5 .

Consideremos ahora G′24 , el subgrafo de G′ inducido por los vértices que tienen los mismo
colores que v2 y v4 .

De nuevo, si v2 y v4 pertenecen a distintas componentes conexas de G′24 , entonces podremos

permutar los colores de los vértices en la componente conexa de v4 para seguir teniendo una
′
coloración de G con el mismo número de colores, pero donde v2 y v4 tienen el mismo color y, por
tanto, coloreamos a v del color que tenía originalmente v4 , obteniendo así una coloración en G que
no usa más de cinco colores.
CAPÍTULO 4. TEORÍA DE GRAFOS 102

Si v2 y v4 pertenecen a la misma componente conexa de G′24 , existirán un camino en G′24 que

conecta a v2 con v4 ,
P ′ = (v2 = u′0 , e′1 , ..., e′k , u′k = v4 ).
En una representación plana de G, este camino P′ deberá intersecarse con el camino P.

Ahora bien, como G es un grafo planar, dada una representación plana de P ′ tan solo G, P y
′
podrán intersecarse en un vértice de G, lo cual no es posible, ya que P es un camino en G13 , cuyos
′ ′
vértices tienen los mismo colores que v1 y v3 , P es un camino en G24 , cuyos vértices tienen los
mismo colores que v2 y v4 y los colores de estos cuatro vértices son distintos entre sí.

Por lo tanto, no puede ocurrir que v1 y v2

estén en la misma componente conexa de G′13 y
′
también que v2 y v4 están en la misma componente conexa de G24 .

Como ambas condiciones no pueden darse simultáneamente, o bien v1 y v3 están en componentes

′ ′
conexas distintas de G13 , o bien v2 y v4 están en componentes conexas distintas de G24 .

Si v1 y v3 están en componentes conexas distintas de G′13 entonces, permutando los colores de

las componente conexa de v3 , obtenemos una coloración de G que no usa más de cinco colores.

De forma análoga, vimos que si v2 y v4 están en componentes conexas distintas de G′24 , también
se obtenía una coloración de G que no usa más de cinco colores.

Luego G puede colorearse con un máximo de cinco colores.

Aplicando el principio de inducción matemática, tenemos que todo grafo simple y planar puede
colorearse con un máximo de cinco colores.
CAPÍTULO 4. TEORÍA DE GRAFOS 103

Ejercicios
1. Dibuja, si existen, grafos simples de cuatro vértices con los siguientes grados:

a ) 2, 2, 2 y 4.

b ) 2, 1, 2 y 1.

c ) 2, 2, 2 y 3.

2. Dibuja, si existen, grafos simples de cinco vértices con los siguientes grados:

a ) 1, 2, 3, 1 y 5.

b ) 0, 1, 2, 3 y 4.

c ) 2, 2, 2, 3 y 3.

3. Un grafo simple tiene 16 aristas y sus vértices tienen grado 3 o 4. ¾Cuántos vértices de grado
3 y cuántos de grado 4 debe tener? Indica todas las soluciones posibles.
4. Dado el grafo G de la siguiente gura, decidir razonadamente si los grafos G′ , G′′ , H y H′
son subgrafos de G, subgrafos inducidos de G o no son subgrafos de G.

5. Sea G = (V, E) un grafo simple con V = {1, 2, 3, 4, 5, 6}.

E = {{1, 2}, {1, 4}, {2, 5}, {3, 6}, {4, 5}},
a ) Si determina el subgrafo de G inducido por el
conjunto de vértices {1, 2, 3, 6}.

b ) Si E = {{1, 2}, {1, 3}, {1, 5}, {3, 4}, {4, 5}, {5, 6}}, halla el subgrafo de G inducido por
los vértices 1, 3, 4 y 5.
6. Demuestra que los siguientes grafos son isomorfos.
CAPÍTULO 4. TEORÍA DE GRAFOS 104

7. Estudia si los siguientes grafos son isomorfos:

8. Comprobar que los siguientes grafos no son isomorfos:

9. Sea G un grafo simple con 6 vértices tales que 4 de ellos tienen grado 1 y el resto de vértices
tienen grado 2. ¾Es G conexo?

10. Dar la matriz de adyacencia del siguiente grafo.

Si i ∈ {1, 2, 3, 4, 5}, ¾qué representa la suma de los elementos de la i-ésima la?

11. La siguiente matriz A representa la matriz de adyacencia de un cierto grafo simple G

 
0 0 1 0 1

 0 0 1 1 0 

A=
 1 1 0 0 1 .

 0 1 0 0 0 
1 0 1 0 0
Dibujar el grafo G correspondiente. Si i ∈ {1, 2, 3, 4, 5}, ¾qué representa la suma de los
elementos de la columna i-ésima?
12. Sea n ∈ N G = (V, E) un grafo simple tal que |V | = n. Sea A = AG = (aij )ni,j=1
y sea
la matriz de adyacencia de G respecto del orden en V = {v1 , v2 , ..., vn } y consideremos la
(k)
k -ésima potencia de A, Ak , para k ∈ N. Demostrar que, si denotamos por aij al elemento
k (k)
que ocupa la posición (i, j) en A , entonces aij es el número de paseos de longitud k que
conectan al vértice vi con el vértice vj , para todo i, j ∈ {1, 2, ..., n}.
CAPÍTULO 4. TEORÍA DE GRAFOS 105

13. Dar dos ejemplos de grafos que sean:

a ) Eulerianos y hamiltonianos.

b ) Eulerianos, pero no hamiltonianos.

c ) Hamiltonianos, pero no eulerianos.

d ) Ni eulerianos ni hamiltonianos.

14. Sea G = (V, E) un grafo simple con la siguiente matriz de adyacencia:

 
0 0 0 1 1 1

 0 0 1 1 1 1 

 0 1 0 1 1 1 
A= .

 1 1 1 0 0 0 

 1 1 1 0 0 1 
1 1 1 0 1 0
Determina las componentes conexas de G. ¾Es G euleriano y/o hamiltoniano?

15. Dibuja, si es posible, el grafo que corresponda a cada una de las propiedades descritas a
continuación. Si no es posible, explique por qué:

a ) Un grafo con n vértices y n + 1 aristas, pero que no sea árbol.

b ) Un árbol con 5 vértices con grados 1, 1, 2, 2 y 4.

16. SeaG = (V, E) un grafo simple y conexo tal que |V | = 2n, con n ∈ N, y sea A una matriz de
adyacencia de G. Determina si G es un árbol, si sabemos que la suma de todas las entradas
de A es 2n − 2.

17. SeaG = (V, E) un grafo simple y conexo tal que |V | = n, con n ∈ N, y sea A una matriz de
adyacencia de G. Determina si G es un árbol, si sabemos que la suma de todas las entradas
de A es 2n − 2.

18. Sean ∈ N, con n ≥ 2, y sea G un árbol con n vértices, todos ellos de grados 1 o 3. Demuestra
n−2
que G tiene exactamente vértices de grado 3.
2

19. Sea n ∈ N, con n ≥ 2, y sea G un árbol con n vértices. Demostrar que G posee al menos dos
vértices de grado 1.

20. Sea G = (V, E) un grafo simple, conexo y planar tal que |V | ≥ 3 y sin ciclos de longitud 3.
Demostrar que |E| ≤ 2 |V | − 4.
21. Calcula el número cromático del grafo de Petersen
CAPÍTULO 4. TEORÍA DE GRAFOS 106

22. Sea n∈N y consideremos Pn , el camino de longitud n. Determina χ(Pn ).

23. Sea n ∈ N, con n ≥ 3, y consideremos Cn , el ciclo de longitud n. Calcula χ(Pn ).

24. Sea n ∈ N, con n ≥ 2, y consideremos Kn , el grafo completo de n vértices. ¾Cuál es el número

cromático de Kn ?

25. Determina de cuántas formas se puede colorear el siguiente grafo G con 3 colores distintos

26. ¾Cuál es el número cromático del siguiente grafo?