§1.4, p. 5 — a graph of girth at least 5 is 2-closed, and each of its edges is a maximal clique
ProvedCClosedGraphs.LowerBound.two_closed_of_girth_fivec-closed-graphgirthmaximal-cliquep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite graph of girth at least , i.e. without triangles and without -cycles. Then
- is -closed (vacuously: no two distinct vertices have two common neighbours), and
- every edge of is a maximal clique, so
The paper makes this observation for the point–line incidence graph of a finite projective plane, which has edges, to show that -closed graphs can have maximal cliques. Combined with a graph of girth at least and many edges, it gives the lower bound for .
Formalization Note The page states the observation for the projective-plane incidence graph (girth ). The two properties it uses are "no -cycle" (-closed) and "no triangle" (edges are maximal cliques), and girth at least is exactly both, so the statement is made for every graph of girth at least (Mathlib's egirth, which is for forests).
Preamble
import Mathlib import Definitions.Def_CClosedGraphs_LowerBound_Setting
Formal statement
namespace CClosedGraphs.LowerBound
theorem two_closed_of_girth_five {V : Type*} [Fintype V] [DecidableEq V] (H : SimpleGraph V)
(hH : 5 ≤ H.egirth) : CClosedGraphs.Peeling.IsCClosed 2 H ∧ H.edgeSet.ncard ≤ CClosedGraphs.Peeling.numMaxCliques H := by sorry
end CClosedGraphs.LowerBound
Source
Fox, Roughgarden, Seshadhri, Wei and Wein, Finding cliques in social networks: a new distribution-free model, arXiv:1804.07431v1, p. 5, §1.4 (projective-plane construction of Eschen, Hoàng, Spinrad and Sritharan [22])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.