DMATIC. ETSI Informáticos.

UPM Matemática Discreta II

Curso 21-22
NOCIONES BÁSICAS DE GRAFOS

REPRESENTACIÓN DE GRAFOS
1. Se considera el conjunto C = {1, 2, 3, 4, 5} y todos sus subconjuntos de cardinal 2. Construye y
dibuja el grafo cuyos vértices son los subconjuntos anteriores y donde la adyacencia se define así:
Dos subconjuntos son adyacentes si su intersección es vacía. El grafo resultante es el grafo de
Petersen.
2. Sea S una familia de subconjuntos de un conjunto A. El grafo de intersección para S tiene un
vértice por cada miembro de S, y dos vértices son adyacentes si sus correspondientes
subconjuntos tienen intersección no vacía.
a) Construye el grafo de intersección de la familia de todos los subconjuntos de {a, b, c}
b) Construye el grafo de intersección de la familia de todos los subconjuntos de {a, b, c, d}
SUCESIONES GRÁFICAS
3. a) A una fiesta asisten 20 invitados. Cada uno de ellos conoce a un número diferente de invitados.
¿Es esto posible?

b) Prueba que todo grafo sin bucles de orden n  2 tiene al menos dos vértices con el mismo grado.
4. Estudia si las siguientes sucesiones son gráficas:
a) 3,3,3,3,2 b) 1,2,3,4,4 c) 3,4,3,4,3 d) 1, 1, 2, 2, 3, 3
e) 3,3,2,2,2,2,1,1 f) 6,4,4,4,3,3,3,3 g) 5,3,3,3,2,2,1,1 h) 5,5,4,4,3,3,3,1,0,0
En caso afirmativo, obtén una representación gráfica.
5. Disponemos de 8ordenadores y 12 cables de conexión. Queremos que cada ordenador se conecte
con otros 3 ordenadores. ¿Existe alguna forma de conectarlos? ¿Es única?
6. ¿Es cierto que si un grafo tiene todos sus vértices de grado 2 entonces es un ciclo?
7. a) Si G es un grafo con 52 aristas y el grado de cada vértice es, al menos, cinco, ¿cuál es el máximo
número de vértices que puede tener G?
b) Si G es un grafo simple con 52 aristas, ¿cuál es el menor número de vértices que puede tener G?
8. Una empresa adquiere una red de ordenadores. Cada ordenador se conecta con, a lo sumo, cuatro
ordenadores y el número total de conexiones es 80. ¿Cuántos ordenadores se han comprado?
9. Un grafo tiene 12 vértices y el grado de cada uno de ellos es, al menos, 4. Si el número de aristas
es múltiplo de 13, ¿cuál es dicho número? ¿La solución es única?
10. ¿Cuál es el número mı́nimo de vértices que puede tener un grafo r−regular de 310 aristas?
11. Sea G un grafo simple de 11 vértices. Si el grado de cada vértice es al menos 6 y el número total
de aristas es múltiplo de 19, ¿cuántas aristas tiene G? ¿cuántas aristas tiene su grafo
complementario GC ?
GRAFOS BIPARTIDOS E ISOMORFOS
12. Determina cuales de los siguientes grafos son bipartidos:

1
DMATIC. ETSI Informáticos. UPM Matemática Discreta II
Curso 21-22

c b a
b a

f e
a b
d h g
c g h

d e c d e f

13. Para cada k  1, se define el grafo Mk  (Vk, Ak) con forma de k aspas de molino, con

Vk = {0, 1, 2, ..., 2k} y Ak = { {0, i} : 1  i  2k } ∪ { { 2i − 1, 2i } : i = 1, …, k}. Se pide:

a) Dibuja los grafos Mk para k = 1, 2, 3, 4.

b) ¿Para qué valores de k es el grafo Mk bipartido?

14. Da un ejemplo de un grafo G = (V, A) y un subgrafo suyo G´= (V´, A´), obtenido eliminando aristas de
G, verificando:

a) G no bipartido y G´bipartido.
b) G bipartido y G´no bipartido.

15. ¿Son isomorfos los grafos G y G´ dados por las matrices de adyacencia siguientes?

16. Determina cuáles de los siguientes pares de grafos son isomorfos, dando en su caso los vértices
que se corresponden por el isomorfismo:

b a

1 3 5
c f

2 4 6 d e
....................

2 4 5 d

3 6 a b c e f
..................
17. Sean G y Q3 los grafos representados por las figuras adjuntas, ¿es G isomorfo al grafo 𝑄 ?
En caso negativo, justifica la respuesta. En caso afirmativo, define el isomorfismo 𝐼: 𝐺 → 𝑄
existente.

2
DMATIC. ETSI Informáticos. UPM Matemática Discreta II
Curso 21-22

18. Si G = (V, A), el grafo de aristas de G, designado por L(G), es el grafo cuyos vértices son las
aristas de G. La adyacencia en L(G) se define por la adyacencia en G. Probar que
a) L(Cn) es isomorfo a Cn
b) L(Kn) tiene vértices y es regular de grado 2 (n  2).

c) L(K5) es el complementario del grafo de Petersen.

CONEXIÓN
19. Sea G un grafo simple de 10 vértices tal que el grado de cada vértice es al menos 6 y el número de
aristas es múltiplo de 13.
a) Demuestra que G es conexo y no es bipartido.
b) Halla el número de aristas de G.
20. Encuentra un contraejemplo para cada una de las siguientes afirmaciones:
a) Si G es un grafo conexo que sólo contiene vértices pares entonces G no contiene vértices-corte.
b) Si G es un grafo conexo con un vértice-corte, entonces G contiene un puente.
21. Sea G un grafo simple de n vértices cuyos vértices tienen todos grado mayor o igual que (n – 1)/2.
Probar que G es conexo.
22. ¿Cuál es el número máximo de componentes conexas que puede tener un grafo de 40 vértices y 435
aristas?

Indicación: encuentra primero el grafo completo con mayor orden y un número de aristas  435.