完全二分圖

完全二分圖，有時也稱為完全雙色圖 (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) 中起著重要的作用。