Grafos

CAPÍTULO 1
Grafos
E
ste capítulo es una introducción a la teoría de grafos. Los grafos son
estructuras discretas compuestas por puntos (llamados vértices) y
líneas (llamadas aristas) que conectan algunos pares de esos pun-
tos. Son una abstracción útil para modelar diversas situaciones reales como
por ejemplo: redes de computadoras, redes telefónicas o eléctricas, circuitos
eléctricos, sistemas de carreteras, sistemas de transporte y distribución de
mercancías y sistemas organizacionales.
Hay muchos libros dedicados por entero a esta disciplina, que el lector
interesado puede consultar. Entre ellos cabe destacar los clásicos [H2, B2],
y entre los más modernos [B2, D1]. En español es muy recomendable el de
José Rodríguez [R6].
1.1. Deniciones y conceptos básicos

1.1.1. Grafos simples
Denición 1.1.1. Un grafo simple es un par G = (V, E) donde V es un
conjunto nito no vacío de elementos llamados vértices y E es un conjunto
de pares no ordenados de elementos distintos de V llamados aristas. Por
razones técnicas se supondrá que V ∩ E = ∅.
Si e = {u, v} es una arista entonces se dice que los vértices u y v son los
2 Capítulo 1. Grafos
extremos de e. Un vértice y una arista son incidentes si el vértice es uno de

los extremos de la arista. Dos vértices u y v son adyacentes si {u, v} es una
arista. El orden de un grafo G = (V, E) es el número de vértices |V |.
Lamentablemente en teoría de grafos no hay una terminología uniforme y
aceptada por todos. Casi puede decirse que cada autor tiene su propia termi-
nología, y por eso la mayoría de las obras sobre grafos comienzan deniendo
los conceptos que se van a utilizar. En particular, los vértices de un grafo
también son llamados nodos o puntos y las aristas líneas, arcos o ejes.
Un grafo se representa por medio de puntos o pequeños círculos, que
designan vértices, y líneas que los unen, que representan las aristas. Para
simplicar la notación frecuentemente designaremos una arista {u, v} sim-
plemente como uv .
Ejemplo 1.1.2. Sea V = {a, b, c, d, e} y E = {ab, bd, be, de}. Entonces (V, E)
es un grafo con cinco vértices (a, b, c, d y e) y cuatro aristas (ab, bd, be y
de). La gura 1.1 es su representación gráca:
a b
c e
Figura 1.1: Grafo simple.
Denición 1.1.3. El grado de un vértice v de un grafo es el número g(v)

de aristas incidentes con él. Si g(v) = 0 se dice que v es un vértice aislado.
En el grafo del ejemplo anterior se tiene g(a) = 1, g(b) = 3, g(d) = g(e) =
2 y g(c) = 0 (c es un vértice aislado).
La sucesión de grados de un grafo se obtiene ordenando en forma no
decreciente los grados de todos los vértices. En el ejemplo anterior la sucesión
de grados es 0, 1, 2, 2, 3.
Teorema 1.1.4 (Euler). En todo grafo G = (V, E) se cumple
X
g(v) = 2|E|.
v∈V
1.1. Deniciones y conceptos básicos 3
Demostración. Las aristas se pueden contar viendo cuántas son incidentes

con cada vértice y sumando todos los números obtenidos. Pero así cada arista
resulta contada dos veces, una por cada uno de sus extremos.
Corolario 1.1.5. En todo grafo G = (V, E) el número de vértices de grado

impar es par.
Denición 1.1.6. Dos grafos G = (V, E) y G0 = (V 0 , E 0 ) son isomorfos si
existe una biyección f : V → V 0 que preserva la relación de adyacencia, es
decir tal que
{u, v} ∈ E si y sólo si {f (u), f (v)} ∈ E 0 .
Para indicar que G y G0 son isomorfos se escribe G ≈ G0 .
Ejemplo 1.1.7. Los dos grafos representados en la gura 1.2 son isomorfos,
ya que la función f que lleva a en a0 , b en b0 , c en c0 y d en d0 es una biyección
y preserva la adyacencia.
a b b
c d a d
c
Figura 1.2: Grafos isomorfos.
Dos grafos isomorfos deben tener el mismo número de vértices. Más aún
todas las propiedades que se deriven de la relación de adyacencia deben ser
idénticas en ambos, en particular deben tener el mismo número de aristas,
el mismo número de vértices aislados y la misma sucesión de grados. Para
los nes de la teoría de grafos, dos grafos isomorfos se consideran idénticos.
Dos grafos con idénticas sucesiones de grados tienen el mismo número de
vértices y de aristas, pero esto no es suciente para que los grafos sean iso-
morfos, como muestran los dos grafos representados en la gura 1.3. Ambos
tienen sucesión de grados 1, 1, 1, 2, 3, 3, pero no son isomorfos ya que en el
de la izquierda el único vértice de grado 2 es adyacente a un vértice de grado
1 y a otro de grado 3, mientras que en el grafo de la derecha el único vértice
de grado 2 es adyacente a dos vértices de grado 3.
Figura 1.3: Grafos no isomorfos.
1.1.2. Algunos tipos particulares de grafos

Denición 1.1.8. Se llama grafo completo de n vértices a un grafo con n
vértices v1 , v2 ,. . . , vn cuyas aristas son todos los pares {v1 , vj } con 1 ≤ i <
j ≤ n.
Todos los grafos completos de n vértices son isomorfos, y se les denota
como Kn . El número de aristas de Kn es n(n − 1)/2. En la gura 1.4 se
representan los grafos completos de orden 1 a 5.
K 1 K2 K3 K4 K5
Figura 1.4: Grafos completos.
Denición 1.1.9. Un grafo G = (V, E) se dice que es bipartito si el conjunto

de vértices V puede particionarse en dos subconjuntos V1 y V2 tales que todas
las aristas tengan un extremo en V1 y el otro en V2 .
En la gura 1.5 se representa un grafo bipartito con V1 = {s, t, u, v} y
V2 = {x, y, z}. Si |V1 | = m, |V2 1 = n y E = V1 × V2 (es decir, si uv es una
arista para todo par de vértices u ∈ V1 , v ∈ V2 ) entonces se dice que el grafo
es bipartito completo y se denota Km,n . En la gura 1.6 se representa K3,2 .
Denición 1.1.10. Un camino de longitud n es un grafo G = (V, E) con
V = {v0 , v1 , v2 , . . . , vn } y E = {v0 v1 , v1 v2 , . . . , vn−1 vn }. Los vértices v0 y vn
son los extremos del camino. Observe que un grafo con un solo vértice es un
camino de longitud 0.
s x
t
u y
v z
Figura 1.5: Grafo bipartito.
Figura 1.6: Grafo bipartito completo K3,2 .
Los caminos se representan dando la sucesión v0 v1 . . . vn de los vértices

que lo componen, entendiendo que sus aristas son v0 v1 , v1 v2 ,. . . , vn−1 vn .
Todos los caminos de longitud n son isomorfos, y se les denota Pn . El camino
de longitud 0, P0 , consta de un solo vértice y ninguna arista.
Denición 1.1.11. Un ciclo de longitud n es un grafo G = (V, E) de orden
n ≥ 3, con vértices v0 , v1 , . . . , vn−1 y aristas v0 v1 , v1 v2 ,. . . , vn−2 vn−1 y
vn−1 v0 .
Los ciclos se representan dando la sucesión v0 v1 . . . vn−1 de los vértices
que lo componen, entendiendo que sus aristas son v0 v1 , v1 v2 ,. . . , vn−2 vn−1
y vn−1 v0 . Todos los ciclos de longitud n son isomorfos, y se les denota Cn .
En la gura 1.7 se representan P5 y C5 .
Denición 1.1.12. Un grafo G = (V, E) es regular si todos sus vértices
tienen el mismo grado. Si el grado común es k se dice que el grafo es k -
regular. A los grafos 3-regulares se les llama también grafos cúbicos.
La gura 1.8 muestra un grafo cúbico de 8 vértices (precisamente el grafo
formado por los vértices y aristas de un cubo).
v3 u2
v1
v5
u1 u3
C5
v2 v4
v0 P5 u0 u4
Figura 1.7: Camino y ciclo.
Figura 1.8: Grafo cúbico.
1.1.3. Subgrafos
Denición 1.1.13. Si G = (V, E) y H = (W, F ) son grafos tales que W ⊂ V
y F ⊂ E , entonces se dice que H es un subgrafo de G y que G es un supergrafo
de H .
Denición 1.1.14. Si G = (V, E) es un grafo y W ⊂ V , se llama subgrafo
inducido (o generado) por W al grafo G[W ] = (W, F ) con F = (W ×W )∩E .
En palabras, el subgrafo de G inducido por W , denotado G[W ], es el grafo
que tiene a W como conjunto de vértices y como aristas a todas las aristas
de G que tengan ambos extremos en W .
Ejemplo 1.1.15. Sea G = ({a, b, c, d, e}, {ab, ac, bc, ad, de}). Entonces H =
({a, b, c}, {ac, bc}) es un subgrafo de G. El subgrafo de G inducido por
{a, b, c} es ({a, b, c}, {ab, ac, bc}).
Un ciclo en un grafo G es un subgrafo de G que sea él mismo un ciclo.
Proposición 1.1.16. Sea G = (V, E) un grafo y sea δ(G) el mínimo de los
grados de sus vértices. Si δ(G) ≥ 2 entonces G contiene un ciclo de longitud

