TAREA I - MATEMÁTICAS DISCRETAS

DAVID CAMILO MOLANO VALBUENA

Aviso de Notación 1. Acá, cuando el nombre de las aristas no sea relevante, se

denotarán los caminos y ciclos por medio de sucesiones de vértices. Por ejem-
plo, el ciclo 1a2b3c4d1 se denotará por (1, 2, 3, 4) y el camino 1a2b3c4d también
por (1, 2, 3, 4). En cada caso mencionaremos si con una cuádrupla (1, 2, 3, 4) nos
referimos a un ciclo o a un camino. Además, todos los grafos considerados serán
finitos.
Ejercicio 1. ¿Cuántas aristas tienen Pn , Cn , Kn , Kn,m ?
Solución. Si V (Pn ) = {v1 , . . . vn }, entonces E(Pn ) = {vk vk+1 | 1 ≤ k ≤ n − 1}.
Por lo tanto, ||Pn || = n − 1.
Como Cn se puede construir de Vn añadiendo la arista v1 vn , ||Cn || = n.
El grafo K2 ∼= P2 tiene una arista. Y el grafo Kn puede ser construı́do de Kn−1
añadiendo un vértice, y una arista de éste a todos los vértices de Kn−1 . Ası́,
||Kn || = ||Kn−1 || + (n − 1). De este modo
n−1
X n(n − 1)
||Kn || = i= .
i=1
2
Con respecto a Kn,m , dada una bipartición de éste, es decir, V (Kn−1,m ) = V1 tV2
con |V1 | = n, |V2 | = m y E(Kn,m ) = {uv | u ∈ V1 , v ∈ V2 }, como para cada
vértice u ∈ V1 hay m aristas distintas que inician en u, y como V1 ∩ V2 = ∅,
||Kn,m || = nm. 
Ejercicio 2. Encuentra dos grafos con 6 vértices no isomorfos y con la misma
sucesión de grados.
Solución. Considérense los grafos G y H dados por V (G) = V (H) = {1, 2, 3, 4, 5, 6}
y E(G) = {12, 23, 34, 45, 26}, E(H) = {12, 23, 34, 45, 36}. Es decir, cuyos complejos
celulares asociados(I) son:
6 6

G: 1 2 3 4 5 ,H: 1 2 3 4 5 .

Ambos grafos tienen un vértice de grado 3 (En G es 2, en H es 3), dos vértices de

grado 2 (En G son 3, 4 y en H son 2, 4) y tres de grado 1 (En G y H son 1, 5, 6).
No son isomorfos ya que 2, el único vértice de grado 3 en G, tiene dos vértices
adyacentes de grado 1 y 3, el único vértice de grado 3 en H, solo tiene 1. 

Fecha: 7 de octubre de 2018.

(I)
Forma técnica de referirse al dibujo. A partir de ahora se ignorará la diferencia entre un grafo y
su complejo celular asociado.
1
2 DAVID CAMILO MOLANO VALBUENA

Ejercicio 3. Si |V (G)| ≥ 6 entonces G tiene 3 vértices mutuamente adyacentes

entre sı́ (Una inmersión de K3 en G), o bien 3 vértices mutuamente no adyacentes
entre sı́ (El complemento G tiene una inmersión de K3 ).
Solución. Sea v ∈ V (G) y supongamos que d(v) ≥ 3. Entonces existen al menos
3 vértices v1 , v2 , v3 ∈ V (G) adyacentes a v. Si existen i 6= j ∈ {1, 2, 3} tales que
vi vj ∈ E(G) entonces los vértices v, vi y vj son mutuamente adyacentes entre
sı́. Si no existen tales i, j, entonces v1 , v2 y v3 son mutuamente no adyacentes
entre sı́. Por el contrario, supongamos que d(v) < 3. Entonces existen al menos
3 vértices v1 , v2 , v3 que no son adyacentes a v. Si existen i 6= j ∈ {1, 2, 3} tales
que vi vj ∈/ E(G) entonces v, vi y vj son mutuamente no adyacentes entre sı́. De
lo contrario, v1 , v2 y v3 son mutuamente adyacentes entre sı́. En cualquiera de los
casos se llega a la conclusión deseada. 
Ejercicio 4. Un grafo G = (V, E) tiene al menos |E| − |V | + 1 ciclos.
Lema 1. Sea G un bosque (Grafo posiblemente disconexo sin ciclos). Entonces G
tiene a lo más |G| − 1 aristas.
Demostración del lema 1. Sea C el conjunto de las componentes conexas C de G.
Cada una de ellas es un árbol, con |C| = nC y
X
nC = |G|.
C∈C

Cada componente de G tiene nC − 1 aristas. Por lo tanto G tiene

X X
nC − 1 = nC − |C|
C∈C C∈C

aristas. Como |C| ≥ 1, G tiene menos de |G| − 1 aristas. 

Solución. Se realizará por inducción sobre m = |E|, para un grafo con n vértices.
Si m ≤ n − 1 entonces m − n + 1 ≤ 0, es decir, no se está exigiendo nada, en
particular, esto hace el caso m = 0 trivial. Supongamos, vı́a inducciı́on, que m ≥ 1
y que todo grafo con m − 1 aristas posee al menos m − n + 1 ciclos. Por lo
mencionado anteriormente, solo tenemos que considerar el caso m > n − 1. En
este caso, por el lema 1, G tiene al menos un ciclo α. Sea e ∈ E(α) y consideremos
el grafo G0 = G − e. Entonces G0 tiene m − 1 aristas y al menos un ciclo menos
que G. Aún ası́, por hipótesis de inducción |G| tiene al menos m − n ciclos. Por lo
tanto G tiene los m − n ciclos de G0 , y α, que no es un ciclo en G0 . Por lo tanto,
G tiene al menos m − n + 1 ciclos. 
Ejercicio 5. Sea d ∈ N y V := {0, 1}d . El grafo Qd con vértices V , que se define
de modo que ab ∈ E(Qd ) si y solo si a y b difieren en exactamente una coor-
denada se llama el cubo d−dimensional. Determine el grado promedio, el grosor,
circunferencia, y diámetro de este grafo.
Observación 1. El cubo Qd puede verse como el grafo conseguido de la unión
de dos subgrafos disyuntos isomorfos a Qd−1 añadiendo 2d−1 aristas. En efecto,
consideremos
V1 = {a = (a1 , . . . , ad ) ∈ V (Qd ) | ad = 1}
y
V0 = {a = (a1 , . . . , ad ) ∈ V (Qd ) | ad = 0}.
 TAREA I - MATEMÁTICAS DISCRETAS 3

