Práctico 5

Matemática Discreta I  Año 2020/1

FAMAF
Ejercicios resueltos

1. ¾Cuántas aristas tiene el grafo completo Kn ? ¾Para cuáles valores de n se puede

encontrar un dibujo de Kn con la propiedad que las líneas que representen a las

aristas no se corten?

Rta: En un grafo completo de n vértices podemos contar las aristas de la siguiente

manera: del primer vértice salen n−1 aristas, del segundo salen n−2 pues no

debemos contar la arista al primer vértice, del tercer vértice salen n − 3 aristas (no
contamos las que van al primero y al segundo), y así sucesivamente. Concluyendo,

la cantidad de aristas es
n−1
X n(n − 1)
(n − 1) + (n − 2) + (n − 3) + · · · + 2 + 1 + 0 = i= .
i=0
2
Otra forma de contar es la siguiente: de cada vértice salen n−1 aristas. Si las

sumamos a todas tenemos n(n−1) aristas, pero cada arista está contada dos veces,
por lo tanto la cantidad total de aristas es n(n − 1)/2.
Con respecto a la segunda pregunta, es claro que podemos dibujar K1 , K2 y

K3 sin cruces de aristas. Aunque K4 solemos dibujarlo como un cuadrado con sus

diagonales, también podemos dibujar K4 sin cruces:

Sin embargo, no hay forma de dibujar K5 sin cruces entre las aristas. La demostra-

ción de este hecho no es sencilla y debemos convencernos tratando (y fracasando)

de hacer un dibujo de K5 sin cruces entre aristas.

1
FAMAF Matemática Discreta I

2. a ) Encuentre todos los grafos de 5 vértices y 2 aristas no isomorfos entre sí.

Rta: Hay 2 posibilidades:

(i) las dos aristas no se tocan, es decir, por ejemplo las aristas podrían ser

{v, v 0 }, {w, w0 }, donde v, v 0 , w, w0 son todos distintos.

(ii) las dos aristas se tocan en un punto, por ejemplo {v, v 0 }, {v 0 , w}, donde
0
v, v , w son todos distintos.

Luego, hay solo dos grafos no isomorfos entre sí. Dibujándolos son:

b ) ¾Cuál es el máximo número de aristas que puede tener un grafo de 5 vértices?

Rta: El grafo completo K5 es el que tiene todas las aristas posibles y estas son
5·4
= 10 (ver ejercicio 1).
2
3. Encuentre un isomorsmo entre los grafos dados por las siguientes listas (ambas

listas especican versiones de un famoso grafo conocido como el grafo de Petersen).

a b c d e f g h i j 0 1 2 3 4 5 6 7 8 9
b a b c d a b c d e 1 2 3 4 5 0 1 0 2 6
e c d e a h i j f g 5 0 1 2 3 4 4 3 5 7
f g h i j i j f g h 7 6 8 7 6 8 9 9 9 8

Rta:

Podemos dibujar el primer grafo y el segundo grafo de la siguiente forma:

0
a 9 1

f 8 2
e b
j g

7 3

i h
6 4

d c 5

2
Matemática Discreta I FAMAF

No es fácil darse cuenta que estos grafos son isomorfos. Sin embargo, reordenando

el segundo grafo, por ejemplo buscando cuales vértices forman un 5-ciclo, obtene-

mos

7 1
3 2

8 4

9 6

Luego, el isomorsmo viene dado por

a→0 c→6 e→7 g→2 i→8

b→1 d→9 f →5 h→4 j→3

4. Demuestre que los siguientes pares de grafos son isomorfos, especicando un

isomorsmo en cada caso.

(a)

Rta: Si mandamos, en orden, los puntos del rombo a los puntos del cuadrado, y el

punto del centro al punto exterior al cuadrado, obtenemos un isomorsmo.

(b)

3
FAMAF Matemática Discreta I

Rta: Observar que el primer grafo es un cubo. Si en el segundo grafo levantamos

el cuadrado del centro, podemos deformar ese grafo a un cubo.

5. Si G = (V, E) es un grafo, el grafo complemento es G0 = (V, E 0 ), donde E0 son

todos los 2-subconjuntos de V que no están en E. Es decir, el grafo complemento

tiene los mismos vértices que el grafo original y todas las aristas que le faltan a G
para ser un grafo completo.

a ) Halle el complemento de los siguientes grafos:

(i) (ii) (iii) (iv)

Rta:

(i) (ii) (iii) (iv)

b ) Si V = {v1 . . . vn } y δ(vi ) = di ∀ i = 1, . . . , n , calcule las valencias del grafo

complemento.

Rta: Si v es un vértice del grafo con valencia δ(v) = k , por denición de grafo