mayor que δ(G).
Demostración. Sea v0 v1 . . . vk un camino de longitud máxima en G. Como
g(vk ) ≥ 2, vk debe ser adyacente a algún vértice u 6= vk−1 , que debe perte-
necer al camino pues de lo contrario éste se podría extender. Sea vi el vértice
con menor índice que sea adyacente a vk . Entonces vi vi+1 . . . vk es un ciclo
y como todos los vértices adyacentes a vk deben pertenecer a este ciclo se
deduce que su longitud es al menos δ(G) + 1.
Denición 1.1.17. La cintura de un grafo es la longitud del ciclo más corto

que contiene, y su circunferencia es la longitud del ciclo más largo. Si el grafo
es acíclico, es decir si no contiene ningún ciclo, entonces por convención su
cintura es ∞ y su circunferencia es 0.
Ejemplo 1.1.18. El grafo de la gura 1.9 contiene tres ciclos: cdef g , hef y
cdehf g . Por lo tanto su cintura es 3 y su circunferencia es 6.
b d e
h f
c i
a g
Figura 1.9: Cintura y circunferencia.
1.1.4. Operaciones con grafos

Hay varias operaciones conjuntistas que pueden realizarse con grafos. La
siguiente denición reúne las más comunes.
Denición 1.1.19. La unión de dos grafos G = (V, E) y H = (W, F ) es
el grafo G ∪ H = (V ∪ W, E ∪ F ), y su intersección es el grafo G ∩ H =
(V ∩ W, E ∩ F ). El complemento de G = (V, E) es G0 = (V, E 0 ), donde E 0
es el complemento de E en el conjunto V × V . En otras palabras G0 tiene el
mismo conjunto de vértices que G, pero dos vértices son adyacentes en G0 si
y sólo si no lo son en G.
La gura 1.10 muestra un grafo G y su complemento G0 .
b d d
b
c c
a e a G e
G
Figura 1.10: Complemento.
Si G = (V, E) es un grafo y F ⊂ V × V , entonces G + F = (V, E ∪ F ) y

G − F = (V, E \ F ). En particular si e ∈ V × V usaremos la notación G + e
en vez de G + {e} = (V, E ∪ {e}), y G − e en vez de G − {e} = (V, E \ {e}).
Análogamente Si W es un conjunto de vértices entonces G + W = (V ∪
W, E). Algo más complicada es la denición de G − W , pues si se suprime un
vértice hay que suprimir también todas las aristas incidentes con él. Entonces
G − W = (V \ W, E 0 ), donde E 0 es el conjunto de aristas en E que no son
incidentes con ningún vértice en W . Si W = {x} se utilizan las notaciones
abreviadas G + x en vez de G + {x} y G − x en vez de G − {x}.
En la gura 1.11 se representan un grafo G, el resultado de adicionarle
una arista G + xy y el resultado de suprimir un vértice G − w.
x x v x
v v
w y w y y
u u u
G G + xy G-w
Figura 1.11: Operaciones con grafos.
Denición 1.1.20. Si G = (V, E) es un grafo y e = uv ∈ E , se denota G/e

al grafo que resulta de la contracción de e a un punto, es decir que e, u y
v se eliminan y se sustituyen por un nuevo vértice w, adyacente a todos los
vértices que eran adyacentes a u o a v .
La gura 1.11 muestra un grafo G y el resultado de contraer una arista

e a un punto.
u
e
w
G v
G/e
Figura 1.12: Contracción.
Denición 1.1.21. Se llama subdivisión de un grafo G = (V, E) a cualquier

grafo obtenido a partir de G sustituyendo algunas aristas uv por caminos de
u a v (con vértices interiores no pertenecientes a V ).
Intuitivamente, una subdivisión de un grafo se obtiene agregando vértices
en las aristas del grafo original, como se ve en la gura 1.13.
Figura 1.13: Subdivisión.
1.1.5. Grafos conexos

Un camino en un grafo G es simplemente un subgrafo de G que, conside-
rado como grafo, sea un camino. Un camino se representa dando la sucesión
v0 v1 . . . vk de los vértices que lo componen, entendiendo que sus aristas son
v0 v1 , v1 v2 ,. . . , vk−1 vk y sus extremos v0 y vk .
Denición 1.1.22. La distancia d(u, v) entre dos vértices u y v de un grafo
es la longitud del camino más corto de u a v . Si no existe ningún camino de
u a v se pone d(u, v) = ∞. El diámetro de G es la máxima distancia entre

dos vértices de G y se denota diam(G).
Denición 1.1.23. Un grafo G = (V, E) es conexo si para cualquier par de
vértices u, v ∈ V existe un camino en G que los une, es decir un camino con
extremos u y v . Equivalentemente, G es conexo si diam(G) < ∞.
Observe que un grafo de orden 1 es conexo, ya que su único vértice
puede unirse consigo mismo mediante un camino de longitud 0. En cambio
se conviene en que el grafo vacío no es conexo.
Proposición 1.1.24. Sea G = (V, E) un grafo y sea δ(G) el mínimo de los
grados de sus vértices. Entonces diam(G) ≥ δ(G).
Demostración. Sea k = diam(G) y sea v0 v1 . . . vk un camino de longitud k .
Entonces todos los vértices adyacentes a vk deben pertenecer al camino, pues
de lo contrario éste se podría extender y el diámetro de G sería mayor que
k . Por lo tanto δ(G) ≤ g(vk ) ≤ k = diam(G).
Denición 1.1.25. Un vértice de un grafo G = (V, E) es central si la
máxima distancia que lo separa de otro vértice es tan pequeña como sea
posible. A esa distancia se le llama radio de G y se denota r(G). Formalmente,
r(G) = mı́n máx d(x, y).
x∈V y∈V
Es fácil probar que

r(G) ≤ diam(G) ≤ 2r(G).
Proposición 1.1.26. Sea G un grafo conexo y e una arista perteneciente a
un ciclo en G. Entonces G − e es conexo.
Demostración. Sea v0 v1 . . . vk−1 un ciclo y e = v0 v1 . Dados dos vértices u y
w de G hay un camino P que los une. Si P no incluye la arista e, entonces P
los une también en G − e. Si en cambio P incluye la arista e, se la sustituye
por v0 vk−1 vk−2 . . . v2 v1 (o por v1 v2 . . . vk−1 v0 si v1 aparece antes que v0 en
P ) y se tiene un camino en G − e que une u con w.
Ejemplo 1.1.27. El grafo de la gura 1.14 es conexo. Por ejemplo dados
los vértices b y h, un camino que los une es el bcdeh; hay otros (bcgeh,
bcgif eh, bacdeh, bacgeh y bacgif eh), pero el más corto es bcdeh, por lo
tanto d(b, h) = 4. Como no hay vértices a distancia mayor que 4, el diámetro
de este grafo es 4. Hay dos puntos de corte: c y e. La arista hi es el único
puente.
b d e
h f
c i
a g
Figura 1.14: .
1.1.6. Árboles
Denición 1.1.28. Un árbol es un grafo conexo y acíclico.
En la gura 1.15 se representa un árbol con 13 vértices y 12 aristas.
Figura 1.15: Árbol.
Lema 1.1.29. Un árbol con n > 1 vértices tiene al menos dos vértices de
grado 1.
Demostración. Sea P = v0 v1 . . . vk un camino de la mayor longitud posible.

