Grafos 2-conexo
Ronald Mas,
Angel Ramirez
15 de octubre de 2021
Ronald Jesús Mas Huamán Grafos Eurelianos 15 de octubre de 2021 1 / 13
Contenido
1 Grafos 2-conexo
2 Operaciones en grafos
3 Grafos libre de triángulos
Ronald Jesús Mas Huamán Grafos Eurelianos 15 de octubre de 2021 2 / 13
2-Conectividad
Definición
Un grafo G se llama k-vértice conexo si tiene como mı́nimo k + 1 vértices
y permanece conexo después de suprimir cualquier conjunto de k − 1
vértices.
Observaciones:
Diremos que un grafo G es 2-conexo en vez de decir que un grafo G
es 2-vértice conexo.
Es decir, un grafo G se llama 2-conexo si tiene como mı́nimo 3
vértices y al suprimir cualquier vértice se tiene un grafo conexo.
Un grafo 2- conexo es también conexo.
Ejemplo: El siguiente grafo no es 2-conexo ya que el suprimir el vértice v
se genera un grafo no conexo.
Ronald Jesús Mas Huamán Grafos Eurelianos 15 de octubre de 2021 3 / 13
Operaciones en grafos
Definición
Sea G = (V , E ) un grafo. Definamos algunas operaciones en grafos:
1) Eliminación de una arista:
G − e = (V , E \ {e}),
donde e ∈ E (G ).
2) Adición de una nueva arista:
G + e = (V , E ∪ {e}),
V
donde e ∈ \ E.
2
Ronald Jesús Mas Huamán Grafos Eurelianos 15 de octubre de 2021 4 / 13
Continua las Operaciones en grafos
Definición
3) Eliminación de un vértice:
G − v = (V \ {v }, {e ∈ E : v 6∈ e}),
donde v ∈ V (G ) (al eliminar el vértice se eliminan también todas las
aristas que lo contienen).
4) Subdivisión de una arista:
G %e = (V ∪ {z}, (E \ {{x, y }}) ∪ {{x, z}, {z, y }})
donde e = {x, y } ∈ E (G ) y z 6∈ V (G ) es un nuevo vértice (se coloca
un nuevo vértice z en la arista {x, y }).
Ronald Jesús Mas Huamán Grafos Eurelianos 15 de octubre de 2021 5 / 13
Ejemplos:
Dado un grafo G = (V , E ) veamos algunas operaciones:
Ronald Jesús Mas Huamán Grafos Eurelianos 15 de octubre de 2021 6 / 13
Teorema
Un grafo G es 2-conexo si y sólo si para cualquier par de vértices de G
existe un ciclo en G conteniendo estos dos vértices.
Prueba:
⇐) Como cualquier par de vértices v , v 0 ∈ V (G ) pertenecen a un ciclo en
común entonces existen dos caminos que no contienen vértices comunes
excepto los vértices finales y ası́ v y v 0 no caen en distintos componentes
al eliminar un solo vértice.
⇒) Ejercicio.
Ronald Jesús Mas Huamán Grafos Eurelianos 15 de octubre de 2021 7 / 13
Proposición
Un grafo G es 2-conexo si y sólo si cualquier subdivisión de G es 2-conexo.
Prueba:
Es suficiente probar que, para todo e ∈ E (G ), G es 2-conexo si y sólo si
G %e es 2-conexo. Veamos sólo la vuelta, si v ∈ V (G ) entonces G − v es
conexo si y sólo si (G %e) − v es conexo, por tanto si G % es 2-conexo
entonces G también es 2-conexo.
Ronald Jesús Mas Huamán Grafos Eurelianos 15 de octubre de 2021 8 / 13
Caracterización de grafos 2-conexo
Teorema
Un grafo G es 2-conexo si y sólo si este puede ser creado de un triángulo
(K3 ) por una secuencia de subdivisiones y adición de aristas.
Ejemplo: Veamos como generar el grafo G .
Ronald Jesús Mas Huamán Grafos Eurelianos 15 de octubre de 2021 9 / 13
Grafos libres de triángulos
Sea G un grafo simple con | V (G ) |= n, si | E (G ) |= k entonces
n
0≤k ≤ .
2
Es bien sabido que todo grafo simple máximal con n vértices es isomorfo a
Kn , analicemos la siguiente interrogante:
¿ Cuántas aristas como máximo puede tener un grafo simple G con n
vértices libre de triángulos?
Ronald Jesús Mas Huamán Grafos Eurelianos 15 de octubre de 2021 10 / 13
Casos particulares
Sea T (n) el número máximo de aristas que puede tener un grafo G libre
de triángulos con n vértices. Luego se tiene que:
T (1) = 0.
T (2) = 1.
T (3) = 2.
T (4) = 4, (G ' C4 ).
T (5) = 6. En efecto como muestra el dibujo:
Ronald Jesús Mas Huamán Grafos Eurelianos 15 de octubre de 2021 11 / 13
Teorema
n2
Para todo número natural n se tiene que T (n) = J K.
4
Teorema
Para todo número natural n cada grafo libre de triángulo con la máxima
cantidad de aristas es isomorfo a el grafo Ka,b con a = J n2 K y b = n − J n2 K
Ejemplo: Para un grafo G = (V , E ) libre de triángulos con
| V (G ) |= n = 5 se tiene que a = 2 y b = 3, por tanto:
Ronald Jesús Mas Huamán Grafos Eurelianos 15 de octubre de 2021 12 / 13
Teorema
Sea G = (V , E ) un grafo libre de triángulos. Entonces existe una partición
de V en dos subconjuntos X y Y tal que para todo vértice x ∈ V se tiene
que degG (x) ≤ degK|X |,|Y | (x).
Este teorema permite probar de manera rápida que
n2
T (n) = J
K.
4
En efecto, si | X |= a y | Y |= b se tiene por el teorema anterior que:
| E (G ) |≤| E (Ka,b ) |
con a + b = n, luego como deseamos maximizar a.b se tiene:
a.b = a(n − a) = −a2 + an, es decir el máximo valor del producto e
obtiene cuando a = n2 . Luego
n2
| E (G ) |≤ .
4
n2
Por tanto T (n) = J K.
4
Ronald Jesús Mas Huamán Grafos Eurelianos 15 de octubre de 2021 13 / 13