complemento, la valencia de v en el grafo complemento es n − 1 − k. Por lo

tanto, si denotamos δ 0 (v) la valencia de v en el grafo complemento, la respuesta

del ejercicio es δ 0 (vi ) = n − 1 − di ∀ i = 1, . . . , n .

6. Pruebe que los siguientes grafos no son isomorfos:

4
Matemática Discreta I FAMAF

Rta: Los grafos no son isomorfos pues el primero tiene un 3-ciclo y el segundo no

lo tiene.

Otra forma de ver que los grafos no son isomorfos es hallando sus grafos comple-

mento: el complemento del primer grafo es un ciclo y el complemento del segundo

grafo no lo es, y por lo tanto no son isomorfos.

7. Pruebe que si G es un grafo con más de un vértice, entonces existen dos vértices

con la misma valencia.

Rta: Si G es un grafo de n vértices, con n > 1, entonces como de cada vértice

pueden salir como máximo n − 1 aristas, las valencias pueden ser 0, 1, 2, . . . , n − 1.

Supongamos primero que en el grafo no hay vértices con valencia 0, por lo

tanto, las valencias posibles son 1, 2, . . . , n − 1, que son n−1 números, y como

tenemos n vértices, por el principio de las casillas hay una valencia que se repite.

Ahora, Si G tiene dos vértices con valencia 0, entonces se repite una valencia y
listo. Nos queda el caso de que hay un solo vértice de valencia 0. Si consideramos

el subgrafo que se obtiene eliminando el vértice de valencia 0, obtenemos un grafo

de n−1 vértices y cuyas valencias están en el rango 1, 2, . . . , n − 2, es decir n−2

valores posibles. Por lo tanto, uno de los valores de las valencias se repite.

8. Para cada una de las siguientes secuencias, encuentre un grafo que tenga exacta-

mente las valencias indicadas o demuestre que tal grafo no existe.

a) 3, 3, 1, 1
Rta: Como la suma de valencias es 3 + 3 + 1 + 1 = 8, el grafo debe tener

4 aristas. Como hay 4 vértices y dos de ellos tienen valencia 3, digamos a y

b, de esos vértices salen aristas que llegan a todos los otros vértices, es decir

tenemos la siguiente situación:

a b

d c

Por lo tanto, los dos vértices restantes tienen valencia 2 y habrían 5 aristas, esto
es contradictorio, lo cual nos dice que no puede haber un grafo con valencias

3, 3, 1, 1.
5
FAMAF Matemática Discreta I

b) 3, 2, 2, 1
Rta: Un grafo que cumple con esa secuencia es:

c) 3, 3, 2, 2, 1, 1
Rta: El grafo tiene 6 vértices y 12/2 = 6 aristas:

d) 4, 1, 1, 1, 1
Rta: El grafo tiene 5 vértices y 8/2 = 4 aristas. El único grafo posible es en el

cual desde un vértice salen 4 aristas a los otros vértices.

e) 7, 3, 3, 3, 2, 2
Rta: El grafo tendría 6 vértices, por lo tanto la valencia máxima podría ser 5

y es imposible que uno de los vértices tenga valencia 7.

f) 4, 1, 1, 1
Rta: Como la suma de las valencias 4+1+1+1 = 7 es impar, no existe un

grafo con esas valencias.

9. Sean G = (V, E) y G0 = (V 0 , E 0 ) dos grafos y sea α : V 7→ V 0 una función biyectiva

tal que δ(v) = δ(α(v)) ∀ v ∈ V .

a ) ¾Puede armar que α es un isomorsmo?.

Rta: No. Los grafos

6
Matemática Discreta I FAMAF

son regulares de valencia 3 y no son isomorfos: el primero tiene 3-ciclos y el

segundo no.

b ) ¾Puede armarlo si |V | = 3 ó 4?.

Rta: Si |V | = 3, los únicos grafos posibles son

La lista de valencias de estos grafos es {0, 0, 0}; {1, 1, 0}; {1, 1, 2} y {2, 2, 2},
respectivamente. Por lo tanto, la lista de valencias determinan el grafo.

En el caso que |V | = 4: tenemos un solo grafo sin aristas, un solo grafo con

una arista, y si seguimos agregando aristas, podemos ver que hay 2 grafos con

2 aristas, 3 grafos con 3 aristas, 2 grafos con 4 aristas, un grafo con 5 aristas

y un grafo con 6 aristas. Estos grafos son:

0→ 1→

2→

3→

4→

5→ 6→
Es fácil vericar que las valencias determinan el grafo.

7
FAMAF Matemática Discreta I