Si g(vk ) > 1 entonces vk sería adyacente a un vértice u 6= vk−1 . Si u = vi
para algún i < k − 1, entonces vi vi+1 . . . vk sería un ciclo. Y si u no pertenece
a P entonces el camino se podría extender. Como en ambos casos se llega a
una contradicción debe ser g(vk ) = 1 y análogamente g(v0 ) = 1.
Teorema 1.1.30. Un árbol con n vértices tiene n − 1 aristas.

Demostración. Por inducción en n. Para n = 1 se cumple pues no hay aristas.
Si n > 1 y el árbol tiene m aristas, sea v un vértice de grado 1. Entonces G−v
tiene n − 1 vértices y m − 1 aristas, y obviamente es acíclico y conexo. Por

la hipótesis inductiva debe ser m − 1 = (n − 1) − 1, de donde m = n − 1.
Teorema 1.1.31. Un grafo conexo con n vértices tiene al menos n − 1

aristas, y tiene exactamente n − 1 aristas si y sólo si es un árbol.
Demostración. Si un grafo conexo G es un árbol, entonces tiene n − 1 aris-

tas. Si no es un árbol y tiene m aristas, entonces debe contener algún ciclo.
Removiendo una arista del ciclo se obtiene un grafo conexo G1 con m − 1
aristas. Si G1 no es un árbol se repite el mismo procedimiento, y así sucesi-
vamente hasta obtener un grafo conexo Gk con m − k aristas y sin ciclos, es
decir un árbol. Entonces m − k = n − 1 y m = n − 1 + k > n − 1.
Teorema 1.1.32. Se G = (V, E) un grafo. Las armaciones siguientes son

equivalentes:
(a) G es un árbol.
(b) Dos vértices cualesquiera de G están unidos por un único camino.
(c) G es conexo pero si se le quita cualquier arista deja de serlo.
(d) G es acíclico pero si se le agrega una arista cualquiera deja de serlo.
Demostración. (a)⇒(b): Si G es un árbol entonces es conexo y dos vértices

cualesquiera u y v están unidos por un camino. Si existiesen caminos dife-
rentes x0 x1 x2 . . . xn y y0 y1 y2 . . . ym , con x0 = y0 = u y xn = ym = v , sea i el
primer índice para el cual xi 6= yi , y sea j > i el primer índice mayor que i
para el cual xj = yk , para algún k . Entonces xi−1 xi . . . xj−1 yk yk−1 . . . yi xi−1
sería un ciclo, lo cual es absurdo.
(b)⇒(c): Si dos vértices cualesquiera de G están unidos por un único camino,
entonces G es conexo. Si uv es una arista de G, en G − uv no hay ningún
camino de u a v (pues si no en G habría al menos dos caminos de u a v ).
(c)⇒(d): Si G contuviese un ciclo, quitando cualquier arista del mismo de-
bería seguir siendo conexo.
(d)⇒(a): Basta ver que G es conexo, es decir que dados dos vértices cuales-
quiera u y v , existe un camino de u a v . Si u y v son adyacentes, ese camino es
simplemente uv . Si no lo son, en G + uv debe haber un ciclo vux1 x2 . . . xn v ,
y entonces ux1 x2 . . . xn v es un camino de u a v en G.
1.1.7. Componentes conexas

Denición 1.1.33. Una componente conexa de un grafo G es un subgrafo
conexo maximal de G, es decir un subgrafo conexo que no está propiamente
contenido en ningún otro subgrafo conexo de G.
El grafo de la gura 1.16 tiene cuatro componentes conexas, una de las
cuales es un solo vértice.
Figura 1.16: Componentes conexas.
Las componentes conexas de un grafo son disjuntas, y el grafo es la unión

de ellas. Si un grafo es acíclico entonces cada una de sus componentes conexas
es un árbol. por ello a los grafos acíclicos se les llama bosques.
Teorema 1.1.34. Si un grafo acíclico G tiene n vértices y k componentes
conexas, entonces tiene n − k aristas.
Demostración. Cada componente conexa de G es un árbol. Por lo tanto si
la i-sima componente tiene ni vértices, debe tener ni − 1 aristas. Entonces
el número de aristas de G es
(n1 − 1) + · · · + (nk − 1) = n − k.
Corolario 1.1.35. Un grafo acíclico con n vértices tiene a lo sumo n − 1

aristas, y tiene n − 1 aristas si y sólo si es un árbol.
Demostración. Si es conexo es un árbol y tiene n − 1 aristas. Si no es conexo
entonces tiene k ≥ 2 componentes conexas y m − k < m − 1 aristas.
Ejemplo 1.1.36. Como aplicación de los resultados anteriores supongamos

que un algoritmo halla el mínimo de n números diferentes a1 , a2 ,. . . ,an efec-
tuando comparaciones del tipo ai < aj . ¾Cuántas comparaciones debe reali-
zar como mínimo?
Solución. Consideremos los números a1 , a2 ,. . . ,an como los vértices de un

grtafo, y ejecutemos el algoritmo. Unamos ai con aj mediante una línea si y
sólo si el algoritmo comparó ai con aj . El grafo resultante debe ser conexo,
ya que de lo contrario no habría manera de saber cuál de dos números per-
tenecientes a componentes conexas diferentes es el más grande. Por lo tanto
debe tener al menos n − 1 aristas, es decir que un algoritmo que determine
el mínimo debe hacer al menos n − 1 comparaciones.
1.1.8. Separación y conectividad

Denición 1.1.37. Sean G = (V, E) un grafo, A y B dos subconjuntos de
V y X ⊂ V ∪ E . Se dice que X separa a A y B si todo camino que tenga
un extremo en A y el otro en B tiene un vértice o una arista en X . Un
vértice que separa a otros dos vértices de su misma componente conexa se
llama vértice de corte.vértice!de corte Una arista que separa a sus extremos
se llama puente
Es fácil ver que una arista es un puente si y sólo si no pertenece a ningún

ciclo.
u v w
Figura 1.17: Puentes y vértices de corte.
En la gura 1.17 hay un solo puente, la arista vw, y tres vértices de corte:
u, v y w.
Denición 1.1.38. Si k ≥ 0 es un entero, un grafo G = (V, E) se dice

que es k -conexo si tiene más de k vértices y G − X es conexo para cualquier
subconjunto de vértices X con |X| < k . Al mayor entero k tal que G = (V, E)
es k -conexo se le llama conectividad de G y se denota κ(G).
En otras palabras: G es k -conexo si se necesita remover al menos k vérti-

ces para desconectarlo. Observe que cualquier grafo (no vacío) es 0-conexo.
Un grafo es 1-conexo si y sólo si tiene al menos dos vértices y es conexo.
Observe que κ(G) = 0 si y sólo si G no es conexo o G = K1 . Para los

grafos completos se tiene κ(Kn ) = n − 1. Los ciclos Cn tienen conectividad
2.
En una red de computadoras, si los equipos (computadoras, enrutadores,
puentes, etc.) se consideran como vértices y los cables como aristas, que el
grafo resultante tenga conectividad k signica que hasta k−1 equipos pueden
dejar de funcionar sin que los demás dejen de estar conectados entre sí.
Hay un concepto de conectividad análogo sustituyendo vértices por aris-
tas.
Denición 1.1.39. Si k ≥ 0 es un entero, Un grafo G = (V, E) es k-conexo

por aristas si tiene más de un vértice y G − F es conexo para cualquier
subconjunto de aristas F con |F | < k . Al mayor entero k tal que G = (V, E)
es k -conexo por aristas se le llama conectividad por aristas de G y se denota
λ(G).
La conectividad por aristas de un grafo no conexo es 0. Es fácil ver que

en general se tiene:
κ(G) ≤ λ(G) ≤ diam(G).
1.1.9. Grafos Eulerianos

