数学、とくにグラフ理論における2部グラフ（にぶぐらふ、）は、頂点集合を二つの部分集合に分割して各集合内の頂点同士の間には辺が無いようにできるグラフのことである。このような頂点の集合を独立集合といい、より一般にn個の独立頂点集合に分割可能なグラフのことをn部グラフ () という。完全2部グラフは、二つの頂点集合V, Vに分割したとき、V同士・V同士の頂点間には辺が存在しないが、VとV間の任意の2点間に辺が存在するグラフのことである。m頂点の頂点集合とn頂点の頂点集合に分割されるような完全2部グラフのことをKとかく。隣り合った頂点同士を異なる色で塗ることを（頂点）彩色という。よって、n部グラフはn点彩色可能なグラフである。同様に、隣り合った辺同士を異なる色で塗ることを辺彩色という。二部グラフの辺集合Mがマッチングであるとは、Mに属するどの2辺も隣接していないと言うことである。グラフGの最大マッチングとは、GのマッチングMのうち、辺の数が最大のものである。また、全ての頂点を含むマッチングのことを完全マッチングという。

出典:wikipedia