頂点連結度・辺連結度

$G$ を $n$ 頂点のグラフとする。

• $S\subseteq V(G)$ は、$G-S$ が非連結になるとき分離集合という。$k\ge0$ に対し、$n>k$ で、かつ $k$ 個未満の頂点からなるどの $S$ についても $G-S$ が連結であるとき、$G$ は $k$-連結であるという。$G$ が $k$-連結であるような最大の $k$ を頂点連結度 $\kappa(G)$ という。
• $F\subseteq E(G)$ は、$G-F$ が非連結になるとき辺カットという。$n\ge2$ で、$k$ 本未満の辺からなるどの $F$ についても $G-F$ が連結であるとき、$G$ は $k$-辺連結であるという。その最大の $k$ を辺連結度 $\lambda(G)$ という（$n=1$ のときは $\lambda=0$ とする）。
• 頂点 $s,t$ と $S\subseteq V(G)\setminus\{s,t\}$ について、$s$ と $t$ が $G-S$ の異なる連結成分に属するとき、$S$ は $s$ と $t$ を分離するという。辺集合についても同様に定める。