Denición 1.1.40. Una caminata en un grafo G = (V, E) es una sucesión
alternada de vértices y aristas v0 e0 v1 e1 . . . vk−1 ek−1 vk , donde ei = {vi , vi+1 }
para i = 0, 1, . . . , k −1. Si v0 = vk la caminata se dice cerrada, de lo contrario
se dice abierta. Una caminata es euleriana si incluye a cada arista del grafo
exactamente una vez. Un grafo es euleriano si admite una caminata euleriana
cerrada.
Teorema 1.1.41. Un grafo es euleriano si y sólo si es conexo y todos sus

vértices tienen grado par.
Demostración. Sea G un grafo euleriano. Es obvio que G es conexo. Ahora

bien, el grado de un vértice vi en una caminata euleriana es igual al doble del
número de veces que vi aparece en el interior de la caminata, más uno por
cada vez que vi aparece como extremo. Si G admite una caminata euleriana
cerrada, entonces es obvio que cada vértice debe tener grado par.
Recíprocamente si G es conexo y todos sus vértices tienen grado par,
sea v0 e0 v1 e1 . . . vk−1 ek−1 vk una caminata sin aristas repetidas y de la mayor
longitud posible. Entonces todas las aristas incidentes con vk pertenecen a
la caminata (pues de lo contrario ésta se podría extender), y como el grado

de vk es par debe ser vk = v0 . Si hubiese una arista e no perteneciente a esta
caminata, y uno de sus vértices fuese un vi , si el otro vértice es u entonces la
caminata uevi ei . . . vk−1 ek−1 v0 e0 . . . ei−1 vi sería más larga que la de mayor
longitud, absurdo. Si ninguno de los vértices u, v de e es un vi entonces,
como G es conexo, hay un camino uu1 . . . uj v0 de u a v0 . Si ui es el primer
vértice de ese camino perteneciente a la caminata, entonces ui−1 ui es una
arista que no pertenece a la caminata pero tiene un vértice en ella, lo cual
es absurdo.
Teorema 1.1.42. Un grafo admite una caminata euleriana abierta si y sólo

si es conexo y tiene exactamente dos vértices de grado impar.
Demostración. Sea G conexo con exactamente dos vértices u y v de grado

impar. Si u y v no son adyacentes sea G0 = G + uv . Entonces por el teorema
1.1.41 G0 admite una caminata euleriana cerrada, y al quitarle la arista uv
queda una caminata euleriana abierta con extremos u y v . Si en cambio u y v
son adyacentes, sea x un nuevo vértice y G0 = G + x + ux + xv . Entonces por
el teorema 1.1.41 G0 admite una caminata euleriana cerrada, y al quitarle
las aristas ux y xv queda una caminata euleriana abierta con extremos u y
v.
A D
Figura 1.18: Los siete puentes de Konigsberg.
Ejemplo 1.1.43. La ciudad de Konigsberg, capital de Prusia oriental en el

siglo XVIII, era atravesada por el río Pregel, sobre el cual había siete puentes.
Los habitantes de la ciudad se preguntaban si era posible salir de su casa,
dar un paseo y regresar al punto de partida, habiendo pasado una y sólo una
vez por cada puente.
Euler resolvió el problema en 1735. Observemos que las regiones en que

estaba dividida Konigsberg y los 7 puentes pueden representarse como se
ve en la gura 1.19. Como hay vértices de grado impar, este grafo no es
C
A D
Figura 1.19: Grafo de Konigsberg.
euleriano. Más aún, como hay más de dos vértices de grado impar ni siquiera
admite una caminata euleriana abierta.
1.1.10. Grafos Hamiltonianos

Denición 1.1.44. Un ciclo hamiltoniano en un grafo es un ciclo que con-
tiene a todos los vértices del grafo. Un grafo es hamiltoniano si contiene un
ciclo hamiltoniano. Un camino hamiltoniano es un camino que contiene a
todos los vértices.
Observe que un ciclo hamiltoniano debe contener todos los vértices, pero
no necesariamente todas las aristas. Los ciclos Cn son ejemplos triviales de
grafos hamiltonianos. Un ejemplo menos trivial es el grafo formado por los
vértices y aristas de un cubo.
Si n ≥ 3 el grafo completo Kn es hamiltoniano. De hecho, cualquier
permutación de los vértices de un grafo completo da lugar a un ciclo hamil-
toniano. El número de ciclos hamiltonianos en Kn es (n − 1)!/2.
El nombre de estos grafos proviene de William Rowan Hamilton (1805
1865), matemático irlandés que propuso como rompecabezas hallar un ciclo
que pase por todos los vértices de un dodecaedro regular. El acertijo se fa-
cilita si se representa el grafo del dodecaedro en el plano, como en la gura
1.20. A diferencia de lo que ocurre con los grafos eulerianos, no se conoce una
condición necesaria y suciente, sencilla y útil, para que un grafo sea hamil-
toniano. Una obvia condición necesaria es δ(G) ≥ 2, pero no es suciente.
Figura 1.20: Grafo del dodecaedro.
Tampoco es suciente una condición del tipo δ(G) ≥ k , con k constante. Sin
embargo se tiene el siguiente resultado.
Teorema 1.1.45 (Ore, 1960). Si un grafo tiene n ≥ 3 vértices y la suma de

los grados de cualquier par de vértices no adyacentes es mayor o igual que
n, entonces el grafo es hamiltoniano.
x+ x
y y+
Figura 1.21: Teorema de Ore.
Demostración. Consideremos el grafo completo K con el mismo conjunto

de vértices que G. De todos los ciclos hamiltonianos en K tomemos uno
C que tenga el mayor número posible de aristas en G. Si x es un vértice
de C , llamemos x+ a su sucesor en el ciclo. Probaremos que C tiene todas
sus aristas en G. Para ello supongamos por absurdo que una arista xx+ no
pertenezca a G. Sea S el conjunto de todos los vértices de G adyacentes a x.
Sea S + = {y + : y ∈ S}. Es claro que |S + | = |S| = g(x). Armamos que x+
es adyacente a algún y + ∈ S + . En efecto, si no fuese así, como x+ 6∈ S + , los
vértices adyacentes a x+ estarían contenidos en V (G) \ (S + ∪ {x+ }) y por lo
1.2. Grafos planares 19
tanto g(x+ ) ≤ n−|S + |−1 = n−g(x)−1, de donde g(x+ )+g(x) ≤ n−1 < n,
contradiciendo la hipótesis.
Por lo tanto existe y + ∈ S + adyacente a x+ . Pero esto nos permite
cambiar las aristas xx+ y yy + de C por las aristas xy y x+ y + (ver gura
1.18) obteniendo un nuevo ciclo hamiltoniano C 0 en K que tiene al menos
una arista más en G que C , lo cual es absurdo.
Corolario 1.1.46 (Dirac, 1952). Si G = (V, E) es un grafo de orden n ≥ 3

y grado mínimo δ(G) ≥ n/2, entonces es hamiltoniano.
Demostración. Si u y v son vértices no adyacentes de G entonces g(u) +

g(v) ≥ δ(G)+δ(G) ≥ n/2+n/2, y por el teorema anterior G es hamiltoniano.
1.2. Grafos planares

Una representación de un grafo G = (V, E) en el plano R2 es una corres-
pondencia que a cada vértice v ∈ V le asocia un punto Pv ∈ R2 y a cada
arista e ∈ E con extremos u y v le hace corresponder una curva continua y
sin autointersecciones en R2 (es decir una función continua e inyectiva de un
intervalo cerrado de R en R2 ) que tenga como extremos a Pu y Pv . A estas
curvas les llamaremos líneas de la representación. Todas las guras de grafos
que se muestran en las páginas precedentes son representaciones planas, en
las cuales generalmente las líneas son segmentos rectilíneos.
A una representación plana tal que si dos líneas se intersectan lo hacen
en un extremo común se le llama grafo plano.
Un grafo es planar si puede ser representado como un grafo plano. Por
ejemplo la gura 1.22 muestra dos representaciones de K4 . En la representa-
ción de la izquierda hay dos líneas que se cruzan, por lo tanto no es un grafo
plano. La representación de la derecha sí es un grafo plano. Por lo tanto K4
es planar.
Las líneas de un grafo plano dividen al plano en regiones abiertas y dis-
juntas que se llaman caras, y son las componentes conexas del complemento
en R2 de la unión de todas las líneas y puntos del grafo. Como los grafos
planos son acotados (porque cada línea lo es), todas sus caras son acotadas
excepto una de ellas. Por ejemplo en la gura 1.23 se muestra un grafo plano
con 5 caras, 4 acotadas y una no acotada.
Figura 1.22: K4 es planar.
Figura 1.23: Grafo plano con 5 caras.
Teorema 1.2.1 (Euler). Si un grafo plano conexo tiene V vértices, A aristas

