完全二分图

完全二分图，有时也称为完全双色图 (Erdős et al. 1965) 或完全二部图，是一个二分图（即将图的顶点集分解为两个不相交的集合，使得同一集合内没有两个图的顶点相邻），其中两个集合中的每对图的顶点都相邻。 如果两个集合中分别有 和 个图的顶点，则完全二分图表示为 。 上图显示了 和 。

也被称为效用图（并且是循环图 ），并且是唯一的 4-笼图。 是一个 Cayley 图。 完全二分图 是一个循环图 (Skiena 1990, p. 99)，特别是 ，其中 是向下取整函数。

的特殊情况总结在下表中。

	路径图
	路径图
	爪状图
	星图
	四圈图
	效用图

图 对于 , 2, ... 的（有向）哈密顿环的数量为 0, 2, 12, 144, 2880, 86400, 3628800, 203212800, ... (OEIS A143248)，其中对于 的第 项由 给出，其中 是阶乘。

完全二分图是优美的。

Zarankiewicz 猜想提出了 的图交叉数的闭合形式。

的独立多项式由下式给出

(1)

它具有以下递推方程

(2)

匹配多项式由下式给出

(3)

其中 是拉盖尔多项式，匹配生成多项式由下式给出

(4)

具有真哈密顿分解 当且仅当 且 为偶数时成立，并且具有准哈密顿分解 当且仅当 且 为奇数时成立 (Laskar and Auerbach 1976; Bosák 1990, p. 124)。

上面例示的完全二分图 在翁贝托·埃科的小说傅科摆 (1989, p. 473; Skiena 1990, p. 143) 中起着重要的作用。