完全二分图

完全二分图是一种特殊的二分图，可以把图中的顶点分成两个集合，使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连。

定义完全二分图G: = (V1 +V2,E)是一个二分图，使得对于任何两个顶点和，v1v2都是G中的一条边。且的完全二分图记为Km,n。

例子

K1,3

K2,3

K3,3

性质平面图不能含有子图K3,3；外平面图不能含有子图K3,2（这些是必要条件而不是充分条件）。 完全二部图Km,n的顶点覆盖数为min{m,n}，边覆盖数为max{m,n}。 完全二分图Km,n具有大小为max{m,n}的最大独立集合。 完全二分图Km,n具有大小为min{m,n}的最大匹配。 完全二分图Kn,n具有正则的n-边染色。 完全二分图Km,n有m n个不同的生成树。