完全2部グラフ
完全2部グラフ K m , n {\displaystyle K_{m,n}} の最大独立集合の大きさは max { m , n } {\displaystyle \max \lbrace m,n\rbrace } である。
完全2部グラフ K m , n {\displaystyle K_{m,n}} の隣接行列の固有値は n m {\displaystyle {\sqrt {nm}}} 、 − n m {\displaystyle -{\sqrt {nm}}} 、0であり、重複度はそれぞれ 1、1、n+m-2 である。
完全2部グラフ K m , n {\displaystyle K_{m,n}} のラプラシアン行列の固有値は n+m、n、m、0 であり、重複度はそれぞれ 1、m-1、n-1、1 である。
完全2部グラフ K m , n {\displaystyle K_{m,n}} には m n の全域木がある。
完全2部グラフ K m , n {\displaystyle K_{m,n}} には大きさ min { m , n } {\displaystyle \min \lbrace m,n\rbrace } の最大マッチングがある。
完全2部グラフ K n , n {\displaystyle K_{n,n}} にはラテン方格に対応した n色の辺彩色が存在する。
最後の2つは、k-正則2部グラフに結婚定理を適用することで得られる系である。