Claim 4.2, p. 12 — the blow-up of a girth-5 graph by cliques of size c/2 is c-closed
ProvedCClosedGraphs.LowerBound.claim_4_2Let be a finite graph of girth at least , let be an integer, and let be the blow-up of in which each vertex becomes a clique of vertices, the bipartite graph between and is minus a perfect matching when , and there are no edges between and otherwise. Then, with ,
This is the first half of the lower-bound construction: the graph built from satisfies the triadic-closure condition with parameter .
Formalization Note The paper's is even and ; here and the conclusion is stated for . The paper builds from one extremal girth- graph, but its proof uses only that has girth at least , so the claim is stated for every such (girth via Mathlib's egirth, for forests). The perfect matching is fixed as , one admissible choice in the paper's construction. For the blow-up is edgeless and the claim is still true.
import Mathlib import Definitions.Def_CClosedGraphs_LowerBound_Setting
namespace CClosedGraphs.LowerBound
theorem claim_4_2 {V : Type*} [Fintype V] [DecidableEq V] (H : SimpleGraph V) (h : ℕ)
(hh : 1 ≤ h) (hH : 5 ≤ H.egirth) : CClosedGraphs.Peeling.IsCClosed (2 * h) (blowUp H h) := by sorry
end CClosedGraphs.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.