10. Encuentre una función del grafo A al grafo B que preserve valencias. ¾Es un

isomorsmo?.

A: B:

Rta: Todos los vértices tienen valencia 3 en ambos grafos, así que cualquier función

biyectiva entre los vértices del primer grafo y los vértices del segundo preserva

valencias. Sin embargo, ninguna de estas funciones es un isomorsmo de grafos,

pues el primer grafo tiene un 5-ciclo y el segundo no lo tiene.

11. Dados los siguientes grafos:

(1) (2) (3)

b 2 1

2 3
a e c 1 3

4 4 5
5
d
6 7
8

(5) (6)
(4)
1 2 b b

a e c a e c

5 4 3 d d

8
Matemática Discreta I FAMAF

(7)

1 2 3

4 6

7 8

9 10

11 12

a ) Determine en cada caso si existen subgrafos completos de más de 2 vértices.

Rta: En (1), hay varios K3 : abe, bec, aed, ecd. En (2), el subgrafo 1234 es un

K4 . En (3), no hay grafos completos. En (4), hay varios subgrafos isomorfos a

K3 , por ejemplo 145. En (5), no hay subgrafos completos. En (6), el aed es un

K3 . En (7), no hay grafos completos.

b ) Para el grafo (1), dé todos los caminos que unen a con b.

Rta: ab, adcb, adeb, adceb, adecb, aeb, aecb, aedcb.
c ) Dé caminatas eulerianas en los grafos (4), (5) y (6).

Rta: En el grafo (4), δ(2) = 3, δ(3) = 3 y todas las demás valencias son pares.

Luego la caminata debe salir de 2 y llegar a 3 o viceversa. Una caminata

posible es 234514213.
En el grafo (5), la caminata euleriana debe salir de a y llegar a c o viceversa.

Una caminata posible es: abcdaec.

En el grafo (6), la caminata euleriana debe salir de a y llegar a e o viceversa.

Una caminata posible es: abcedae.

d ) Para (2) y (3), decir si existen ciclos hamiltonianos.

Rta: En (2), no hay ciclos hamiltonianos que pasen por el vértice 5.

En (3) no hay ciclos hamiltonianos: observemos que un ciclo hamiltoniano

puede empezar de cualquier vértice. Supongamos que (3) tiene un ciclo ha-

miltoniano y lo empezamos del vértice 3. El comienzo del ciclo es 327, luego

podría ser (i) 3271 ó (ii) 3278.

9
FAMAF Matemática Discreta I

En el caso (i), solo puede continuar como 32716 y de ahí como 327168 o 327164.
El 327168 solo puede continuar en 3271687 repitiendo vértice sin ser ciclo. El

327164 solo puede continuar en 3271645 y ahí terminar sin ser ciclo.

En el caso (ii), solo puede continuar como 32786 y luego como 3278645 termi-

nando sin ser ciclo, o 3278617 repitiendo vértice sin ser ciclo.

e ) Determinar cuales de los siguientes pares de grafos son isomorfos:

(i) (4) y (2),

Rta: (2) tiene un vértice de valencia 1, mientras que en (4) todas las valencias

son mayores que 1, por lo tanto (2) y (4) no pueden ser isomorfos.

(ii) (5) y (6),

Rta: En este caso la lista de valencias de ambos grafos es 2, 2, 2, 3, 3 y por lo

tanto no podemos usar valencias para distinguir estos grafos. Ahora bien, en

(6) tenemos el 3-ciclo aed, mientras que en (5) no hay 3-ciclos, por lo tanto

(5) y (6) no son isomorfos.

(iii) (5) y (1).

Rta: En (1) hay un vértice de valencia 4 mientras que en (5) no lo hay, por lo

tanto los grafos no son isomorfos.

f ) Halle las componentes conexas del grafo (7).

Rta: Los subgrafos con vértices {1, 6, 12, 9}, {4, 2, 5} y {3, 7, 11, 10, 8} son las

componentes conexas de (7).

12. Dado el siguiente grafo

0 1 2 3 4 5 6 7 8
1 0 1 0 3 0 1 0 1
3 2 3 2 5 4 5 2 3
5 6 7 4 6 7 6 5
7 8 8 8 8 7.
encuentre un ciclo hamiltoniano (si existe). Determine si existe una caminata

euleriana, y en caso de ser así, encuentre una.

Rta: En general el problema de encontrar ciclos hamiltonianos es difícil de resolver,

pero en este caso hay una pista que nos puede ayudar: observar que los vértices

enumerados con números pares se relacionan solamente con vértices enumerados

10
Matemática Discreta I FAMAF

con números impares, y recíprocamente. Podemos dibujar el grafo poniendo todos

