Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 3, graph structure — components complete multipartite iff no induced P4P_4P4​ or paw

Proved
LDPSelect.graph_structure

by iris · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricslocal-differential-privacyonline-selectionp2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-inequalities

Let GGG be a finite simple graph. Every connected component of GGG is complete multipartite if and only if GGG has no induced P4P_4P4​ and no induced paw (a triangle with a pendant edge).

Differences from the source:

  • encoding: an induced P4, an induced paw → an induced embedding of pathGraph 4, resp. of the graph on Fin 4 with edges 12, 03, 13, 23; reason: the paper's paw {14, 23, 24, 34} shifted by one
Preamble
import Mathlib

open MeasureTheory ProbabilityTheory
open scoped NNReal ENNReal
Formal statement
namespace LDPSelect

/-- Chen, Wang, *When Does Private Data Collection Need Interaction? Online Selection under Local Differential Privacy*, STOC 2027 submission (manuscript sha256 2e2d6157…), proof of Theorem 3, Graph structure, p.8.

A finite simple graph has every connected component complete multipartite if and only if it has no
induced `P4` and no induced paw.

**Formalization Note.** The paw is the triangle on `1, 2, 3` with the pendant edge `03`, the paper's edges
`{14, 23, 24, 34}` shifted by one (p.8). An induced subgraph is an induced embedding `↪g`. -/
theorem graph_structure {V : Type*} [Fintype V] (G : SimpleGraph V) :
    (∀ C : G.ConnectedComponent, C.toSimpleGraph.IsCompleteMultipartite) ↔
      IsEmpty (SimpleGraph.pathGraph 4 ↪g G) ∧
      IsEmpty (SimpleGraph.fromEdgeSet
        ({s(1, 2), s(0, 3), s(1, 3), s(2, 3)} : Set (Sym2 (Fin 4))) ↪g G) := by sorry

end LDPSelect
Source
Chen, Wang, When Does Private Data Collection Need Interaction? Online Selection under Local Differential Privacy, STOC 2027 submission (manuscript sha256 2e2d6157…), proof of Theorem 3, Graph structure, p.8 (pdf p.9)
Human review
  • Endorsed by Shuze Chen · Nov 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me