n個點，使最大匹配為k-1的最大邊數等於

(n-1) + (n-2) + ... (n-k+1)
  由一個點連到所有邊，重複做k-1次。

(2(k-1) * (2(k-1)-1) / 2) + Max(n-2(k-1), 2(k-1))
  建一個有2(k-1)個點的完全子圖S，然後由外部一個點對S全部點連線，或由S一個點
  對外部全部點連線。

這兩種構圖方式之一(我證不出來)。

如果2k>n，那麼解就是n(n-1)/2(完全圖)。

• 我给个证明吧 (1327) jml04 2010-12-22 19:58:11