完全二分图

完全二分图${\displaystyle G:=(V_{1}+V_{2},E)}$是一个二分图，使得对于任何两个顶点${\displaystyle v_{1}\in V_{1}}$和${\displaystyle v_{2}\in V_{2}}$，${\displaystyle v_{1}v_{2}}$都是${\displaystyle G}$中的一条边。${\displaystyle \left|V_{1}\right|=m}$且${\displaystyle \left|V_{2}\right|=n}$的完全二分图记为${\displaystyle K_{m,n}}$。

• 
  K_1,3
• 
  K_2,3
• 
  K_3,3

• 平面图不能含有子图${\displaystyle K_{3,3}}$；外平面图不能含有子图${\displaystyle K_{3,2}}$（这些是必要条件而不是充分条件）。
• 完全二分图${\displaystyle K_{m,n}}$的顶点覆盖数为${\displaystyle \min \lbrace m,n\rbrace }$，边覆盖数为${\displaystyle \max \lbrace m,n\rbrace }$。
• 完全二分图${\displaystyle K_{m,n}}$具有大小为${\displaystyle \max \lbrace m,n\rbrace }$的最大独立集。
• 完全二分图${\displaystyle K_{m,n}}$具有大小为${\displaystyle \min \lbrace m,n\rbrace }$的最大匹配。
• 完全二分图${\displaystyle K_{n,n}}$具有正则的n-边染色。
• 完全二分图${\displaystyle K_{m,n}}$有m^n-1 n^m-1个不同的生成树。

• 圈图
• 道路 (图论)
• 完全图
• 零图
• 二分图
• 三間小屋問題