y C caras, entonces
V − A + C = 2.
Demostración. Para un número de vértices V jo, procedamos por inducción

en el número de aristas. El paso base es A = V − 1, en cuyo caso el grafo
es un árbol (ver teorema 1.1.31) y por lo tanto es acíclico. Al no contener
ciclos no hay ninguna cara acotada y por lo tanto C = 1 (la única cara es la
región no acotada). Entonces V − A + C = 1 + 1 = 2.
Supongamos ahora que G tiene A > V − 1 aristas y que el resultado es
cierto para grafos planos conexos con V vértices y menos de A aristas. Sea
e una arista perteneciente a un ciclo (G contiene algún ciclo por el teorema
1.1.31). Entonces el grafo G0 = G−e tiene V 0 = V vértices, A0 = A−1 aristas
y su número de caras es C 0 = C −1, ya que al quitar e hay dos caras de G que
se conectan y pasan a ser una sola. Por lo tanto V − A + C = V 0 − A0 + C 0 ,
pero por la hipótesis inductiva V 0 − A0 + C 0 = 2.
Por ejemplo en el grafo de la gura 1.23 se tiene V = 11, A = 14, C = 5

y V − A + C = 11 − 14 + 5 = 2.
El teorema precedente puede aplicarse a los poliedros convexos, ya que
el grafo formado por los vértices y aristas de estos objetos siempre es plano.
1.2. Grafos planares 21
En efecto, si nos imaginamos el poliedro transparente y nos acercamos lo

suciente a una de las caras, desde afuera, entonces veremos el borde de esa
cara y todas las aristas restantes del poliedro dentro de ella, formando un
grafo plano (más formalmente, lo que se hace es proyectar el poliedro desde
un punto exterior a una cara y sucientemente cercano a ella, sobre el plano
de la cara). Las guras 1.8 y 1.20 muestran el resultado de este procedimiento
para el cubo y el dodecaedro, respectivamente.
Una triangulación es un grafo plano en el cual todas las caras (incluso
la no acotada) tiene una frontera triangular (es decir, un ciclo de longitud
tres como borde). Es fácil ver que cualquier grafo plano con 3 o más vértices
puede convertirse en una triangulación añadiendo un número conveniente
de aristas. Por ejemplo en la gura 1.24 se muestra un grafo plano con 5
aristas (en trazo continuo) que se convierte en una triangulación al agregarle
6 aristas (en trazo punteado).
Figura 1.24: Triangulación.
Teorema 1.2.2. Una triangulación plana con n vértices tiene 3n−6 aristas.
Un grafo plano con n ≥ 3 vértices tiene a lo sumo 3n − 6 aristas.
Demostración. Como en una triangulación cada cara tiene 3 aristas como
frontera, y cada arista es borde de dos caras, se cumple que 3C = 2A. Pero
por el teorema 1.2.1 se tiene V −A+C = 2, y multiplicando por 3 resulta 3V −
3A + 3C = 6, de donde A = A + (2A − 3C) = 3V − 6. Como cualquier grafo
plano con n ≥ 3 vértices puede convertirse en una triangulación agregando
aristas, la segunda armación del teorema es consecuencia de la primera.
Teorema 1.2.3. K5 y K3,3 no son planares.

Demostración. Por el teorema anterior un grafo planar¡ con

¢ 5 vértices puede
tener como máximo 3 · 5 − 6 = 9 aristas, pero K5 tiene 52 = 10, por lo tanto
no es planar.
El caso de K3,3 es más difícil, ya que tiene 6 vértices y 9 aristas, y
3·6−6 = 12 ≥ 9. Sin embargo K3,3 no contiene ningún triángulo, por lo cual,
si pudiese representarse como un grafo plano, éste tendría cada cara limitada
por un ciclo de longitud al menos 4. Por lo tanto 2A ≥ 4C , y combinando
esto con V − A + C = 2 resulta A ≤ A + (A − 2C) = 2(A − C) = 2(V − 2).
Pero esto es imposible para K3,3 pues 9 > 8.
Obviamente Kn no es planar si n ≥ 5, y Km,n no es planar si m ≥ 3 y

n ≥ 3. En cambio es fácil ver que si m ≤ 2 o n ≤ 2 entonces Km,n es planar.
Los grafos K5 y K3,3 contienen, por así decirlo, la semilla de la no pla-
naridad, como muestra el siguiente resultado.
Teorema 1.2.4 (Kuratowski, 1930). Un grafo es planar si y sólo si no
contiene a una subdivisión de K5 o K3,3 como subgrafo.
1.2.1. Extensiones del concepto de grafo

El concepto de grafo simple admite varias generalizaciones. Una de ellas
consiste en admitir aristas que tienen un solo extremo. Este tipo de aristas
se llaman bucles o lazos, y se pueden visualizar como líneas que parten de
un vértice y vuelven a él.
Otra generalización consiste en admitir más de una arista con los mismos
extremos. Este tipo de grafos se denomina multigrafo .
Figura 1.25: Multigrafo.
Una manera de formalizar estas ideas es denir un multigrafo como una

terna G = (V, E, ψ) donde V es el conjunto de vértices, E es el conjunto de
aristas y ψ : E → P (V ) es una función, siendo P (V ) = {{u, v} : u, v ∈ V }
1.3. Digrafos 23
el conjunto de todos los pares no ordenados de elementos (diferentes o no)

de V . La función ψ se llama función de incidencia. Para cada arista e ∈ E ,
ψ(e) contiene los extremos de e. Si |ψ(e)| = 1 entonces e es un bucle, de lo
contrario |ψ(e)| = 2.
Muchos de los conceptos que hemos visto para grafos se pueden aplicar
a los multigrafos, pero en algunos casos hay que hacer adaptaciones más
o menos obvias. Por ejemplo al denir el grado de un vértice, se considera
que cada bucle aporta dos unidades al grado de su único extremo. De esta
manera el teorema de Euler sobre la suma de los grados (1.1.4) es válido
también para multigrafos.
Las caminatas abiertas y cerradas se denen igual que para los grafos
simples, pero un camino o un ciclo no se pueden especicar dando solamen-
te los vértices. Un camino se dene entonces como una caminata que tiene
todos los vértices diferentes, y un ciclo como una caminata con todos los vér-
tices diferentes excepto el primero y el último. De este modo puede denirse
la noción de multigrafo conexo. La caracterización de los grafos eulerianos
(teoremas 1.1.41 y 1.1.42) sigue siendo válida para multigrafos. Por ejemplo
el problema de los siete puentes de Konigsberg (ver gura 1.18), en vez de
modelarlo con un grafo simple como en la gura 1.19, puede modelarse de
manera más natural con un multigrafo, como en la gura f13-20, donde cada
vértice representa una de las cuatro regiones de la ciudad y cada arista un
puente.
C
A D
Figura 1.26: Multigrafo de los 7 puentes de Konigsberg.
1.3. Digrafos
Otra generalización del concepto de grafo es la siguiente:
Denición 1.3.1. Un grafo dirigido o digrafo es una cuaterna G = (V, E, φ, ψ)

donde V es un conjunto de elementos llamados vértices, E es un conjunto de
elementos llamados arcos, y φ y ψ son dos funciones de E en V . Para cada
e ∈ E , a φ(e) se le llama origen y a ψ(e) se le llama extremo de e.
Obsérvese que un digrafo es como un multigrafo en el cual a cada arista
se le ha asignado un sentido.
Los digrafos se representan dibujando, para cada vértice v , un punto Pv ,
y para cada arco de origen v y extremo w, una echa (segmento dirigido)
desde Pv hasta Pw .
Ejemplo 1.3.2. En la gura 1.27 se representa un digrafo con 5 vértices y 8
arcos, uno de los cuales es un bucle con origen y extremo x. Observe que un
arco va de v a w y otro en el sentido opuesto, de w a v . También hay dos
arcos paralelos de x a y .
v w y
x
u
Figura 1.27: Digrafo.
Todo digrafo tiene un grafo (o multigrafo) subyacente, que se obtiene ol-

