定义

例子

性质

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

定义

完全二分图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-1)) * (n^(m-1))个不同的生成树。