Capítulo 9

Tests y problemas de Grafos

9.1. Tests

1. Sea G un grafo simple con 35 aristas y tal que el grado de cada vértice es al menos
4. Entonces el número máximo de vértices que puede tener G es:
a) 17.
b) 16.
c) 18.
d) 8.
2. De las siguientes secuencias de grados de un grafo simple, indica cuál es imposi-
ble:
a) 1, 1, 2, 2, 3, 3, 4, 6.
b) 1, 1, 2, 2, 3, 3, 6.
c) 1, 1, 2, 3, 3, 6.
d) 1, 2, 2, 2, 2, 3, 3, 7
3. Sabemos que un grafo simple G = (V, A) posee diez vértices y que el grado de
cada uno de ellos es, al menos 6. Si además el número de aristas de G es múltiplo
de 13, concluimos que:
a) | A| = 39.
b) | A| = 26.
c) | A| = 52.
d) Ninguno de los anteriores.
4. Es posible conectar quince ordenadores de modo que cada uno esté conectado
exactamente con:
a) Otros tres.
b) Otros cuatro.
c) Otros cinco.

202
 203

d) Ninguno de los anteriores.

5. Si un grafo simple G tiene 14 aristas y su complementario G tiene siete aristas,
entonces el número de vértices de G es:
a) 6.
b) 5.
c) 8.
d) 7.
6. Si M es la matriz de adyacencia de un grafo de orden 7 y el elemento en la posi-
ción (1, 4) de la matriz M4 es 3, entonces:

a) Hay 4 caminos entres los vértices v1 y v4 con 3 vértices intermedios.

b) Hay 3 caminos de longitud 4 entre v1 y v4 .
c) Hay 3 aristas que unen v1 y v4 .
d) Hay 4 caminos de longitud 3 que unen v1 y v4 .

7. Dado un grafo de orden p, con matriz de adyacencia M tal que C = (cij ) p× p =

M + M2 + . . . + M p−1 , se tiene que:
a) Si C 6= 0, entonces el grafo es conexo.
b) Si cij = 1 entonces existe una arista entre los vértices vi y v j .
c) Si cii = p + 1 entonces el grafo es euleriano.
d) Si el grafo es conexo, entonces todos los elementos no diagonales de C son
no nulos.
8. Un grafo simple y conexo de 9 vértices y 36 aristas:
a) Es euleriano dependiendo de cómo estén conectados los vértices.
b) Nunca puede ser euleriano.
c) Es euleriano.
d) Es semieuleriano.
9. Sabemos que un grafo simple G posee 10 vértices y que el grado de cada uno de
ellos es, al menos, 6. Podemos afirmar que:
a) G es completo.
b) G es conexo.
c) G es euleriano.
d) Ninguno de los anteriores.
10. Sea un grafo G que admite la siguiente representación gráfica
 204

v1 v2 v3

v7

v6 v5 v4

Entonces G:

a) Es euleriano.
b) Es bipartido.
c) Tiene por matriz de adyacencia:
 
0 1 0 0 0 1 0
 
1 0 1 0 1 0 0
 
 
 
0 1 0 1 0 0 1
 
 
M = 0
 
 0 1 0 1 0 0
 
0 1 1 1 1 0 1
 
 
 
1 0 0 0 1 0 0
 
 
0 0 1 0 1 0 0

d) Ninguno de los anteriores.

11. Sea tiene un grafo G de orden 8 con 5 aristas, entonces:

a) G tiene dos componentes conexas.
b) G es conexo.
c) G tiene, al menos, tres componentes conexas.
d) Ninguna de las anteriores es cierta.
12. Si M es la matriz de adyacencia de un grafo de orden 7 y el elemento en la posi-
ción (1, 4) de la matriz M2 es 3, entonces:
a) Hay dos caminos entre los vértices v1 y v4 con tres vértices intermedios.
b) Hay dos caminos de longitud 3 entre v1 y v4 .
c) Hay tres caminos entre v1 y v4 cada uno con un vértice intermedio.
d) Ninguna de las anteriores es correcta.
13. Un grafo simple y conexo de nueve vértices y 36 aristas:
a) Es imposible.
b) No puede ser completo nunca.
 205

c) Es 7-regular y podría ser completo dependiendo de cómo estén conectados