vidando el sentido de los arcos y considerándolos como aristas no orientadas.
De esta manera muchos conceptos de la teoría de grafos se pueden aplicar a
los digrafos, como por ejemplo las nociones de grado, camino, grafo conexo,
etc. Otras deniciones se adaptan de manera más o menos obvia, por ejemplo
se pueden denir sub-digrafos, isomorsmo de digrafos, etc.
Denición 1.3.3. El grado saliente g + (v) de v ∈ V es el número de arcos
que tienen a v como origen, y su grado entrante g − (v) es el número de arcos
que lo tienen como extremo.
Obviamente
g(v) = g + (v) + g − (v).
El teorema 1.1.4 sobre la suma de los grados, toma para digrafos la siguiente
forma: X X
g + (v) = g − (v) = |E|.
v∈V v∈V
1.4. Coloración de grafos por vértices 25
Denición 1.3.4. Una caminata dirigida en un digrafo G = (V, E, φ, ψ) es

una sucesión alternada de vértices y arcos v0 e0 v1 e1 . . . vk−1 ek−1 vk , tal que
φ(ei ) = vi y ψ(ei ) = vi+1 para i = 0, 1, . . . , k − 1. Si v0 = vk la caminata
se dice cerrada, de lo contrario se dice que es una caminata abierta de v0
a vk . Un camino dirigido es una caminata dirigida con todos sus vértices
diferentes.
Denición 1.3.5. Un digrafo es fuertemente conexo si para cada par de
vértices u y v existe una caminata dirigida de u a v (y otra de v a u).
Los sub-digrafos fuertemente conexos maximales de un digrafo se llaman
componentes fuertemente conexas.
Ejemplo 1.3.6. El digrafo de la gura no es fuertemente conexo ya que por
ejemplo no hay forma de ir desde y a x. Tiene dos componentes fuertemente
conexas, G[{u, v, w, x}] y G[{y, z}], que se muestran rodeadas por líneas
punteadas.
v w y
x
u z
Figura 1.28: Componentes fuertemente conexas.
1.4. Coloración de grafos por vértices

Denición 1.4.1. Dado un conjunto de colores C , una coloración por vér-
tices de un grafo G = (V, E) es una función f : V → C tal que si uv ∈ E
entonces f (u) 6= f (v).
En otras palabras, una coloración por vértices de un grafo es una asig-
nación de colores a los vértices de manera tal que a vértices adyacentes les
correspondan colores diferentes. En realidad los elementos del conjunto C
pueden ser objetos de cualquier naturaleza, y en última instancia lo único
que interesa es su número, pero se usa la metáfora de los colores porque es
intuitiva y fácil de comprender.
Denición 1.4.2. Un grafo G es k-colorable si admite una coloración con

k colores. Al menor k tal que G es k -colorable se le llama número cromático
de G y se denota χ(G).
Obviamente todo grafo de orden n es n-colorable. Kn no se puede colorear

con menos de n colores, pues como todos sus vértices son adyacentes cada
uno debe pintarse de un color diferente. Por lo tanto χ(Kn ) = n. Si llamamos
ω(G) al orden del mayor subgrafo completo de G, entonces se tiene
ω(G) ≤ χ(G) ≤ n.
Un camino de longitud n > 2 tiene número cromático 2, ya que sus vér-

tices pueden pintarse con dos colores en forma alternada, comenzando por
un extremo. Más en general cualquier árbol de orden n > 2 tiene número
cromático 2. En efecto, si se toma un vértice u como raíz y se pinta del color
1, y los adyacentes a u se pintan de color 2, y los que están a distancia 2 de
u se pintan de color 1, y los que están a distancia 3 de u se pintan de color
2, y así sucesivamente, es claro que se obtiene una 2-coloración.
Figura 1.29: Los árboles son 2-colorables.
Ejemplo 1.4.3. En unas jornadas cientícas se van a dictar cierto número

de conferencias. Si los horarios de dos conferencias se solapan, éstas tienen
que dictarse en salones distintos. Consideremos el grafo G que tiene como
vértices a las conferencias, y en el cual dos conferencias son adyacentes si y
sólo si sus horarios se solapan. Entonces decir que G es k -colorable equivale
a decir que k salones son sucientes para dictar todas las conferencias. El
mínimo número de salones necesario para poder dictar todas las conferencias
es el número cromático χ(G).
1.4.1. Algoritmo avaricioso

Dado un grafo numeremos sus vértices como v1 , v2 ,. . . ,vn y los colores
como 1,2,3,. . . El algoritmo avaricioso (en inglés greedy ) intenta colorear el
grafo por vértices ahorrando todos los colores que pueda.
1. Asigne el color 1 al vértice v1 .
2. Para cada i desde 2 hasta n, asigne a vi el color con el menor número

posible que no haya sido ya usado para colorear un vértice adyacente
al vi .
Lamentablemente los resultados del algoritmo avaricioso no siempre son

los mejores, y dependen de la numeración escogida. Por ejemplo para un
camino v1 v2 v3 v4 , con los vértices numerados en ese orden, el algoritmo ava-
ricioso halla una coloración óptima con dos colores ( v1 y v3 reciben el color
1 mientras que v2 y v4 reciben el color 2). Pero si los vértices se examinan
en el orden v1 , v2 , v4 , v3 entonces el algoritmo halla una coloración que usa
tres colores.
En todo caso el algoritmo avaricioso permite obtener una cota superior
para el número cromático: lo peor que puede pasar cuando se va a colorear
un vértice vi es que todos sus adyacentes ya hayan sido coloreados con los
colores 1, 2,. . . , g(vi ), en cuyo caso tendremos que usar el color g(vi )+1 para
colorear vi . Por lo tanto si ∆(G) es el máximo grado, entonces χ(G) ≤ ∆(G).
Por otra parte si ω(G) es el número de clique de G, es decir el orden del mayor
subgrafo completo de G, entonces debe ser χ(G) ≥ ω(G). Combinando estas
desigualdades resulta
ω(G) ≤ χ(G) ≤ ∆(G) + 1.
Las acotación χ(G) ≤ ∆(G) + 1 en general no puede mejorarse, ya que

para el grafo completo Kn el número cromático es n y el grado máximo
n − 1, y se verica la igualdad. También se da la igualdad para los ciclos de
longitud impar, que tienen número cromático 3 y máximo grado 2. En los
grafos conexos éstos son los únicos casos en que se alcanza la igualdad, y por
lo tanto:
Teorema 1.4.4 (Brooks, 1941). Si G es un grafo conexo que no sea completo

ni un ciclo de longitud impar, entonces
χ(G) ≤ ∆(G).
Cualquier grafo bipartito G = (V, E) que contenga al menos una arista

tiene número cromático 2. En efecto, si V se parte en dos subconjuntos de
vértices independientes V1 y V2 entonces basta colorear a los vértices de V1
con un color y a los de V2 con otro.
En particular cualquier árbol A de orden n ≥ 2 tiene número cromático
2, ya que es bipartito. Otra manera de verlo es que si se toma un vértice u
como raíz y se pinta del color 1, y los adyacentes a u se pintan de color 2,
y los que están a distancia 2 de u se pintan de color 1, y los que están a
distancia 3 de u se pintan de color 2, y así sucesivamente, es claro que se
obtiene una 2-coloración. Como un color no es suciente si n ≥ 2, se tiene
χ(A) = 2.
Para grafos planares se tiene el importante Teorema de los cuatro colores :
Teorema 1.4.5 (Appel & Haken, 1976). Todo grafo planar es 4-colorable.
Además, si el grafo no contiene triángulos (es decir ciclos de longitud 3)
se tiene lo siguiente:
Teorema 1.4.6 (Grötzch, 1959). Todo grafo planar sin triángulos es 3-

colorable.
1.4.2. Coloración de mapas

