完全二分图（complete bipartite graph），可以把节点集合分割为两个互补的非空子集，一个子集中的任意顶点与另一个子集中的每一个顶点有且仅有一条边相连。

完全二分图是一个具有二划分的简单二分图，即把图的结点分成两个集合，且两个集合互不相交。

正文

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

定义

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

例子

性质

平面图不能含有子图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））个不同的生成树。

参考资料