2部グラフ
グラフ$ Gの頂点集合$ V(G)を互いに素な部分集合$ V_1, V_2に分割して、$ V_1の頂点同士も$ V_2の頂点同士も隣接しないようにできる時、$ Gを2部グラフと呼び、$ V_1, V_2を部集合と呼ぶ。
さらに$ V_1の各頂点が$ V_2の全ての頂点と隣接している時、$ Gを完全2部グラフという。
$ |V_1| = m, |V_2| = nなる完全2部グラフを$ K_{m,n}あるいは$ K(m,n)と表す。
定理
グラフ$ Gに対して、$ Gが2部グラフであることと、$ Gが奇閉路を含まないこととは同値である。