Es claro que V (Qd−1 ) = V1 t V0 . Además, cada elemento a = (a1 , . . . , ad−1 , 0) de

V0 difiere en al menos una coordenada (La d−ésima) con los elementos de V1 , y
en exactamente una solamente con a0 = (a1 , . . . , ad−1 , 1). Ası́ para cada elemento
a ∈ V0 existe exactamente una arista entre a y un elemento de V1 , a0 . De este modo
V (Qd ) = V1 t V2 y E(Qd ) = E(G(V1 )) t E(G(V0 )) t {aa0 | a ∈ V0 }. Como V0 y V1
tienen el mismo número de elementos, son disyuntos, y V (Qd ) tiene 2d elementos
(Los detalles están abajo, en la Solución del ejercicio), entonces {aa0 | a ∈ V0 } tiene
2d d−1
2 = 2 elementos. Además, la proyección πd : {0, 1}d → {0, 1}d−1 dada por
(a1 , . . . , ad−1 , ad ) 7→ (a1 , . . . , ad−1 ) determina un isomorfismo entre G(Vs ) y Qd−1 ,
para s ∈ {0, 1}, ya que E(G(Vs )) consiste en todos los elementos de la forma ab tal
que a y b difieren en exactamente una coordenada distinta de la d−ésima. También
se observa que la función ν dada por a 7→ ed − a es un isomorfismo entre G(V0 )
y G(V1 ) ya que ν = (πd |−1 V1 ) ◦ πd |V0 (Donde ed = (0, 0, . . . , 0, 1)).

Solución. Supongamos que tenemos el vértice a = (a1 , . . . , ad ) con ai ∈ {0, 1}.

Hay exactamente d vértices que difieren exactamente en una coordenada con a,
dı́gase, a(i) := (a1 , . . . , ai−1 , 1 − ai , ai+1 , . . . , ad ). Ası́, cada vértice tiene grado d,
de modo que el grado promedio también es d. Como hay 2d vértices, entonces
2d
1X
||Qd || = d = d2d−1 .
2 i=1

Para calcular el grosor, se toma un vértice arbitrario a como arriba. Cualquier

arista λ será entre a y un vértice a(i) que difiere en la coordenada i−ésima con
a, para un i ∈ {1, . . . , d}. Como Qd es simple, no hay más aristas entre a y a(i),
de modo que no se puede escoger un ciclo de longitud 2. Una segunda arista
µ iniciando en a (O a(i)) tendrá que ser entre a (O a(i)) y un vértice a(j) (O
a(i)(j)) para j 6= i. En este caso no habrá ninguna arista entre a(i) (O a) y a(j)
(O a(i)(j)), ya que difieren en dos coordenadas. Ası́ que no hay ciclos de longitud
3. Por último, dado a, existe el ciclo (a, a(i), a(i, j), a(j)) para cualesquiera i, j, ya
que consecutivamente difieren en solo una coordenada.

a(j) a(i)(j)

a a(i)

Asi, el grosor es 4. Para calcular la circunferencia, consideramos que, dado que Qd

tiene 2d vértices, un ciclo no puede tener longitud mayor a 2d . Demostraremos
la existencia de un ciclo de tal longitud, por inducción sobre d ≥ 2. Para d =
2, Qd es un ciclo de longitud 4 = 22 = 2d (Un cuadrado) ası́ que el resultado
se sigue. Ahora, supongamos que para d > 2, el grafo Qd−1 tiene un ciclo de
longitud 2d−1 . Para el grafo Qd , lo separamos en los dos subgrafos G(V1 ) y G(V0 )
isomorfos a Qd−1 como en la observación anterior. En G(V0 ) tomemos el ciclo α =
d−1
(a(1) , a(2) , . . . , a(2 ) ) (Se usan superı́ndices para evitar ambigüedad) de tamaño
4 DAVID CAMILO MOLANO VALBUENA

