/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Erdős Problem 1017

References:

    erdosproblems.com/1017

    [EGP66] Erdős, Paul and Goodman, A. W. and Pósa, Lajos, The representation of a graph by set intersections. Canadian J. Math. (1966), 106–112.

    [Er71] Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97–109.

    [GyKe17] Győri, Ervin and Keszegh, Balázs, On the number of edge-disjoint triangles in $K_4$-free graphs. Combinatorica (2017), 1113–1124.

    [Lo68] Lovász, L., On covering of graphs. Theory of Graphs (Proc. Colloq., Tihany, 1966) (1968), 231–236.

@[expose] public sectionnamespace Erdos1017open SimpleGraph

The least uniform bound on the number of cliques in an edge partition of an $n$-vertex, $k$-edge graph. For infeasible parameters the value is zero.

noncomputable def f (n k : ℕ) : ℕ := sInf {m : ℕ | ∀ G : SimpleGraph (Fin n), G.edgeSet.ncard = k → ∃ P : Finset (Finset (Fin n)), G.IsCliqueEdgePartition P ∧ P.card ≤ m}

Partitioning into individual edges gives the bound $f(n,k) \le k$.

@[category API, AMS 5] theorem f_le (n k : ℕ) : f n k ≤ k := n:ℕk:ℕ⊢ f n k ≤ k classical n:ℕk:ℕ⊢ k ∈ {m | ∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m} n:ℕk:ℕG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = k⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ k n:ℕk:ℕG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = kP:Finset (Finset (Fin n))hP:G.IsCliqueEdgePartition Phcard:P.card = G.edgeFinset.card⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ k n:ℕk:ℕG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = kP:Finset (Finset (Fin n))hP:G.IsCliqueEdgePartition Phcard:P.card = G.edgeFinset.card⊢ P.card ≤ k All goals completed! 🐙

The infimum defining $f$ is an attained uniform bound.

n:ℕk:ℕG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = khne:{m | ∀ (H : SimpleGraph (Fin n)), H.edgeSet.ncard = k → ∃ P, H.IsCliqueEdgePartition P ∧ P.card ≤ m}.Nonempty⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ f n k All goals completed! 🐙

A graph with no edges needs no cliques in its edge partition.

@[category test, AMS 5] theorem f_zero (n : ℕ) : f n 0 = 0 := Nat.eq_zero_of_le_zero (f_le n 0)

A proposed uniform bound is valid exactly when it is at least $f(n,k)$.

@[category API, AMS 5] theorem f_le_iff (n k m : ℕ) : f n k ≤ m ↔ ∀ G : SimpleGraph (Fin n), G.edgeSet.ncard = k → ∃ P : Finset (Finset (Fin n)), G.IsCliqueEdgePartition P ∧ P.card ≤ m := n:ℕk:ℕm:ℕ⊢ f n k ≤ m ↔ ∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m n:ℕk:ℕm:ℕ⊢ f n k ≤ m → ∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ mn:ℕk:ℕm:ℕ⊢ (∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m) → f n k ≤ m n:ℕk:ℕm:ℕ⊢ f n k ≤ m → ∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m n:ℕk:ℕm:ℕh:f n k ≤ mG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = k⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m n:ℕk:ℕm:ℕh:f n k ≤ mG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = kP:Finset (Finset (Fin n))hP:G.IsCliqueEdgePartition Phcard:P.card ≤ f n k⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m All goals completed! 🐙 n:ℕk:ℕm:ℕ⊢ (∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m) → f n k ≤ m n:ℕk:ℕm:ℕh:∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m⊢ f n k ≤ m n:ℕk:ℕm:ℕh:∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m⊢ m ∈ {m | ∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m} All goals completed! 🐙

Impossible edge counts give the vacuous value zero and are excluded from the question.

n:ℕk:ℕhk:n.choose 2 < kG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = khcard:G.edgeFinset.card ≤ (Fintype.card (Fin n)).choose 2this:G.edgeFinset.card = k⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ 0 n:ℕk:ℕhk:n.choose 2 < kG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = kthis:G.edgeFinset.card = khcard:k ≤ n.choose 2⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ 0 All goals completed! 🐙def erdos_1017.lower_bound.answer (n k : ℕ) : ℕ := n:ℕk:ℕ⊢ ℕ All goals completed! 🐙

Let $f(n,k)$ be such that every graph on $n$ vertices and $k$ edges can be partitioned into at most $f(n,k)$ edge-disjoint complete graphs. Estimate $f(n,k)$ for $k>n^2/4$.

@[category research open, question value, AMS 5] theorem erdos_1017.lower_bound : ∀ n k : ℕ, k ≤ n.choose 2 → n * n < 4 * k → erdos_1017.lower_bound.answer n k ≤ f n k := ⊢ ∀ (n k : ℕ), k ≤ n.choose 2 → n * n < 4 * k → lower_bound.answer n k ≤ f n k All goals completed! 🐙def erdos_1017.upper_bound.answer (n k : ℕ) : ℕ := n:ℕk:ℕ⊢ ℕ All goals completed! 🐙

Estimate an upper bound for $f(n,k)$, the worst-case number of complete subgraphs needed to partition the edges of an $n$-vertex, $k$-edge graph, for $n^2/4 < k \le \binom{n}{2}$.

@[category research open, question value, AMS 5] theorem erdos_1017.upper_bound : ∀ n k : ℕ, k ≤ n.choose 2 → n * n < 4 * k → f n k ≤ erdos_1017.upper_bound.answer n k := ⊢ ∀ (n k : ℕ), k ≤ n.choose 2 → n * n < 4 * k → f n k ≤ upper_bound.answer n k All goals completed! 🐙end Erdos1017