los vértices enumerados con números impares en una columna a la izquierda y los

enumerados con números pares a la derecha. Vemos como hay aristas que van de

un costado al otro pero no hay aristas dentro de la misma columna, estos grafos

se llaman bipartitos.

1 2

3 4

5 6

7 8

Ahora bien, más allá del dibujo, un ciclo hamiltoniano pasa por los 9 vértices y por

lo tanto debe tener 9 aristas. Si partimos de la columna de la izquierda (por ejemplo

del vértice 1), la primera arista va a la columna de la derecha, la segunda vuelve

a la columna de la izquierda, y así sucesivamente, hasta que nos damos cuenta

que una arista que comienza en un vértice enumerado con un número impar debe

terminar en la columna de la derecha. Si partimos de la derecha, el razonamiento

es análogo y podemos concluir: cualquier ciclo termina en la columna opuesta a

la de donde comienza. Por lo tanto no hay ciclos hamiltonianos.

Con respecto a las caminata eulerianas, como solo hay dos vértices de valencia

impar (2 y 6), hay caminatas eulerianas que van de 2 a 6 o viceversa. La cantidad

6·4+2·3+2
de aristas total es
2
= 16, que debe ser el largo de la caminata. Una posible
caminata es 21034567850723816.

13. Un ratón intenta comer un 3 × 3 × 3 cubo de queso. Él comienza en una esquina y

come un subcubo de 1 × 1 × 1, para luego pasar a un subcubo adyacente. ¾Podrá

el ratón terminar de comer el queso en el centro?

Rta: Podemos modelar este problema como un grafo en el espacio, con coordenadas

(x, y, z) para cada vértice, 0 ≤ x, y, z ≤ 2, lo cual se logra pensando cada vértice

como la representación de cada subcubo de 1 × 1 × 1. El grafo sería como en el

11
FAMAF Matemática Discreta I

siguiente dibujo, donde el vértice de partida está en gris y el vértice de llegada en

negro.

Más allá de la representación gráca, lo que se pregunta en el ejercicio es sobre

la existencia de un camino hamiltoniano desde (0, 0, 0) hasta (1, 1, 1), es decir, un

camino que comience en (0, 0, 0), pase por todos los vértices y termine en (1, 1, 1).
Veremos que no podremos hacer el camino requerido por el ejercicio y que la forma

de resolver el problema es similar a la del ejercicio 12.

Primero deniremos un concepto muy sencillo: diremos que una 3-upla de

enteros (x, y, z) es par si x+y+z es un número par, en caso contrario diremos

que es impar.

Ahora bien, podemos ver el pasaje de un vértice a otro como una operación

algebraica, por ejemplo, la arista que une (0, 0, 2) con (0, 1, 2) se obtiene sumando

(0, 1, 0) a (0, 0, 2). En general, para pasar de un nodo a otro debemos sumar o restar
(1, 0, 0) o (0, 1, 0) o (0, 0, 1), y es claro que al hacer esta operación cambiamos la

paridad del vértice. Notemos que si pasamos de v0 a v1 y de v1 a v2 (v0 , v1 , v2

vértices), entonces la parida de v0 es igual a la paridad de v2 . A partir de esta

observación, podemos concluir que si partimos de un vértice par y hacemos una

caminata con un número par de aristas, entonces terminaremos en un vértice par.

Ahora bien, el ejercicio nos pregunta sobre un camino hamiltoniano desde (0, 0, 0)
hasta (1, 1, 1), en este caso el camino hamiltoniano debería tener 26 aristas, pues

pasa por 27 vértices y por lo tanto, al partir de un vértice par, debería terminar en

otro vértice par, sin embargo (1, 1, 1) es un vértice impar, y concluimos que este

camino hamiltoniano no puede existir.

12
Matemática Discreta I FAMAF

14. Dé todos los árboles de 5 vértices no isomorfos.

Rta: Sabemos que un árbol (conexo por denición) con 5 vértices debe tener 4

aristas. Y que cualquier grafo con 4 aristas tendría un grado total (suma de todas

las valencias) de 8. Así que nuestro problema se reduce en encontrar árboles con

5 vértices cuyo grado total sea 8, y donde, cada uno de los vértices tiene valencia

≥ 1. Las posibles conguraciones de valencias son:

1, 1, 1, 1, 4
1, 1, 1, 2, 3
1, 1, 2, 2, 2

Veamos caso por caso.

1, 1, 1, 1, 4: es claro que en este caso hay un solo grafo posible,

1, 1, 1, 2, 3: se puede construir a partir del anterior cambiando una arista de

lugar

y vemos que no hay más.

1, 1, 2, 2, 2: en este caso solo podemos tener

13