《Discrete Applied Mathematics》：Maximum size of a graph with given matching number and covering number
編輯推薦：
本文綜述了對于給定頂點數n、匹配數k和覆蓋數t（滿足n ≥ 2k+1 且 k ≤ t ≤ 2k）的圖，其可能達到的最大邊數（規模）進行了精確的確定，并給出了達到該最大規模的極值圖的完整刻畫。此結果不僅推廣并驗證了圖論中的Erd?s匹配猜想在特定參數下的情形（Corollary 1.4），也為理解圖的匹配數（ν）與覆蓋數（τ）這兩個核心極值參數之間的約束關系提供了重要的理論工具。文中應用了經典的Tutte-Berge公式等工具，所得結論在圖論和組合極值理論領域具有基礎性意義。
結果亮點
定理1.2
設n、k和t為三個整數，滿足n ≥ 2k+1 且 k ≤ t ≤ 2k。令G為一個頂點數為n、匹配數ν(G) = k且覆蓋數τ(G) = t的圖。那么，該圖的最大邊數e(G)滿足以下不等式：
e(G) ≤ max{ C(t, 2) + t(2k + 1 - t), C(t+1, 2) + (2k - t)(n - t - 1) }。
（其中C(x, 2)表示從x個元素中選取2個的組合數）。
而且，等式成立當且僅當滿足以下條件之一：
(i) 當 n < 2t + 1 時， G = (Kt∨ K?2k+1-t) ∪ K?n-2k-1;
(ii) 當 n > 2t + 1 時， G = K2k-t∨ (K2t-2k+1∪ K?n-t-1);
(iii) 當 n = 2t + 1 時， G是(i)或(ii)中描述的圖。
需要注意的是，對于任意圖G，如果其匹配數ν(G) = k，那么其覆蓋數必然滿足k ≤ τ(G) ≤ 2k。因此，定理1.2的結論是完備的。
為了表達簡潔，我們用[n]來表示集合{1,2,...,n}，對于兩個滿足a < b的整數a和b，用[a,b]表示集合{a, a+1, ..., b}。在整篇文章中，[n]將作為具有n個頂點的超圖的頂點集。
在文獻[9]中，Frankl和Kupavskii提出了以下猜想。
猜想1.3[9]
令H是一個頂點數為n的r-一致超圖（r-graph）。如果ν(H) = k 且 τ(H) > k，那么其邊數e(H)不超過一個由特定超圖族定義的邊數的最大值（具體定義詳見原文）。
最近，Guo等人在[11]中驗證了當k=3且n足夠大時猜想1.3成立。據我們所知，該猜想在一般情形下仍未解決。
應用定理1.2，通過簡單計算我們首先得到以下結果，這證實了猜想1.3在r=2（即圖）這一特殊情形下的正確性。
推論1.4
設n和k為兩個整數，滿足n ≥ 2k + 1。令G是一個頂點數為n、匹配數ν(G) = k且覆蓋數τ(G) > k的圖。那么其最大邊數為：
e(G) ≤ max{ C(2k+1, 2), C(k+2, 2) + (k - 1)(n - k - 2) }。
等式成立當且僅當滿足以下條件之一：
(i) 當 n < (5/2)k + 3 時， G = K2k+1∪ K?n-2k-1;
(ii) 當 n > (5/2)k + 3 時， G = Kk-1∨ (K3∪ K?n-k-2);
(iii) 當 n = (5/2)k + 3 時， G是(i)或(ii)中描述的圖。
類似地，我們還得到了以下結果。
推論1.5
設n和k為兩個整數，滿足n ≥ 2k + 1。令G是一個頂點數為n、匹配數ν(G) = k且覆蓋數τ(G) ≤ t的圖。那么其最大邊數為：
e(G) ≤ max{ C(t, 2) + t(2k + 1 - t), C(k, 2) + k(n - k) }。
等式成立當且僅當滿足以下條件之一：
(i) 當 C(t, 2) + t(2k + 1 - t) > C(k, 2) + k(n - k) 時， G = (Kt∨ K?2k+1-t) ∪ K?n-2k-1;
(ii) 當 C(t, 2) + t(2k + 1 - t) < C(k, 2) + k(n - k) 時， G = Kk∨ K?n-k;
(iii) 當 C(t, 2) + t(2k + 1 - t) = C(k, 2) + k(n - k) 時， G是(i)或(ii)中描述的圖。
定理1.2將在接下來的章節中得到證明。
定理1.2的證明
我們將以Tutte–Berge公式這個已知結論開始我們的證明。
定理2.1[2]
令G是一個頂點數為n的圖。那么其匹配數ν(G)滿足：
ν(G) = (1/2) * ( n - maxS?V(G){ o(G-S) - |S| } )。
其中o(G-S)表示從圖G中移除頂點集S后，所剩子圖中奇連通分量的數量。
我們現在來證明定理1.2。
定理1.2的證明
令G是一個頂點數為n、匹配數ν(G)=k、覆蓋數τ(G)=t且具有最大可能邊數的圖。因為n ≥ 2k+1，根據定理2.1，存在一個頂點子集S ? V(G)，使得o(G-S) - |S| = n - 2ν(G)。令C是圖G的一個覆蓋集，滿足|C| = τ(G)。我們通過以下斷言來完成證明。
斷言1
（證明在后續未提供的正文中繼續）
