Grafo conexo

[1]​ Para el caso de los grafos dirigidos, si no se considera el sentido de las aristas, se habla de componente débilmente conexo, mientras que sí se considera el sentido, se habla de componente fuertemente conexo.

Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no tiene vértices de corte, esto es, vértices tales que al quitarlos el grafo resultante se vuelve disconexo.

En ciencias de la computación, es posible determinar si un grafo es conexo usando un algoritmo de búsqueda en anchura (BFS) o búsqueda en profundidad (DFS).

En términos matemáticos, la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de estos en componentes (fuertemente) conexas, es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados.

Esta propiedad es importante para muchas demostraciones en teoría de grafos.