連結成分とは、無向グラフの最大連結部分グラフのことである。 各頂点は各辺と同様にちょうど1つの連結成分に属する。 グラフは正確に1つの連結成分を持つ場合にのみ連結される．
強成分は有向グラフの最大強連結部分グラフである。
連結グラフGの頂点切断または分離集合は、その除去によりGが不連結になる頂点の集合である。 頂点連結度κ(G)(Gは完全グラフでない)は最小頂点切断の大きさである。 より正確には，グラフG（完全グラフかどうかは問わない）は，少なくともk+1個の頂点を含み，その除去によってグラフが切断されるk – 1個の頂点の集合を含まないとき，k-頂点連結であるといい，κ（G）はグラフがk-連結である最大のkと定義される． 特に、n個の頂点を持つ完全グラフ（Knとする）は、頂点の切断を全く持たないが、κ（Kn）＝n – 1となる。
2-連結性はバイコネクティビティ、3-連結性はトリコネクティビティとも呼ばれる。 接続されているが2-接続されていないグラフGを分離可能と呼ぶこともある。
同様の概念を辺にも定義できる。 ある特定の辺を切るとグラフが切断されるような単純な場合、その辺はブリッジと呼ばれる。 より一般的には、Gのエッジカットは、その削除によってグラフが切断されるエッジの集合です。 縁結合度 λ(G) は最小の縁切断の大きさであり、2頂点 u, v の局所縁結合度 λ(u, v) は u を v から切り離す最小の縁切断の大きさである。 8022>
グラフの接続性がその最小次数に等しいとき，グラフは最大接続と呼ばれる．
Super- and hyper-connectivityEdit
すべての最小頂点切断が頂点を分離する場合，グラフは super-connected または super-κ-connected と呼ばれる． 各最小頂点切断を削除するとちょうど2つの成分ができ、そのうちの1つが孤立頂点である場合、グラフは超連結または超-κであるという。 より正確には，G連結グラフは，すべての最小頂点切断が1つの（最小次数の）頂点に隣接する頂点からなるとき，超連結または超-κ連結という．
GのカットセットXは，Xが任意の頂点u ∉ Xの近傍N(u)を含まないとき，非自明カットセットと呼ばれる． Gの超連結度κ1とは：
κ1(G) = min{X| : X is a non-trivial cutset}である．
non-trivial edge-cut と edge-superconnectivity λ1(G)は同様に定義される。
