グラフ$G$のどの2頂点に対しても、それらを結ぶ散歩道が存在するとき、 $G$は連結である(connected)という。 連結でないグラフは非連結である(disconnected)という。
2つのグラフ$G_1=(V_1,E_1)$と$G_2=(V_2,E_2)$に対して、 $(V_1\coprod V_2\,,\ E_1\coprod E_2)$はグラフになる。 これを$G_1$と$G_2$の和と呼び、$G_1\union G_2$と書く。 グラフが連結であることと、グラフが2個のグラフの和として 表わされないことは同値である。
任意のグラフ$G$は有限個の連結なグラフの和として表わせ、 それら連結なグラフの各々は、$G$の成分(component)と呼ばれる。