Um grafo $G$ é dito conexo se para quaisquer vértices $v,u \in G$ distintos existir um caminho entre eles. Caso contrário, $G$ é dito desconexo.