Los mapas se colorean de modo tal que países con un segmento de frontera
común (un solo punto no cuenta) tengan colores diferentes. Aunque algunos
mapas se pueden colorear con menos de 4 colores, algunos requieren cuatro
colores, como muestra el mapa de un país rodeado por otros tres en la gura
1.30.
En 1850 Francis Guthrie, luego de colorear el mapa de Inglaterra con
cuatro colores, planteó el problema de si cuatro colores eran sucientes para
colorear cualquier mapa. El problema fue propuesto a De Morgan, quien
no pudo resolverlo. Algunos otros matemáticos prestigiosos lo intentaron sin
éxito, hasta que en 1879 Kempe publicó una demostración que le dio mucha
fama. Sin embargo 11 años después, en 1890, Heawood descubrió que la
demostración de Kempe tenía un error. Heawood intentó corregir el error
pero no tuvo éxito, sólo consiguió probar un resultado más débil, a saber,
que cinco colores son sucientes (este resultado es el teorema de los cinco
colores ). Sin embargo, nadie pudo conseguir un mapa que no se pudiese
colorear con cuatro colores.
Figura 1.30: Mapa que requiere 4 colores.
Colorear mapas equivale a colorear las caras de un grafo plano. Este

problema a su vez equivale a uno de coloración por vértices, en un grafo
llamado grafo de caras, el cual tiene un vértice para cada cara del grafo
original y donde dos vértices se unen con una arista si y sólo si las caras
correspondientes tienen un segmento de frontera común (un solo punto no
cuenta). Este nuevo grafo también es planar.
Figura 1.31: Grafo de caras de un grafo plano.
La conjetura de los 4 colores equivale entonces a la armación de que

todo grafo planar es 4-colorable por vértices. Este problema, que permaneció
abierto más de un siglo desde que fuera planteado por Guthrie, fue resuelto
en 1976 por K. Appel y W. Haken con ayuda de un complejo programa y
1200 horas de computador. Su método consistió en reducir el problema a
un número nito (pero muy grande) de casos, los cuales analizaron con el
computador.
Esto provocó muchas objeciones, porque por primera vez los matemáticos
no podían vericar cada uno de los pasos de una demostración y tenían que
conar en la corrección del programa y en el funcionamiento correcto del
computador. Luego de que se realizó la prueba en forma independiente, en
otros computadores, con el mismo resultado, la conanza fue creciendo.
1.4.3. Polinomio cromático

Denición 1.4.7. Dado un grafo G y un número natural x, llamemos PG (x)
al número de coloraciones por vértices de G con colores {1, 2, . . . , x}. A PG (x)
se le llama polinomio cromático de G, ya que como veremos siempre es un
polinomio en x.
Ejemplo 1.4.8. Para un grafo G de n vértices sin aristas se tiene PG (x) = xn .
Para un grafo completo PKn (x) = x(x − 1)(x − 2) · · · (x − n + 1).
Para un árbol G con n vértices se tiene PG (x) = x(x − 1)n−1 , ya que
tomando un vértice como raíz y coloreándolo con cualquiera de los x colores
disponibles, cada vértice restante se puede colorear con cualquiera de los
x − 1 colores diferentes al de su padre.
Para hallar el polinomio cromático del grafo G de la gura comenzamos
por asignar al vértice a uno cualquiera de los x colores disponibles. Ahora
b se puede pintar con cualquiera de los x − 1 colores restantes; c sólo se
puede pintar de x − 2 maneras, ya que no puede tener igual color que a ni
que b; d se puede pintar con cualquier color diferente al de b, es decir x − 1
posibilidades; e se puede pintar con cualquier color diferente al de c, es decir
x − 1 posibilidades.
a
x
b c x-2
x-1
d x-1 e x-1
Por el principio del producto PG (x) = x(x − 1)(x − 2)(x − 1)(x − 1) =
x(x − 1)3 (x − 2).
Si e = uv ∈ E , recordemos que G − e es el grafo que resulta al suprimir
la arista e, y G/e es el grafo que resulta de la contracción de e a un punto.
1.5. Coloración de grafos por aristas 31
Lema 1.4.9. Si e ∈ E entonces PG (x) = PG−e (x) − PG/e (x).

Demostración. Las coloraciones de G−e con x colores son de dos tipos: (1) las
que asignan colores diferentes a u y v , y (2) las que asignan el mismo color a u
y a v . Las del tipo (1) son tantas como las coloraciones de G, es decir PG (x).
Las del tipo (2) son tantas como las coloraciones de G/e, es decir PG/e . Por lo
tanto PG−e (x) = PG (x)+PG/e (x), de donde PG (x) = PG−e (x)−PG/e (x).
Ejemplo 1.4.10. Para hallar el polinomio cromático de G = C4 sea e una de

las aristas. Entonces G − e es un camino, por lo tanto PG−e (x) = x(x − 1)3 .
G/e es un triángulo (K3 ), por lo tanto PG/e (x) = x(x−1)(x−2). Finalmente
PG (x) = x(x − 1)3 − x(x − 1)(x − 2) = x(x − 1)[(x − 1)2 − (x − 2)] =
x(x − 1)(x2 − 2x + 1 − x + 2) = x(x − 1)(x2 − 3x + 3).
G G-e G/e
Figura 1.32: Cálculo de PC4 (x).
Teorema 1.4.11. PG (x) es siempre un polinomio en x.

Demostración. Por inducción en el número m de aristas. Si m = 0 y el
grafo G tiene n vértices entonces PG (x) = xn es un polinomio. Si m > 0 y
suponemos el resultado cierto para grafos con menos de m aristas, entonces
sea e una arista de G. Por el lema anterior PG (x) = PG−e (x) − PG/e (x). Pero
G − e y G/e tienen menos de m aristas, y entonces por la hipótesis inductiva
PG−e (x) y PG/e (x) son polinomios en x, y también lo será su diferencia
PG (x).
1.5. Coloración de grafos por aristas

Denición 1.5.1. Dado un conjunto de colores C , una coloración por aristas
de un grafo G = (V, E) es una función f : E → C tal que si e, f ∈ E son
aristas incidentes (es decir con un extremo común) entonces f (u) 6= f (v).
En otras palabras, una coloración por aristas de un grafo es una asigna-

ción de colores a las aristas de manera tal que a cada par de aristas con un
extremo común les correspondan colores diferentes.
Muchos problemas de elaboración de horarios y planicación de tareas
pueden modelarse como problemas de coloración de grafos por aristas.
1.5.1. Grafo de líneas

Denición 1.5.2. El grafo de líneas de un grafo G = (V, E) es el grafo
L(G) = (E, F ) que tiene como vértices a las aristas de G, y en el cual dos
vértices son adyacentes si y sólo si, considerados como aristas de G, son
incidentes.
La gura 1.33 muestra un grafo G a la izquierda y a la derecha su corres-
pondiente grafo de líneas L(G).
d d
e f e f
a b a b
g
c c g
Figura 1.33: Grafo de líneas.
Denición 1.5.3. Un grafo G es k-colorable por aristas si admite una colo-

ración por aristas con k colores. Al menor k tal que G es k -colorable por
aristas se le llama índice cromático de G y se denota χ0 (G).
Obviamente χ0 (G) ≥ ∆(G).
Observe que a cada coloración por aristas de un grafo G le corresponde
una coloración por vértices de su grafo de líneas L(G), y recíprocamente. esto
signica que el problema de colorear por aristas un grafo G es equivalente
al de colorear por vértices su grafo de líneas L(G). En particular χ0 (G) =
χ(L(G)).
Ejemplo 1.5.4. Consideremos la tabla de horarios de un liceo. Se puede cons-
truir un multigrafo bipartito tomando como conjunto de vértices V1 a los
profesores, y como conjunto de vértices V2 a los grupos. Por cada clase que
un profesor debe dictar a un grupo durante la semana se traza una arista
del profesor al grupo. Supongamos que cada clase dura una hora. Entonces
tomemos como conjunto de colores las horas posibles (por ejemplo lunes de
8 a 9, martes de 11 a 12, etc.) A cada arista se le debe asignar un horario de
modo tal que las que salen de un mismo profesor tengan horarios diferentes,
y las que llegan a un mismo grupo también.
El índice cromático de este multigrafo representa la mínima longitud total
de la tabla de horarios (es decir el menor número total de horas ocupadas
en la semana).
1.5.2. Teoremas sobre el índice cromático

