グラフ$G$のどの2頂点に対しても、それらを結ぶ散歩道が存在するとき、 $G$は連結である(connected)という。
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)と呼ばれる。