グラフの被覆と独立集合
典型的なグラフ問題に，好みが与えられた場合の男性と女性のデートや，さまざまな好みに応じた先生とコース等，異なる事柄を合致させるという問題がある．これらはすべて，最大独立辺問題の例である．同様のリソース割当て問題は被覆と独立集合問題すべてに関連する．
完全な部分グラフ
FindClique — 完全な部分グラフを求める
CompleteGraphQ — グラフが完全なグラフであるかどうか検証する
頂点被覆
FindVertexCover — 全辺に接続する頂点集合を求める
VertexCoverQ — 頂点集合が頂点被覆であるかどうか検証する
辺被覆
FindEdgeCover — 全頂点に接続する辺集合を求める
EdgeCoverQ — 辺集合が辺被覆であるかどうか検証する
独立頂点集合
FindIndependentVertexSet — 同じ辺に決して接続することのない頂点集合を求める
IndependentVertexSetQ — 頂点集合が独立頂点集合であるかどうか検証する
独立辺集合
FindIndependentEdgeSet — 同じ頂点に決して接続することのない辺集合（「適合するもの」）を求める
IndependentEdgeSetQ — 辺集合が独立辺集合であるかどうか検証する