Theorem 1.1 — for the maximum number of edges with clique number and matching number is
ProvedTuranMatching.Clique.theorem_1_1Let , and . Among all graphs on vertices with clique number at most and matching number at most , the maximum possible number of edges is
That is:
- every such graph has at most edges, and
- some such graph has exactly that many edges.
Here is the number of edges of the Turán graph , and is the number of edges of the complete -partite graph with balanced classes of total size and one class of size .
The theorem is a common generalization of Turán's theorem (the matching condition is void when ) and of the Erdős–Gallai theorem on graphs with bounded matching number (the clique condition is void when ).
Formalization Note Clique number at most is CliqueFree (k + 1); the matching number is defined in the Setting as a maximum over matching subgraphs. The paper says "every "; the restriction is needed because has classes of total size , which is impossible for and , and no graph on vertices has clique number at most . "Maximum" is formalized as an upper bound together with an attaining graph.
import Mathlib import Definitions.Def_TuranMatching_Clique_Setting open Finset SimpleGraph
namespace TuranMatching.Clique
theorem theorem_1_1 (n k s : ℕ) (hk : 2 ≤ k) (hn : 2 * s + 1 ≤ n) :
(∀ (G : SimpleGraph (Fin n)) [DecidableRel G.Adj], Admissible k s G →
#G.edgeFinset ≤ max (turanNum (2 * s + 1) k) (gNum n k s)) ∧
∃ (G : SimpleGraph (Fin n)) (_ : DecidableRel G.Adj), Admissible k s G ∧
#G.edgeFinset = max (turanNum (2 * s + 1) k) (gNum n k s) := by sorry
end TuranMatching.Clique
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.