2部グラフ
2部グラフの最大マッチングは多項式時間で求められる。最大フロー問題を参照。
木は2部グラフである。
閉路グラフは頂点が偶数個のときに限り2部グラフである。
Königの定理:2部グラフにおいて、最大マッチングの辺数は最小点被覆の点数と等しい。