完全2部グラフ
完全2部グラフ G := ( V 1 + V 2 , E ) {\displaystyle G:=(V_{1}+V_{2},E)} は2部グラフであり、任意の2つの頂点 v 1 ∈ V 1 {\displaystyle v_{1}\in V_{1}} と v 2 ∈ V 2 {\displaystyle v_{2}\in V_{2}} について G {\displaystyle G} 内の辺 v 1 v 2 {\displaystyle v_{1}v_{2}} が存在する。完全2部グラフのパーティションの大きさが | V 1 | = m {\displaystyle \left|V_{1}\right|=m} と | V 2 | = n {\displaystyle \left|V_{2}\right|=n} であるとき、これを K m , n {\displaystyle K_{m,n}} と表記する。