设f(n,k)=
n(n-1)/2           n<=2k+1
k(2k+1)            2k+1<=n<=2k+1+(k+1)/2
k(n-(k+1)/2)       2k+1+(k+1)/2<=n
证n个点，最大匹配数为k图的最大边数为f(n,k)

显然上述值可以取到，两种情况最大的就行：
min(n,2k+1)个点的完全图
或任取k个点，取从这k个点出发的所有边

n=1,2,3易证
k=0易证
n>=4,k>0数学归纳
设对顶点数为1,2,3,...,n-1的情况已成立，
对一幅n个点，最个匹配为数为k的图，设它的边数为fnk

取度数最大的点a
若d(a)>=2k+1,则
除了点a剩下的n-1个的点的图的匹配数最多为k-1（反证法，略)
fnk=f(n-1,k-1)+d(a)<=f(n-1,k-1)+n-1
分四种情况:
n<=2k fnk<=(n-1)(n-2)/2+(n-1)=f(n,k)
2k+1<=n<=2k+k/2 fnk<=(k-1)*(2k-1)+n-1<=(k-1)*(2k-1)+2k+k/2-1=k*(2k-1/2)<=k(2k+1)=f(n,k)
2k+k/2<=n<=2k+k/2+3/2 fnk<=(k-1)*(n-1-(k)/2)+n-1=nk-k(k+1)/2=k(n-(k+1)/2)-1<=k(2k+1)<=f(n,k)
n>=2k+k/2+3/2 fnk<=(k-1)*(n-1-(k)/2)+n-1=nk-k(k+1)/2<=f(n,k)
所以fnk<=f(n,k)

1<d(a)<=2k
取与a相邻的点b,则
除了点a，b剩下的n-2个的点的图的匹配数最多为k-1(反证法,略）
fnk=f(n-2,k-1)+d(a)+d(b)-1<=f(n-2,k-1)+2n-3
fnk=f(n-2,k-1)+d(a)+d(b)-1<=f(n-2,k-1)+4k-1
所以:
n<=2k+1 fnk<=(n-2)(n-3)/2+2n-3=n*n/2-n/2=f(n,k)
2k+2<=n<=2k+1+k/2 fnk<=(k-1)*(2k-1)+4k-1=2k*k+k=f(n,k)

n>=2k+1+(k+1)/2:
取度数最小的点c,易证d(c)<=k(反证，不断取边，观察剩余图中最小度数）
fnk<=f(n-2,k-1)+d(a)+d(c)<=f(n-2,k-1)+3k
若除了点a，c剩下的n-2个的点的图的匹配数最多为k-1
fnk<=(k-1)(n-2-k/2)+3k=kn-k*k/2-k/2+k-n+3k－2k+2=f(n,k)+2k+2-n<=f(n,k)
若除了点a，c剩下的n-2个的点的图的最大匹配数为k
则易证d(a)+d(c)<=2k(证略，很容易)
fnk<=k(n-2-(k+1)/2)+2k=f(n,k)
所以fnk<=f(n,k)

d(a)=0 fnk=0<=f(n,k)

所以可以证明fnk<=f(n,k）,又f(n,k)能取到，所以...