los vértices.
d) Es completo.
14. Si G = (V, A) es 6-regular y | A| = 4|V | − 4, podemos afirmar que:
a) Tal grafo no existe.
b) El número de vértices es impar.
c) G no es un grafo simple.
d) El número de vértices es 6.
15. Si el grafo bipartido completo Km,12 tiene 72 aristas, entonces el valor de m es:
a) 5.
b) 8.
c) 6.
d) 4.
16. Para un grafo G = (V, A) de orden n, denotamos por gr(v) el grado de un vértice
v en G y por grc (v) el grado de un vértice v en el grafo complementario G. La
relación entre los grados de los vértices de un grafo simple y los grados de los
vértices de su grafo complementario es:
a) gr(v) + grc (v) = n.
b) gr(v) + grc (v) = n + 1.
c) gr(v) + grc (v) = n − 1.
d) No hay relación entre los grados de los vértices en G y G.
17. Los grafos Kn,m :
a) No pueden ser eulerianos.
b) Son eulerianos solo si n y m son impares.
c) Son semieulerianos si n es par y m impar.
d) Ninguna de las respuestas anteriores es correcta.
18. Sea G un grafo simple del que sabemos que tiene 60 aristas, un ciclo con un nú-
mero par de aristas, tres vértices de grado 2 y dos vértices de grado 3 y que el
resto de vértices tienen grado mayor o igual a 4, entonces:

a) Al menos hay otro ciclo con un número par de aristas.

b) El número máximo de vértices que puede tener es 32 .
c) El grafo es bipartido.
d) La situación descrita no puede darse.

19. sabemos que un grafo simple G = (V, A) tiene ocho vértices y es tal que el nú-
mero de aristas es múltiplo de 11, entonces:
a) El número de aristas es 22.
b) El grafo es conexo.
 206

c) Todos sus vértices deben tener grado menor que 6.

d) Todas las anteriores son ciertas.
20. Se tiene un grafo simple con 5 vértices y tal que él y su complementario tienen el
mismo número de aristas, entonces:

a) No existe un grafo simple con tales características.

b) El grafo es conexo.
c) El número de aristas es 5.
d) Ninguna de las anteriores es cierta.

21. Sea un grafo simple no conexo con 8 vértices, entonces podemos afirmar que:

a) Siempre tendrá al menos un vértice de grado menor o igual que 3.

b) Todos sus vértices deben tener grado menor que 4.
c) Hay un vértice de grado 3 y el resto tendrá grado menor o igual que 4.
d) Hay un vértice de grado 3 y el resto tendrá grado 2.

22. Sea un grafo G que admite la siguiente representación gráfica

v1 v2 v3

v7

v6 v5 v4

Entonces G:

a) Es semi euleriano.
b) Es bipartido.
c) Tiene por matriz de adyacencia:
 
0 1 0 0 1 1 0
 
1 0 1 0 1 0 0
 
 
 
0 1 0 1 0 0 1
 
 
M = 0
 
 0 1 0 1 0 0
 
1 1 1 1 1 0 1
 
 
 
1 0 0 0 1 0 0
 
 
0 0 1 0 1 0 0
 207

d) G no es bipartido.

23. Sabemos que un grafo simple G = (V, A) tiene ocho vértices y es tal que el nú-
mero de aristas es múltiplo de 11, entonces:
a) El número de aristas es 22.
b) El grafo es conexo.
c) Todos sus vértices deben tener grado menor que 6.
d) Todas las anteriores son ciertas.
24. Sea un grafo simple no conexo con 8 vértices, entonces podemos afirmar que:

a) Siempre tendrá al menos un vértice de grado menor o igual que 3.

b) Todos sus vértices deben tener grado menor que 4.
c) Hay un vértice de grado 3 y el resto tendrá grado menor o igual que 4.
d) Hay un vértice de grado 3 y el resto tendrá grado 2.

25. Sea un grafo G que admite la siguiente representación gráfica

v1 v2 v3

v7

v6 v5 v4

Entonces G:

a) Es euleriano.
b) Es bipartido.
c) Tiene por matriz de adyacencia:
 
0 1 0 0 0 1 0
 
1 0 1 0 1 0 0
 
 
 
0 1 0 1 0 0 1
 
 
M = 0
 
 0 1 0 1 0 0
 
