Граф называется связным, если для любой пары его вершин (u, v) существует последовательность вершин u, (w1... wk), v, где k ≥ 0, такая, что любые две смежные вершины в последовательности соединены ребром.