2部グラフ

2部グラフ（2ぶグラフ）は、グラフGのうち、V(G)を二つの頂点集合に分割して各集合内の頂点同士に枝が無いようにできるグラフのこと。n個の頂点集合に分割可能なグラフは、n部グラフという。

完全2部グラフは、二つの頂点集合V₁, V₂に分割したとき、V₁同士・V₂同士の頂点間には辺が存在しないが、V₁とV₂間の任意の2点間に辺が存在するグラフのことである。m頂点の頂点集合とn頂点の頂点集合でできているとき、K_{m, n}とかく。

隣り合った頂点同士を異なる色で塗ることを（頂点）彩色という。よって、n部グラフはn点彩色可能なグラフである。同様に、隣り合った辺同士を異なる色で塗ることを辺彩色という。

辺集合Mがマッチングであるとは、Mに属するどの2辺も隣接していないと言うことである。グラフGの最大マッチングとは、GのマッチングMのうち、辺の数が最大のものである。

グラフG=(V,E)に対して、全ての頂点を含むマッチングのことを完全マッチングという

性質

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