Como los grafos de líneas son un tipo especial de grafos, se sabe mucho
más sobre χ0 (G) que sobre χ(G).
Teorema 1.5.5 (König, 1916). Si G es un grafo bipartito entonces χ0 (G) =

∆(G).
Teorema 1.5.6 (Vizing, 1964). Para todo grafo G se tiene

∆(G) ≤ χ0 (G) ≤ ∆(G) + 1.
Este teorema reduce a sólo dos posibilidades el valor del índice cromático:
∆(G) o ∆(G) + 1.
Bibliografía
[B2] Berge, C., The Theory of Graphs and its applications, Methuen & Co -
John Wiley & Sons, London - New York, 1962.
[B3] Bollobas, B., Modern Graph theory, Springer-Verlag, New York, 1998.
[D1] Diestel, R., Graph Theory, 2nd ed., Springer, New York, 2000.
[H2] Harary, F. Graph theory, Addison-Wesley, Reading, Mass., 1969.
[R6] Rodríguez, J., Teoría de Grafos, Kariña Editores, Mérida, 2003.

Índice alfabético
árbol, 11 Euler, 17
Euler, L., 19
algoritmo extremo, 24
avaricioso, 27
arco, 24 grado, 2
entrante, 24
bosque, 13 saliente, 24
grafo
caminata, 15 acíclico, 7
camino, 4, 9 bipartito, 4
hamiltoniano, 17 cúbico, 5
ciclo, 5 completo, 4
hamiltoniano, 17 conexo, 10
coloración dirigido, 24
por vértices, 25 euleriano, 15
componente hamiltoniano, 17
fuertemente conexa, 25 planar, 19
componente conexa, 13 plano, 19
conectividad, 14 regular, 5
conectividad por aristas, 15 simple, 1
contracción, 8
Hamilton, William R., 17
diámetro, 10 multigrafo, 22
digrafo, 24
fuertemente conexo, 25 número
distancia, 9 de clique, 27
orden, 2
Ore, O., 18
origen, 24
puente, 14
radio, 10
representación, 19
subdivisión, 9
subgrafo, 6
subgrafo inducido, 6
supergrafo, 6
teorema
de los cuatro colores, 28
triangulación, 21
vértice
central, 10
de corte, 14

Grafos

Cargado por

Copyright:

Formatos disponibles

Grafos

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Grafos

Cargado por

Copyright:

Formatos disponibles

CAPÍTULO 1

1.1. Deniciones y conceptos básicos

extremos de e. Un vértice y una arista son incidentes si el vértice es uno de

Figura 1.1: Grafo simple.

Denición 1.1.3. El grado de un vértice v de un grafo es el número g(v)

Demostración. Las aristas se pueden contar viendo cuántas son incidentes

Corolario 1.1.5. En todo grafo G = (V, E) el número de vértices de grado

Figura 1.2: Grafos isomorfos.

Figura 1.3: Grafos no isomorfos.

1.1.2. Algunos tipos particulares de grafos

Figura 1.4: Grafos completos.

Denición 1.1.9. Un grafo G = (V, E) se dice que es bipartito si el conjunto

Figura 1.5: Grafo bipartito.

Figura 1.6: Grafo bipartito completo K3,2 .

Los caminos se representan dando la sucesión v0 v1 . . . vn de los vértices

Figura 1.7: Camino y ciclo.

Figura 1.8: Grafo cúbico.

grados de sus vértices. Si δ(G) ≥ 2 entonces G contiene un ciclo de longitud

Denición 1.1.17. La cintura de un grafo es la longitud del ciclo más corto

Figura 1.9: Cintura y circunferencia.

1.1.4. Operaciones con grafos

La gura 1.10 muestra un grafo G y su complemento G0 .

Figura 1.10: Complemento.

Si G = (V, E) es un grafo y F ⊂ V × V , entonces G + F = (V, E ∪ F ) y

Figura 1.11: Operaciones con grafos.

Denición 1.1.20. Si G = (V, E) es un grafo y e = uv ∈ E , se denota G/e

La gura 1.11 muestra un grafo G y el resultado de contraer una arista

Figura 1.12: Contracción.

Denición 1.1.21. Se llama subdivisión de un grafo G = (V, E) a cualquier

Figura 1.13: Subdivisión.

1.1.5. Grafos conexos

u a v se pone d(u, v) = ∞. El diámetro de G es la máxima distancia entre

Es fácil probar que

Figura 1.15: Árbol.

Demostración. Sea P = v0 v1 . . . vk un camino de la mayor longitud posible.

Teorema 1.1.30. Un árbol con n vértices tiene n − 1 aristas.

tiene n − 1 vértices y m − 1 aristas, y obviamente es acíclico y conexo. Por

Teorema 1.1.31. Un grafo conexo con n vértices tiene al menos n − 1

Demostración. Si un grafo conexo G es un árbol, entonces tiene n − 1 aris-

Teorema 1.1.32. Se G = (V, E) un grafo. Las armaciones siguientes son

(b) Dos vértices cualesquiera de G están unidos por un único camino.

(c) G es conexo pero si se le quita cualquier arista deja de serlo.

(d) G es acíclico pero si se le agrega una arista cualquiera deja de serlo.

Demostración. (a)⇒(b): Si G es un árbol entonces es conexo y dos vértices

1.1.7. Componentes conexas

Figura 1.16: Componentes conexas.

Las componentes conexas de un grafo son disjuntas, y el grafo es la unión

Corolario 1.1.35. Un grafo acíclico con n vértices tiene a lo sumo n − 1

Ejemplo 1.1.36. Como aplicación de los resultados anteriores supongamos

Solución. Consideremos los números a1 , a2 ,. . . ,an como los vértices de un

1.1.8. Separación y conectividad

Es fácil ver que una arista es un puente si y sólo si no pertenece a ningún

Figura 1.17: Puentes y vértices de corte.

Denición 1.1.38. Si k ≥ 0 es un entero, un grafo G = (V, E) se dice

En otras palabras: G es k -conexo si se necesita remover al menos k vérti-

Observe que κ(G) = 0 si y sólo si G no es conexo o G = K1 . Para los

Denición 1.1.39. Si k ≥ 0 es un entero, Un grafo G = (V, E) es k-conexo

La conectividad por aristas de un grafo no conexo es 0. Es fácil ver que

1.1.9. Grafos Eulerianos

1.1. Deniciones y conceptos básicos

Denición 1.1.3. El grado de un vértice v de un grafo es el número g(v)

Denición 1.1.9. Un grafo G = (V, E) se dice que es bipartito si el conjunto

Denición 1.1.17. La cintura de un grafo es la longitud del ciclo más corto

La gura 1.10 muestra un grafo G y su complemento G0 .

Denición 1.1.20. Si G = (V, E) es un grafo y e = uv ∈ E , se denota G/e

La gura 1.11 muestra un grafo G y el resultado de contraer una arista

Denición 1.1.21. Se llama subdivisión de un grafo G = (V, E) a cualquier

Teorema 1.1.32. Se G = (V, E) un grafo. Las armaciones siguientes son

Denición 1.1.38. Si k ≥ 0 es un entero, un grafo G = (V, E) se dice

Denición 1.1.39. Si k ≥ 0 es un entero, Un grafo G = (V, E) es k-conexo

Demostración. Para un número de vértices V jo, procedamos por inducción

Por ejemplo en el grafo de la gura 1.23 se tiene V = 11, A = 14, C = 5

Una manera de formalizar estas ideas es denir un multigrafo como una

Denición 1.3.1. Un grafo dirigido o digrafo es una cuaterna G = (V, E, φ, ψ)

Denición 1.3.4. Una caminata dirigida en un digrafo G = (V, E, φ, ψ) es

Denición 1.4.2. Un grafo G es k-colorable si admite una coloración con

Ejemplo 1.4.3. En unas jornadas cientícas se van a dictar cierto número

La conjetura de los 4 colores equivale entonces a la armación de que

Denición 1.5.3. Un grafo G es k-colorable por aristas si admite una colo-