Hemos visto ejemplos de grafos conectados y no conectados. Mientras que «no conectado» es prácticamente un callejón sin salida, hay mucho que decir sobre «cómo de conectado» está un grafo conectado.El enfoque más sencillo es ver lo difícil que es desconectar un grafo eliminando vértices o aristas. Suponemos que todos los grafos son simples.
Si es posible desconectar un grafo eliminando un solo vértice, llamado punto de corte, decimos que el grafo tiene conectividad1. Si esto no es posible, pero es posible desconectar el grafoeliminando dos vértices, el grafo tiene conectividad 2.
Hacemos lo mismo con las aristas:
Teorema 5.7.3 $\kappa(G)\le\lambda(G)$.
Los grafos que tienen 2 conexiones son particularmente importantes, y el siguiente teorema sencillo es útil.
Hay otras buenas caracterizaciones de los grafos de 2 conexiones.
El siguiente corolario es un replanteamiento fácil de este teorema.
Esta versión del teorema sugiere una generalización:
Primero probamos la versión original de Menger, una versión «local».
Teorema 5.7.9 Si $v$ y $w$ son vértices no adyacentes en $G$, $\kappa_G(v,w)=p_G(v,w)$.
$$\bullet\quad\bullet$$
Volvemos brevemente a la 2-conectividad.El siguiente teorema puede utilizarse a veces para proporcionar el paso de inducciónen una prueba de inducción.
Un grafo que no es conectado consta de componentes conectados. En un teorema que recuerda a éste, vemos que los grafos conectados que no son2-conectados se construyen a partir de subgrafos 2-conectados y puentes.
Definición 5.7.11 Un bloque en un grafo $G$ es un subgrafo maximalinducido en al menos dos vértices sin punto de corte.
Como es habitual, maximal aquí significa que el subgrafo inducido $B$ no puede hacerse más grande añadiendo vértices o aristas (conservando la propiedad deseada, en este caso, sin puntos de corte).Un bloque es un subgrafo inducido de 2 conexiones o una sola arista junto con sus puntos finales. Los bloques son útiles en gran parte debido a este teorema:
Teorema 5.7.12 Los bloques de $G$ dividen las aristas.
Si $G$ tiene un solo bloque, es $K_2$ o es de 2 conexiones, y cualquier grafo de 2 conexiones tiene un solo bloque.
Teorema 5.7.13 Si $G$ es conexo pero no es de 2 conexiones, entonces cada vértice que está en dos bloques es un punto de corte de $G$.
Ejercicios 5.7
Ex 5.7.1Supongamos que un grafo simple $G$ sobre $n\ge 2$ vértices tiene al menos$\ds {(n-1)(n-2)\ sobre2}+1$ aristas. Demuestre que $G$ es conexo.
Ex 5.7.3Suponga que $G$ es simple con la secuencia de grados$d_1\le d_2\le d_n$, y para $k\le n-d_n-1$, $d_k\ge k$. Demostrar que$G$ es conexo.
Ex 5.7.4Recordemos que un grafo es $k$-regular si todos los vértices tienen grado $k$. Cuál es el menor número entero $k$ que hace que esto sea cierto:
Si $G$ es simple, tiene $n$ vértices, $m\ge k$, y $G$ es $m$-regular, entonces $G$ es conexo.
(Por supuesto $k$ depende de $n$.)
Ex 5.7.6Encuentra un grafo simple con $$\kappa(G)
Nota que un punto de corte está contenido en al menos dos bloques, por lo que todos los vértices dependientes del grafo bloque-punto de corte son bloques. Estos bloques se llaman bloques finales.
Ex 5.7.10Dibuja el grafo bloque-punto de corte del grafo de abajo.