K-辺連結グラフ
グラフG = (V,E) が与えられたとき、|X| < k であるような全ての X ⊆ E に対して G' = (V,E \ X) が連結であるときG は k-辺連結であると言う。明らかに、Gがk-辺連結グラフならばGは (k−1)-辺連結である。