完全二分圖

完全二分圖是一種特殊的二分圖，可以把圖中的頂點分成兩個集合，使得第一個集合中的所有頂點都與第二個集合中的所有頂點相連。

定義

完全二分圖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))個不同的生成樹。