0 1 1 1 1 0 1
 
 
 
1 0 0 0 1 0 0
 
 
0 0 1 0 1 0 0

d) Ninguno de los anteriores.

 208

26. Sea un grafo G que admite la siguiente representación gráfica

v1 v2 v3

v7

v6 v5 v4

Entonces G:

a) Es semi euleriano.
b) Es bipartido.
c) Tiene por matriz de adyacencia:
 
0 1 0 0 1 1 0
 
1 0 1 0 1 0 0
 
 
 
0 1 0 1 0 0 1
 
 
M = 0
 
 0 1 0 1 0 0
 
1 1 1 1 1 0 1
 
 
 
1 0 0 0 1 0 0
 
 
0 0 1 0 1 0 0

d) G no es bipartido.

9.2. Problemas

1. Un estudiante enuncia el siguiente teorema:

Teorema 9.1 Si un grafo es bipartido entonces cada ciclo tiene un número par de aristas.

Del que da la siguiente demostración:

Demostración. Sea G = (V, A) el grafo bipartido, tal que el conjunto de vértices
V se puede particionar en dos subconjuntos V1 y V2 .
Todo grafo bipartido tiene al menos un ciclo. Sea v1 , v2 , . . . , vn , v1 un ciclo. Su-
pongamos que v1 ∈ V1 . Como existe el eje v1 v2 se deduce que v2 ∈ V2 . Se tiene
que v3 ∈
/ V2 al existir la arista v2 v3 y resultará que v4 ∈ V2 , y así sucesivamente.
 209

Luego los vértices de subíndice impar están en V1 y los de subíndice para en V2 ;

luego n es par.


a) Di si la demostración es correcta o no. En caso de que la consideres incorrec-

ta, señala donde están los errores y qué debería corregirse para que ya fuese
correcto el razonamiento efectuado.
b) Si existen pasos que no están justificados completamente debes efectuar la
justificación completa, detallada paso a paso, de los mismos.

2. Sea G = (V, A) es un grafo simple y conexo con 7 vértices, todos de grado mayor
o igual que 2, y tal que dos de sus vértices tienen grado menor o igual que 3.
a) Calcula justificadamente el número mínimo y el número máximo de aristas
que puede tener.
b) En el caso anterior, ¿para qué números de aristas podrá asegurarse que no
hay caso alguno de grafo bipartido?
c) Pon un ejemplo de de un grafo cumpliendo las condiciones del enunciado
que sea además bipartido.
3. Sea G = (V, A) un grafo simple de orden n. Probar que si G no es conexo entonces
tiene al menos un vértice con grado menor que n− 1
2 .

4. Demostrar que:
a) Dos grafos G1 y G2 son isomorfos si y sólo si lo son sus complementarios G1
y G2 .
b) Si G1 y G2 son grafos simples con la misma matriz de adyacencia, entonces
G1 y G2 son isomorfos.
c) Poner un ejemplo de dos grafos isomorfos que tengan distinta matriz de
adyacencia.
5. En una sala hay 30 equipos informáticos con 73 pares de conexiones entre ellos:
a) Demuestra que al menos hay un equipo que está conectado a lo sumo a otros
4 equipos.
b) Supongamos que hay un equipo C que está conectado con algún otro y que
es el único que cumple que el número de conexiones a otros equipos es a lo
sumo 4. Demuestra que los demás equipos están conectados exactamente a
5 equipos cada uno. Calcula el número exacto de conexiones entre C y otros
equipos.
6. Para el grafo G de la figura
 210

a g

c f

b d e h

se pide:
a) Un circuito no simple de longitud 5.
b) Un camino simple no cerrado de longitud 3.
c) Un circuito simple de longitud 4.
d) ¿Es G un grafo euleriano?, ¿semieuleriano?, responde razonadamente. En
caso afirmativo indica una secuencia de vértices que permita un camino eu-
leriano en G.
7. Probar que cualquier grafo simple con secuencia de grados 4, 4, 3, 3, 3, 3, 3, 3 es
conexo.
8. Sea G = (V, A) un grafo con k componentes conexas. Probar que se verifica que

1
| A| ≤ (|V | − k)(|V | − k + 1).
2

Como consecuencia, probar que si | A| > 12 (|V | − 1)(|V | − 2), entonces G es co-
nexo.