K-辺連結グラフ
関連する問題: グラフ G の最小 k-辺連結部分グラフを見つける(すなわち、スケルトンが k-辺連結となるような可能な限り少ない辺をグラフから選択する)問題は、 k ≥ 2 {\displaystyle k\geq 2} に対してNP困難である。