d−1
2d−1 y el ciclo correspondiente ν(α) = (ν(a(1) ), ν(a(2) ), . . . , ν(a(2 ) )).(II) De α
d−1 d−1
removemos la arista a(1) a(2 ) y de ν(α) la correspondiente: ν(a(1) )ν(a(2 ) ). En
d−1 d−1
su reemplazo, agregamos las aristas a(1) ν(a(1) ) y a(2 ) ν(a(2 ) ). El nuevo ciclo
en Qd es:
d−1 d−1 d−1
−1)
(a(1) , a(2) , . . . , a(2 )
, ν(a(2 )
), ν(a(2 ), . . . , ν(a(1) )),
que tiene longitud 2d . Por lo tanto Qd tiene un ciclo de longitud 2d (Es Hamiltoniano);
ése es su grosor.
Con respecto al diámetro, dado que una arista solo existe entre vértices que
difieran en exactamente una coordenada, un camino (path) entre dos vértices a, a0
que tienen todas sus coordenadas distintas, debe tener al menos d aristas. Y en
efecto existe tal camino:
(a, a(1), . . . , a(1)(2) · · · (d) = a0 ).
Por lo tanto el diámetro es d + 1 (Definida la longitud como el número de vértices).

Ejercicio 6. Realizar los cálculos del Ejercicio 5 para el grafo de Petersen.
Solución. En el grafo de Petersen G:
6

1
7 A
2 5

3 4

8 9
todos los vértices son de grado 3, ése es el grado promedio. Hay 15 aristas. Como
el grafo es simple no hay ciclos de longitud 2. Como no hay triángulos, no hay
ciclos de longitud 3. Sea v un vértice arbitrario del grafo de Petersen y tomemos
una arista vw ∈ E(G). Un ciclo γ en el grafo de Petersen puede estar contenido en
el subgrafo exterior (Inducido por el conjunto de vértices {6, 7, 8, 9, 10}), interior
(Inducido por {1, 2, 3, 4, 5}), o en su defecto tener la misma longitud que uno que
tenga la arista 16. En el primer y segundo caso, los subgrafos exterior e interior
son ciclos isomorfos a C5 ; en estos casos |γ| = 5. Para el tercer caso, iniciemos con
el vértice 6, intentaremos construir un ciclo de tamaño mı́nimo que lo contenga, y
veremos con esto que su longitud mı́nima debe ser 5. Hay 3 aristas que contienen
a 6, que son 67, 6A y 61. Iniciemos con 67. Hay dos posibilidades para otra arista
que contenga a 7. Son 72 y 78. Del mismo modo solo hay dos opciones restantes
para 6, que son 6A y 61, de lo que surgen 4 casos. Pero en cada uno de los casos,
agregando 78 y 6A, 72 y 61, 78 y 61, 72 y 6A, no podemos añadir la última arista
para crear un ciclo de longitud 4, ya que, en cada caso respectivo 8 y A, 2 y 1,
8 y 1, 2 y A no son adyacentes. Por lo tanto el grosor es de 5. Para calcular la
(II)
Notemos que para un vértice a, ν(a) es simplemente el vértice a(d), que, en particular, es adyacente
con a.
 TAREA I - MATEMÁTICAS DISCRETAS 5

circunferencia demostraremos que no existe un ciclo de longitud 10, pero sı́ uno
de longitud 9. Supongamos, por el contrario, que existe un ciclo γ de longitud 10
(Cambiando el nombre de los vértices de manera adecuada para que queden de
manera consecutiva). Entonces G consiste en el ciclo, y 5 aristas que no están en
él.
3 2

4 1

5 A

6 9

7 8 .

Como G no tiene ciclos de longitud 2, 3 y 4, estas aristas no pueden estar en

vértices consecutivos de γ, ni en vértices a distancia 2 o 3 entre sı́ en γ. Si
hubiese, en G, una arista entre 2 vértices a distancia 4 entre sı́, por ejemplo, 1 y
5, entonces, dado que el grado de cada vértice es 3, no hay una arista entre A
(El vértice opuesto a 5) y 5. De este modo hay una entre A y 6 o entre A y 4.
En ambos casos habrı́a un ciclo de longitud 4, que serı́a (1, 5, 6, A) o (1, 5, 4, A)
respectivamente. Como la escogencia de la etiqueta para los vértices es arbitraria,
no hay aristas en G entre vértices a distancia 4 entre sı́ en γ. La única manera
restante de colocar las 5 aristas faltantes serı́a entre cada vértice y su opuesto.

3 2

4 1

5 A

6 9

7 8

Pero de este modo habrı́a ciclos de longitud 4, e.g. (1, 2, 7, 6). Siendo todos los
casos anteriores imposibles, no puede haber un ciclo de longitud 10 en G. Pero
hay ciclos de longitud 9 (Volviendo a los nombres originales de los vértices de
G), e.g. (1, 3, 5, 2, 4, 9, 8, 7, 6). Ası́, la circunferencia es 9. Para calcular el diámetro,
tómense dos vértices de G. si ambos están en el subgrafo exterior o interior, están
a distancia 1, 2 o 3 (Definida la distancia usando vértices). Si por el contrario, uno
está en el exterior y el otro en el interior, la distancia entre ellos será 2 (Si son
adyacentes) o 3 si no. Por lo tanto el diámetro es 3 (Si se define la distancia usando
aristas es 2). 
6 DAVID CAMILO MOLANO VALBUENA

Ejercicio 7. Todo grafo conexo con al menos dos vértices contiene un par de
vértices diferentes x, y tales que G − x y G − y son conexos.
Solución. Se realiza por inducción sobre n = |G|. Para n = 2 es trivial. Sea n > 2
y supongamos que para todo grafo G con |G| < n el resultado se cumple. Sea
v ∈ V (G). Si G − v es conexa entonces aplicamos el resultado a G − v: Existen
x, y ∈ V (G − v) tales que G − v − x y G − v − y son ambos conexos. Si G − x es
disconexo, eso significa que G es como sigue:

x v
G−v−x

Si además G − y también fuera disconexo, tendrı́amos el siguiente caso

x

v
G − {v, x, y}

que en realidad es imposible: En ese caso tanto G − x como G − y son conexos.

Por lo tanto, además de G − v, G − x o G − y debe ser conexo.
Si, por el contrario, G − v es disconexo, entonces cionsideramos dos compo-
nentes conexas de G − v, C1 , C2 . Si |C1 | = |C2 | = 1 entonces G − Ci es conexo para
i = 1, 2 (Ya que v conecta las demás componentes conexas de G − v). Si |Ci | > 1
para algún i ∈ {1, 2} entonces podemos encontrar dos puntos xi1 , xi2 ∈ V (Ci ) de
modo que Ci − xij es conexo para j = 1, 2. Si vxij ∈ / E(G) para algún j, entonces
G − xij es conexo (Ya que existe una arista entre v y algún otro vértice de Ci y
que Ci − xij es conexo.) Si vxij ∈ E(G) para todo j, entonces para cualquier j,
G − xij es conexo. Esto nos da, al contar ambas componentes, entre 2 y 4 vértices
G, en particular, dos de ellos, z1 , z2 , tales que G − z1 , G − z2 es conexo, que es lo
que se querı́a demostrar. 
Ejercicio 8. (a) ¿Cn es un subgrafo de Kn ? ¿Para qué n, m se satisface Kn,n ⊆
Km ? ¿Para qué n se satisface Cn ⊆ Kn,n ?
Solución. Acá, cualquier grafo G tendrá como conjunto de vértices a {1, . . . , |G|}
(Esto facilitará la notación en (a) y (b) donde, en caso contrario, habrı́a que construir
isomorfismos). También, para Cn , diremos que E(Cn ) = {12, 23, . . . , (n − 1)n, n1}.
(a) En efecto, V (Cn ) = V (Kn ) ası́ que por la definición de Kn , E(Cn ) ⊆ E(Kn ). Ası́,
Cn ⊆ Kn . (b) Se requiere que 2n ≤ m. Siempre que esto se satisfaga, V (Kn,n ) ⊆
V (Km ). Además, por la definición Kn , E(Kn,n ) ⊆ E(Km ). (c) Como Kn,n es bi-
partito, entonces n no puede ser impar. Mientras esto se cumpla, Cn ⊆ Kn,n . En
efecto, dada una bipartición (J, K) de Kn,n , podemos renombrar algunos vértices
de Kn,n de modo que 1, 3, . . . , n − 1 ∈ J y 2, 4, . . . , n ∈ K. Consideremos la inclu-
sión i : V (Cn ) → V (Kn,n ). Sabemos que J 0 = {1, 3, . . . , n − 1}, K 0 = {2, 4, . . . , n}
forman una bipartición de Cn . Veamos que i es un isomorfismo entre Cn y i(Cn ).
Pero en efecto, como Kn,n es completamente bipartito y para todo i ∈ {1, . . . , n},
i, i+1 pertenecen a diferentes elementos de las biparticiones de Cn , Kn,n , entonces
 TAREA I - MATEMÁTICAS DISCRETAS 7

i(i + 1) ∈ E(Cn ) si y solo si i(i + 1) ∈ E(Kn,n ) para todo i ∈ {1, . . . , n} = V (Cn ).

Entonces la inclusión Cn → i(Cn ) ⊆ Kn,n , en efecto es un isomorfismo de gra-
fos. 

Ejercicio 9. ¿Cuál es el máximo número de aristas que un grafo no-conexo con n

vértices puede tener?
Solución. Si G es un grafo disconexo entonces existen dos subconjuntos V1 y V2
de G tales que E(G) = E(G(V1 )) t E(G(V2 )). Sean m = |V1 |, k = |V2 |. Entonces
n = m + k y |E(G)| = |E(G(V1 ))| + |E(G(V2 ))| ≤ m(m−1) 2 + k(k−1)
2 .(III) Como
m = n − k, entonces tenemos que maximizar:
k(k − 1) (n − k)(n − k − 1) 1 2
= k 2 − nk +


η(k) = + n −n ,
2 2 2
con 1 ≤ k ≤ n − 1 (Estamos suponiendo que el grafo es disconexo).
La parábola asociada al polinomio tiene su vértice en k = n2 . Como además
su coeficiente lider es positivo, se abre hacia arriba. De esto, f es simétrica con
respecto a la recta k = n2 , además es creciente para k ≥ n2 y decreciente para
k ≤ n2 . Por consiguiente, va a tomar su valor máximo cuando k = n−1 o en el caso
análogo, cuando k = 1. En este caso, el valor máximo será η(n − 1) = (n−1)(n−2)
2 .
El valor máximo se cumple, naturalmente, cuando G(V1 ) es un grafo completo y
V2 es un punto aislado. 

Ejercicio 10. Si G es conexo y contiene un ciclo, entonces existe una arista e tal
que G − e es conexo.
Solución. Sea α un ciclo en G y e = xy ∈ E(α). Sean u, v ∈ V (G − e). Si existe
una caminata en G entre u y v que contiene a e, dı́gase θ = uβxeyγv, entonces
existe un camino entre x y y distinto de xey, dı́gase, δ = α − e. La caminata
θ0 = uβxδyγv es una caminata que pasa por e una vez menos que θ. Repitiendo
el proceso, construimos una caminata entre u, v que no pasa por θ (Evitamos usar
caminos (paths) ya que podrı́a haber aristas repetidas al tomar el camino α − e y
concatenarlo con β y γ). Por lo tanto, existe un camino entre u y v en G − e. 

Ejercicio 11. Todo grafo conexo G contiene un camino de longitud al menos

mı́n(2δ(G) + 1, |G|).
Lema 2. Sea G un grafo conexo con más de 3 vértices. Entonces G tiene un camino
de longitud al menos 3.
Demostración del lema 2. Sean u, v ∈ V (G) adyacentes. Entonces existe un vértice
w ∈ v(G) adyacente a u o v y diferente de v o u respectivamente (En caso contrario
G serı́a disconexo). El camino u(uv)v(vw)w o en su defecto w(wu)u(uv)v tiene
longitud al menos 3. 

Solución del Ejercicio. Si |G| ≤ 2 entonces G solo puede ser, o un punto, o un

camino de longitud 2. El caso de un punto es trivial ya que 2δ(G) + 1 = |G| = 1,
y ésta es la longitud del camino trivial. El caso cuando G es el camino de longitud
2 también es trivial ya que G es el mismo camino buscado.

(III)
La desigualdad surge de que G(V1 ), G(V2 ) tienen a lo más tantas aristas como los grafos completos
en sus números de vértices.
8 DAVID CAMILO MOLANO VALBUENA

Supongamos que |G| ≥ 3 y sea α = (v1 , · · · , vk ) un camino en G de longitud

máxima. Si α pasa por todos los vértices de G entonces su longitud es |G| y hemos
concluı́do.
Supongamos que α no pasa por todos los vértices de G. Notemos además
que todos los vértices adyacentes a v1 y vk están en α. En caso contrario, si
u ∈ / V (α) fuese adyacente a, digamos, v1 , entonces el ciclo α0 = (u, v1 , · · · , vk )
tendrı́a longitud mayor que la de α, una contradicción.
Ahora veremos que si, para algún i ∈ {1, . . . , k − 1}, vi vk ∈ E(G) entonces
vi+1 v1 ∈ / E(G). Supongamos, por el contrario que vi vk , vi+1 v1 ∈ E(G). Como G
es conexo, existe u ∈ / V (α) tal que uvj ∈ E(G) para algún j ∈ {2, . . . , k − 1}.
Supongamos primero que i ≤ j. Entonces podemos modificar α como sigue, para
hacer un camino de mayor longitud:
Iniciamos con los vértices v1 , u y vk .Como u es adyacente a vj , añadimos
vj , vj+1 , . . . , vk−1 junto con las aristas uvj , vj vj+1 , . . . , vk−1 vk . Agregamos, además,
v2 , v3 , . . . , vi junto con las aristas v1 v2 , v2 v3 , v3 v4 , . . . vi−1 vi , vi vk . Si además i < j
agregamos los vértices vi+1 , . . . , vj−1 junto con las aristas
v1 vi+1 , vi+1 vi+2 , . . . , vj−2 vj−1
(Si i = j no se añade ninguna arista).
Entonces tenemos el camino
(u, vj , vj+1 , . . . , vk−1 , vk , vi , vi−1 , . . . , v2 , v1 , vi+1 , vi+2 , . . . , vj−2 vj−1 ),
que tiene longitud mayor que la de α, lo cual es imposible.
Si j ≤ i analogamente se construye otro camino con α y u.
Por lo tanto se tiene, en efecto, que si vi vk ∈ E(G) entonces vi+1 v1 ∈
/ E(G),
dado, por supuesto, que |α| > 3.
Entonces A t B ⊆ V (α) donde A = {vi | vi v1 ∈ E(G)} ∪ {v1 } y B = {vi+1 |
vi vk ∈ E(G)} ∪ {vk }. Como d(v1 ) ≥ δ(G) entonces |A| ≥ δ(G) + 1. Del mismo
modo |B| ≥ δ(G). De este modo, |α| ≥ 2δ(G) + 1. 

Ejercicio 12. Si G es un grafo no conexo entonces G es conexo.

Solución del Ejercicio 12. Supongamos que G no es conexo y particionémoslo en
sus más de una componentes conexas. Tómense dos vértices v, v 0 ∈ V (G). Si están
en diferentes componentes conexas de G, entonces existe un camino en G que los
conecta. Si, por el contrario, están en la misma componente conexa, y tomamos un
vértice w en otra componente conexa, entonces hay un camino en G que conecta
v con w, y otro que conecta v 0 con w. Por lo tanto v, w y v 0 están en la misma
componente conexa de G. Como v y v 0 eran arbitrarios, G es conexo. 
Ejercicio 13. (a) P4 y C5 son autocomplementarios.
(b) Todo grafo autocomplementario es conexo.
(c) Si G es autocomplementario, entonces n ≡ 0, 1( (mód 4)).
(d) Todo grafo autocomplementario con 4k+1 vértices tiene un vértice de grado
2k.
Solución. (a) Si P4 está dada por

1 2 3 4

entonces P 4 está dado por

 TAREA I - MATEMÁTICAS DISCRETAS 9

1 2 3 4
.

Un isomorfismo entre P4 y P 4 se tiene mediante la correspondencia (1, 2, 3, 4) 7→

(2, 4, 1, 3). Con respecto a C5 , si está dado por

2 5

3 4 ,

i.e. E(C5 ) = {12, 23, 34, 45, 15}, entonces E(C 5 ) = {13, 14, 24, 25, 35}:

2 5

3 4 ,

Un isomorfismo lo da la correspondencia (1, 2, 3, 4, 5) 7→ (1, 3, 5, 2, 4).

(b) Si un grafo no es conexo, su complemento sı́ lo es. Como la conexidad es un
invariante, un grafo autocomplementario tiene que ser conexo.
(c) Si G es autocomplementario, entonces ||G|| = ||G||, ası́ que
n(n − 1)
= ||Kn || = 2||G||.
2
De lo anterior se sigue que n(n − 1) = 4||G||. Supongamos que n es impar.
Entonces n − 1 es par y 4||G||
n−1 = n es impar. Esto quiere decir que 4 | n − 1. Por
el contrario, supongamos que n es par. Entonces n − 1 = 4||G||
n es impar, ası́ que
4 | n. Si 4 | n − 1 entonces n ≡ 1 (mód 4). Si 4 | n entonces n ≡ 0 (mód 4), el
resultado esperado.
(d)Consideremos los vectores d(G) y d(G). Entonces d(G) = d(G). Si a cada
vértice de G le asignamos, de manera única, una fila de d(G) y d(G) por medio
de un orden en los vértices y las funciones dG , dG respectivamente, entonces la
función idéntica 1V induce una permutación σ ∈ S4k+1 que es una involución (La
permutación de las filas de los grados correspondientes a cada vértice en G y G).
10 DAVID CAMILO MOLANO VALBUENA

Pero una involución en un conjunto de cardinal impar tiene un punto fijo(IV). Por lo
tanto, existe una fila invariante bajo 1V . Eso significa que existe v ∈ V (G) tal que
dG (v) = dG (v). Ası́, si d = dG (v) entonces d = 4k − d, de donde d = 2k. 
Ejercicio 14. Sea Aut(G) el conjunto de todos los automorfismos de G. Entonces
Aut(G) es un grupo bajo la operación de composición.
Solución. Basta demostrar que Aut G es un subgrupo del grupo simétrico de G,
SG .
La función idéntica 1G es un automorfismo de G. En efecto, es biyectivo y
uv ∈ E(G) ⇔ 1G (u)1G (v) = uv ∈ E(G).
Ahora, sean σ, τ ∈ Aut G. Entonces στ −1 (u)στ −1 (v) ∈ E(G) (ya que σ ∈ Aut G)
si y solo si τ −1 (u)τ −1 (v) ∈ E(G), y esto sucede (ya que τ τ −1 (u) = u, τ τ −1 (v) = v)
si y solo si uv ∈ G. Entonces στ −1 ∈ Aut G. Por lo tanto, Aut G ≤ SG y, en
particular, Aut G es un grupo bajo la misma operación de SG : La composición. 
Ejercicio 15. Para cualquier grafo simple G, Aut G = Aut G.
Solución. Sea σ ∈ Aut G. Entonces σ(u)σ(v) ∈ E(G) si y solo si uv ∈ E(G). Ası́,
σ(u)σ(v) ∈ E(G) si y solo si σ(u)σ(v) ∈
/ E(G) si y solo si uv ∈
/ E(G) si y solo si
uv ∈ E(G), por lo tanto σ ∈ Aut G y Aut G ⊆ Aut G. Ahora, tomando G en lugar
de G, Aut G ⊆ Aut G = Aut G. Por lo tanto, Aut G = Aut G. 
Ejercicio 16. Sea D un digrafo. Demostrar:
− +
P P
(a) v∈V (D) d (v) = v∈V (D) d (v).
(b) Si |D| = n y todos los grados interiores de D son distintos entonces D es
acı́clico.
(c) Todo grafo simple G puede ser orientado para no tener ningún ciclo dirigido.
Lema 3. Si dado un digrafo D = (V, E) con |V | = n, se puede ordenar V como
(v1 , . . . , vn ) de modo que i < j cuando vi vj ∈ E(D), entonces D es acı́clico.(V)
Demostración del lema 3. Si construimos un ciclo (vi1 , vi2 , . . . , vir ) entonces i1 <
i2 < · · · < ir < i1 , lo cual es imposible. 
Solución del Ejercicio. (a) Toda arista contribuye exactamente una vez al grado in-
terno de un vértice, y exactamente una vez al grado externo de otro vértice.
Entonces X X
d− (v) = 1 = ||D||.
v∈V (D) e∈E(D)
Del mismo modo, X X
d+ (v) = 1 = ||D||.
v∈V (D) e∈E(D)
El resultado se sigue.
(b) En este caso se pueden renombrar los vértices de D de modo que V (D) =
{v1 , . . . , vn } y d− (vi ) = i − 1, i ∈ {1, . . . , n} (Como hay n grados distintos, con un
máximo de n − 1 aristas, estos tienen que ser 0, . . . , n − 1). Vemos que para todo
i ∈ {1, . . . , n − 1}, vi vn ∈ E(D), ya que d− (vn ) = n − 1. Además, como vn vn−1 ∈ /
(IV)
En efecto, si σ ∈ S4k+1 es una involución sin puntos fijos, entonces podemos particionar
{1, . . . , 4k + 1} en conjuntos de la forma {i, σ(i)}. Pero esto en realidad es imposible, ya que 4k + 1
serı́a par.
(V)
El converso también se cumple.
 TAREA I - MATEMÁTICAS DISCRETAS 11

E(D) y d− (vn ) = n − 2, entonces para todo i ∈ {1, . . . , n − 2}, vi vn−1 ∈ E(D).

Repitiendo el proceso, vemos que vi vj ∈ E(D) si y solo si i < j. Se sigue que D
es acı́clico. Pero también se sigue que D es una orientación del grafo completo Kn .
(c) Si un grafo G tiene n vértices, entonces G ⊆ Kn . En Kn podemos definir
una orientación, fijando v1 , trazando una arista dirigida v1 → vi para todo i > 1,
trazando una arista dirigida v2 → vi para todo i > 2, y repitiendo el proceso
hasta trazar una arista dirigida vn−1 → vn , como en (b). Por lo mismo que en (b),
esta orientación de Kn no tiene ciclos. Por lo tanto la orientación inducida en G
tampoco tiene ciclos. 
Ejercicio 17. Todo grafo conexo contiene una caminata que pasa por cada una de
sus aristas exactamente una vez en cada dirección.
Lema 4. Todo árbol contiene una caminata cerrada que pasa por cada una de sus
aristas exactamente una vez en cada dirección iniciando desde cualquiera de sus
vértices.
Demostración del lema 4. Se demostrará por inducción sobre el número de vérti-
ces. Para un árbol de un vértice se cumple vacı́amente. Para el de dos vértices solo
se recorre la única arista en ambas direcciones desde cualquiera de los vértices.
Ahora, tómese un árbol T con n > 2 vértices y supongamos que todo árbol con
menos de n vértices tiene una caminata cerrada desde cualquiera de sus vértices
que recorre cada arista exactamente una vez en cada dirección. Sea v ∈ V (T ) y
consideremos el grafo T 0 = T − v. Si T 0 es conexo es porque v es una hoja.(VI) En
ese caso, consideramos el padre w de v, y por hipótesis de inducción realizamos
una caminata cerrada γ iniciando en w que pasa por cada una de las aristas de
T 0 exactamente una vez en cada dirección. Entonces la caminata v(vw)wγw(vw)v
inicia en v y pasa por cada una de las aristas de T exactamente una vez en cada
dirección.
Ahora, si T 0 no es conexo, entonces sus componentes conexas Ti , i ∈ {1, . . . , s}
son árboles, cada una de ellas con menos vértices que T exactamente un vértice
vi adyacente a v en T .(VII) Iniciando en vi , en cada Ti realizamos una caminata
cerrada γi que pasa por cada una de las aristas de Ti exactamente una vez en
cada dirección. Entonces, la caminata
v(vv1 )v1 γ1 v1 (vv1 )v(vv2 )v2 γ2 v2 (vv2 )v · · · v(vvs )vs γs vs (vvs )v
es una caminata cerrada iniciando en v que pasa por cada una de las aristas de T
exactamente una vez en cada dirección. 
Solución del ejercicio. Se sigue del lema al olvidar que la caminata es cerrada. 
Ejercicio 18. Se definen V(G), E(G) como los F2 −espacios vectoriales libres ge-
nerados por V (G) = {vi }ni=1 y E(G) = {ej }m j=1 respectivamente. La matriz de
incidencia B induce una transformación lineal B : E(G) → V(G) Pn mediante produc-
to matricial. En particular, si ej = vi1 vi2 , entonces B(ej ) = i=1 bij vi = vi1 + vi2
ya que bij = 1 si y solo si vi ∈ ej . También V(G) se puede identificar co-
mo P(V (G)) donde la suma es la diferencia simétrica, mediante un isomorfismo
(VI)
En caso contrario, habrı́a dos vértices adyacentes a v entre los cuales todavı́a hay un camino.
Junto con v y las aristas respectivas esto harı́a un ciclo.
(VII)
Si hubiese dos, entonces el camino entre ellos en T 0 , junto con las dos aristas entre ellos y v,
formarı́an un ciclo en T .
12 DAVID CAMILO MOLANO VALBUENA

Pn
i=1 αi vi 7→ {vi | αi 6= 0}. Con esto, demostrar que cada conjunto de vértices
está en la imagen de la matriz de incidencia de un grafo conexo si y sólo si tiene
cardinalidad par.
Solución. Primero, consideremos dos vértices v, w ∈ V (G). Sea α un camino entre
v y w, dı́gase vel1 vl1 · · · vlk−1 elk w. Defı́naes (α) = el1 + · · · + elk . Entonces
B ((α)) = v + vl1 + vl1 + vl2 + · · · + vlk−1 + vlk−1 + w = v + w.
Ahora, consideremos {vi1 , . . . , vir } con cardinalidad par. Tomando caminos αim
entre vim y vim+1 para m ∈ {1, 3, . . . , r − 3, r − 1} vemos que B((αim )) = vim +
vim+1 . Entonces
B((αi1 ) + (αi3 ) + · · · + (αir−1 )) = vi1 + vi2 + · · · + vir ,
de modo que {vi1 , vi2 , . . . , vir } está en la imagen de B (más exactamente, de φB
donde φ es el isomorfismo entre V(G) y P(V (G))). Recı́procamente, dadas aristas
distintas f1 , . . . , fs entonces B(f1 + · · · + fs ) tiene un número par de elementos,
siempre que G sea un grafo simple (Hay un número par de sumandos, y aristas
con algún vértice común causan que dos de los sumandos se cancelen: Seguirá
habiendo un número par de elementos). Por lo tanto, la imagen de B consiste
exactamente en los subconjuntos de V (G) de cardinalidad par. 
En los siguientes dos ejercicios la longitud de una caminata denota el número
de aristas (contando repeticiones) que posee.
Ejercicio 19. Sea A la matriz de adyacencia del grafo con n vértices G. Entonces
el número Akij es la cantidad de caminatas de longitud k desde vi hasta vj en G
para todo i, j ≤ n.
Solución. Se realizará por inducción sobre k. Para k = 1 Aij es el número de
aristas entre vi y vj : Las caminatas de longitud 1. Sea k > 1 y supongamos que
para todo i, j, Ak−1
ij es el número de caminatas de longitud k − 1 desde vi hasta
(k)
vj . Entonces, por un lado, el número Nij de caminatas de longitud k desde vi
(k−1)
hasta vj es la suma de los números Nimde caminatas de longitud k − 1 desde
vi hasta cada vértice vm multiplicados por el número dmj de aristas entre vm y
vj . Esto se escribirı́a ası́:
n
(k) (k−1)
X
Nij = Nim dmj .
m=1
Pero esto tiene forma de un producto matricial. Es decir, dadas las matrices N (k) =
(k) (k−1)
(Nij )i,j , N (k−1) = (Nij )i,j , D = (dij )i,j , es claro, primero, que D = A, y por
hipótesis de inducción, que N (k−1) = Ak−1 . Por lo tanto N (k) = Ak−1 A = Ak . El
resultado se sigue. 
Ejercicio 20. Sean G un grafo simple con n vértices y A su matriz de adyacencia.
Entonces G es conexa si y solo si (I + A)n−1 consiste de entradas positivas.
Solución. Por el ejercicio anterior, An−1 es la matriz cuya entrada ij consiste de
las caminatas de longitud n − 1 entre vi y vj . Entonces
n−1
X n − 1
n−1
(A + I) = Ak
k
k=0
 TAREA I - MATEMÁTICAS DISCRETAS 13

es una matriz cuya componente i, j es una combinación lineal con escalares po-
sitivos del número de caminatas de longitudes de todas las longitudes menores
o iguales a n − 1 entre vi y vj . Si (I + A)n−1 tiene sus entradas todas positivas,
entonces entre vi y vj hay al menos una caminata de longitud a lo más n − 1, y por
lo tanto G es conexo. Reciprocamente, si G es conexo, entonces entre cada dos
vértices vi y vj hay un camino, de longitud a lo más n−1 (Ya que hay n vértices), y
alguna de las matrices Ak , k < n tiene su entrada i, j positiva. Como las entradas
de todas las matrices Ak , k < n son no negativas, se sigue que (I + A)n−1 tiene
todas sus entradas positivas, que es lo que se querı́a demostrar. 
Ejercicio 21. Todo grafo simple G con n ≥ 6 vértices y 4n − 9 aristas tiene un
subgrafo con grado mı́nimo 5.
Solución. Primero veamos que la proposición es equivalente a que todo grafo
simple G con n ≥ 6 vértices y al menos 4n − 9 aristas tiene un subgrafo con
grado mı́nimo 5. En efecto: Si todo grafo con n ≥ 6 vértices y 4n − 9 aristas tiene
un subgrafo con grado mı́nimo 5, y tomamos uno con más aristas, solo hay que
removerlas para conseguir un subgrafo con exactamente 4n − 9 aristas, al cual se
le puede aplicar el resultado. El recı́proco es inmediato.
Dicho esto, la demostración se realizará por inducción sobre n = |G|. Para
n = 6, 4n − 9 = 15 = 6·5
2 , ası́ que G es completo y todos sus vértices tienen grado
5: El resultado se satisface. Ahora supongamos que n > 6 y que todo grafo con
|G| < n y ||G|| = 4|G| − 9 tiene un subgrafo con grado mı́nimo 5. Si dG (v) ≥ 5 para
todo v ∈ V (G) el resultado se tiene. En caso contrario tomemos v ∈ V (G) con
dG (v) ≤ 5. Consideremos el grafo G0 = G − v. Entonces G0 tiene n − 1 vértices y
al menos ||G|| − 4 = 4(n − 1) − 9 aristas. Aplicamos hipótesis de inducción: G0 tiene
un subgrafo con grado mı́nimo 5. Éste a su vez es un subgrafo de G: El resultado
se sigue. 
Ejercicio 22. ¿Para qué n, m ∈ Z existe un homomorfismo Cn → Cm ?
Lema 5. Sea G un grafo y γ una caminata cerrada de longitud impar(VIII). Entonces
G contiene un ciclo.
Demostración del lema 5. Se demostrará por inducción sobre la longitud de γ.
La caminata cerrada más pequeña posible es un ciclo (Un lazo de hecho). Sea
γ = (v, v1 , v2 , . . . , vn , v). Si v aparece solamente 2 veces y ningún otro vértice se
repite, entonces γ es un ciclo. Si v aparece varias veces y ningún otro vértice se
repite entonces el grafo por el que pasa γ es de alguna de las formas siguientes.
w P2

v v

P P1

donde, en el caso de la izquierda, P es un camino que al añadir v (Con las aristas

que conectan v con P ) es un ciclo (Que además es de orden impar). En este caso
la caminata serı́a (v, w, v, v3 , . . . , vn , v) o (v, v1 , v2 , . . . , vn−2 , v, w, v). En el caso de
(VIII)
En este ejercicio, la longitud denotará la cantidad de veces que γ pasa por aristas.
14 DAVID CAMILO MOLANO VALBUENA

la derecha, se tienen varios ciclos (Uno de los cuales es de orden impar) que se
intersecan por pares en v. Los demás casos son combinaciones del de la izquierda
y el de la derecha (Donde tenemos cierta cantidad de vértices de grado 1 y al
menos un ciclo de orden impar). En todos los casos, el resultado se satisface.
Ahora supongamos que hay más vértices repetidos, i.e., que la caminata es de la
forma
(v, v1 , . . . , vi , vi+1 . . . , vj−1 , vj = vi , . . . , vn , v).
Entonces γ se puede descomponer en dos caminatas α, β más pequeñas que γ,
dı́gase (vi , vi−1 , . . . , v1 , v, vn , vn−1 , . . . , vj = vi ) y (vi , vi+1 . . . , vj−1 , vj = vi ). Alguna
de ellas tiene longitud impar, dı́gase, α; aplicamos la hipótesis de inducción sobre
ésta, i.e. α tiene un ciclo.(IX) 
Solución del ejercicio. Si m = 1 el homomorfismo solo existe cuando n = 1. Supon-
gamos que m ≥ 1. Si n es par, el homomorfismo siempre existe. Sea V (Cn ) = Zn
(Análogo para Cm ) y E(Cn ) = {01, 12, . . . , (n − 1)n, n0}. Sea f : Cn → Cm dado
por 
1 si k es impar,
k 7→
0 si k es par.
Entonces f es un homomorfismo. En efecto, para cada i ∈ Zn , i(i + 1) ∈ E(Cn ), y
además f (i) 6= f (i + 1) con f (i) ∈ {1, 2}, ası́ que f (i)f (i + 1) ∈ E(Cm ). Ahora, si
n es impar, el homomorfismo no existe si m es par. En efecto, supongamos, por el
contrario, que g : Cn → Cm existe. Entonces, como vimos, existe un homomorfismo
f : Cm → C2 = P2 . Entonces h = f g : Cn → P2 es un homomorfismo. Pero esto
es imposible. En efecto, si etiquetamos los vértices de P2 de modo que h(0) = 0,
entonces h(1) = 1, h(2) = 0 y ası́, h(n − 1) = 0 y h(0) = 1, una contradicción.
Ahora, supongamos que n, m son impares, entonces n − m es par. Si n ≥ m
entonces el homomorfismo existe; es la función f : Zn → Zm , dada por f (i) = i
para i < m, f (i) = 0 para i = m y para i > m:

0 si i es impar
f (i) =
1 si i es par.
Entonces, como m−n es par, f está bien definida, y además f es un homomorfismo
(El camino (0, . . . , m) es enviado en el ciclo (0, . . . , m − 1) = Cm , con 0, m 7→ 0
y el camino (m, . . . , n − 1, 0) es enviado en (0, 1) como en el caso de m, n pares,
con 0, m 7→ 0). Por último, supongamos que n < m. Entonces el homomorfismo
no existe. En efecto, si f : Cn → Cm es un homomorfismo, entonces al ver a Cm
como un camino cerrado, entonces su imagen es una caminata cerrada de longitud
impar, que, por el lema anterior, contiene un ciclo. Pero el único ciclo de Cm es el
mismo Cm , lo que implicarı́a que f es sobreyectiva, pero eso es imposible ya que
n < m. 

(IX)
Con las observaciones del principio, la demostración puede ir más lejos, afirmando que el ciclo
es de orden impar.