Grafo conexo

Si un grafo no es conexo, se descompone de manera única en componentes conexas: los subgrafos conexos más grandes posibles. Dos vértices están en la misma componente exactamente cuando hay un camino entre ellos, y esa relación reparte los vértices en clases disjuntas. Un grafo es conexo cuando tiene una sola componente; el grafo con un solo vértice es conexo.

Contar aristas da una cota útil. Un grafo conexo con \(n\) vértices tiene al menos \(n-1\) aristas, porque cada arista une a lo más dos componentes. En el otro extremo, un grafo disconexo con \(n\) vértices tiene a lo más \(\binom{n-1}{2}\) aristas (un grafo completo de \(n-1\) vértices más uno aislado); por tanto, más aristas que eso obligan a que sea conexo.

Quitar una arista que forma parte de un ciclo no rompe la conexidad, porque el resto del ciclo sirve de desvío. Una arista cuya eliminación sí desconecta el grafo se llama puente. Un error común es creer que conexo significa «con todas las aristas posibles»: eso es un grafo completo, un caso muy particular. La conexidad es la propiedad que permite definir árboles, recorridos eulerianos y distancias.