Ak sa v grafe dá po hranách dostať odvšadiaľ všade, t.j. ak sú každé dva vrcholy spojené cestou, hovoríme, že graf je súvislý. Vo všeobecnosti môže graf pozostávať z niekoľkých súvislých častí, ktoré voláme komponenty súvislosti. Podobne v orientovaných grafoch, ak sa dá dostať odvšadiaľ všade v smere šípok, graf je silno súvislý.