ERDŐS/DAILY ▸

← back to the ledger

ERDőS #1017 · PARTIAL

Erdős problem #1017 — verified partial results (wave w029)

Access date: 2026-07-29 UTC.

0. Mandatory live-page gate

I fetched both the live problem page, its LaTeX view, and the discussion thread through the Bright Data browser path before doing any mathematics.

The exact current statement is:

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\).

The gate was clear:

The page was last edited 28 December 2025.

The page-listed results were also read in full:

  1. Erdős–Goodman–Pósa give the universal

\(\lfloor n^2/4\rfloor\) bound, using only edges and triangles.

  1. Lovász gives the displayed sharper covering bound when overlap is

permitted; the page explicitly warns that it is not edge-disjoint.

  1. Győri–Keszegh solve the \(K_4\)-free case by finding \(m\)

edge-disjoint triangles in every \(K_4\)-free graph with \(\lfloor n^2/4\rfloor+m\) edges.

  1. The page points to problems #184, #583, and #81 for related

decompositions.

All three comments were read. Alfaiz notes that the Lovász work arose from the 1966 Tihany meeting and was published in the 1968 proceedings; StijnC points to the chordal-graph work and to Blumenthal–Lidický–Pehova–Pfender– Pikhurko–Volec on weighted \(K_2/K_3\) decompositions; msawhney points to the Győri–Keszegh \(K_4\)-free theorem. The thread says the site was updated in response to each comment and warns that comments themselves are not verified.

Thus this run was permitted to proceed.

1. Claim labels and notation

The requested labels are used as follows.

source are stated explicitly.

not as a conclusion.

program, but not promoted to a uniform theorem.

Write

\[ q=t_2(n)=\left\lfloor\frac{n^2}{4}\right\rfloor,\qquad e=q+m\quad(m>0), \]

and make the least-bound interpretation of the page's function explicit:

\[ F(n,e)=\max\{\operatorname{cp}(G): |V(G)|=n,\ |E(G)|=e\}, \]

where \(\operatorname{cp}(G)\) is the minimum number of cliques in an edge partition of \(G\). Thus \(F\) is the natural extremal choice of the page's \(f\).

Let \(\nu_3(G)\) be the maximum number of pairwise edge-disjoint triangles in \(G\).

2. Primary-source literature check

The literature search found and checked the following primary sources.

Some unsolved problems in graph theory and combinatorial analysis, pp. 97–109. On printed p. 102 it states the edge-disjoint clique question and says that no satisfactory nontrivial sharpening was then known.

Erdős–Goodman–Pósa, The Representation of a Graph by Set Intersections, Canadian J. Math. 18 (1966), 106–112.

states exactly that every \(K_4\)-free graph with \(q+m\) edges contains \(m\) edge-disjoint triangles.

published in CPC 30 (2021), defines the \(K_2/K_3\) cost used below and determines its large-\(n\) extremal value. In particular, for sufficiently large \(n\), every graph has such a decomposition of cost at most \(n^2/2+1\).

Balogh–Wigal, arXiv:2502.16683, published as Combinatorica 45:56 (2025). It proves the asymptotic Győri clique-packing conjecture and accurately records two older small-excess results used below.

The Balogh–Wigal paper states, with \(\phi_3(n,m)=\min_G\nu_3(G)\) over \(n\)-vertex graphs with \(q+m\) edges:

\[ \phi_3(n,m)=m \]

when \(m\le 2n-10\) for odd \(n\), or \(m\le \tfrac32n-5\) for even \(n\); it attributes this to Győri, with a minor correction in a later paper. It also records

\[ \nu_3(G)\ge m-O(m^2/n^2)\qquad(m=o(n^2)), \]

and proves uniformly over the full density range

\[ \nu_3(G)\ge (2/3-o(1))m. \]

These statements occur respectively in the concluding remarks, Theorem 1.6, and the main theorem of that primary source.

Searches for the exact phrases “clique partition number” with “number of edges”, “dense graph”, and \(k>n^2/4\) did not locate a paper determining the full two-variable extremal function \(F(n,e)\). Papers on \(K_n\) minus a prescribed graph and on chordal graphs concern restricted families, not the maximum over every graph of a fixed size. This is a reported search miss, not a claim that no such paper exists.

3. An exact reduction to weighted edge-disjoint clique packing

Lemma 1 — exact saving identity (a)

For an edge-disjoint family \(\mathcal Q\) of cliques of order at least three, define its saving by

\[ s(\mathcal Q)=\sum_{Q\in\mathcal Q} \left(\binom{|Q|}{2}-1\right), \]

and put \(S(G)=\max_{\mathcal Q}s(\mathcal Q)\). Then

\[ \boxed{\operatorname{cp}(G)=e(G)-S(G).} \]

Proof. A clique partition \(\mathcal P\) has

\[ |\mathcal P| =\sum_{Q\in\mathcal P}\binom{|Q|}{2} -\sum_{Q\in\mathcal P}\left(\binom{|Q|}{2}-1\right) =e(G)-s(\mathcal P). \]

The \(K_2\) terms have saving zero. Conversely, extend any edge-disjoint clique packing \(\mathcal Q\) by making every uncovered edge a \(K_2\). This is a clique partition with \(e(G)-s(\mathcal Q)\) blocks. Maximizing saving is therefore exactly equivalent to minimizing the number of blocks. \(\square\)

Consequently, if

\[ \Sigma(n,m)=\min_{\substack{|V(G)|=n\\e(G)=q+m}}S(G), \]

then the original problem is exactly

\[ \boxed{F(n,q+m)=q+m-\Sigma(n,m).} \]

This reduction identifies the missing object: a sharp, density-dependent guarantee for a weighted packing of cliques of all orders.

Corollary 2 — triangle-packing bound (a)

Every graph \(G\) satisfies

\[ \operatorname{cp}(G)\le e(G)-2\nu_3(G). \]

Indeed, each packed triangle has saving \(\binom32-1=2\), or equivalently one uses the packed triangles and makes every remaining edge a \(K_2\).

4. A sharp elementary construction

Lemma 3 — Turán plus an internal bipartite graph (a)

Let

\[ a=\lceil n/2\rceil,\qquad b=\lfloor n/2\rfloor. \]

For every

\[ 0\le m\le \left\lfloor\frac{a^2}{4}\right\rfloor \]

there is an \(n\)-vertex graph \(G_{n,m}\) with \(q+m\) edges and

\[ \boxed{\operatorname{cp}(G_{n,m})=q-m.} \]

Construction and proof. Start with \(K_{a,b}\), with parts \(A,B\). Split \(A=X\sqcup Y\), where \(|X|=\lfloor a/2\rfloor\) and \(|Y|=\lceil a/2\rceil\), and add any prescribed \(m\) edges from \(K_{X,Y}\).

For an explicit partition, index \(X=\{x_i\}\), \(Y=\{y_j\}\), and color \(x_i y_j\) by \(j-i\pmod{|Y|}\). Each color class is a matching. Also \(|Y|\le b\), so associate every used color with a different vertex of \(B\). Replace each added edge \(x_i y_j\) of color \(c\) by the triangle \(x_i y_j b_c\). Proper coloring makes these triangles edge-disjoint. Make every unused cross-edge a \(K_2\). There are

\[ m+(q-2m)=q-m \]

blocks.

For the matching lower bound, \(G_{n,m}\) has no \(K_4\): \(B\) is independent and the added graph inside \(A\) is bipartite. Every triangle uses exactly one of the \(m\) added edges. Thus any clique partition has at most \(m\) triangles and only \(K_2\)'s otherwise, so it has at least

\[ (q+m)-2m=q-m \]

blocks. \(\square\)

In the saving language, this construction has \(S(G_{n,m})=2m\).

5. Uniform exact formulas

The first super-Turán layer (a)

For every \(n\ge3\),

\[ \boxed{F(n,q+1)=q-1.} \]

For completeness, here is a from-scratch Mantel argument. If a graph is triangle-free, then for every edge \(uv\), \(d(u)+d(v)\le n\). Summing over edges gives

\[ \sum_vd(v)^2\le ne. \]

Cauchy gives \(\sum_vd(v)^2\ge(2e)^2/n\), hence \(e\le n^2/4\), and therefore \(e\le q\). So every graph with \(q+1\) edges contains a triangle. Use that triangle and \(q-2\) single edges, giving \(q-1\) blocks. Lemma 3 with \(m=1\) supplies a graph requiring \(q-1\) blocks.

\(\square\)

One edge short of complete (a)

For every \(n\ge3\),

\[ \boxed{F\left(n,\binom n2-1\right)=n-1.} \]

There is only one graph up to isomorphism, \(K_n-xy\). It has a partition consisting of \(K_n-y\) and the \(n-2\) remaining edges incident with \(y\), so \(\operatorname{cp}(K_n-xy)\le n-1\).

For the reverse inequality, add the missing pair \(\{x,y\}\) as one two-point block to a clique partition of \(K_n-xy\). The resulting proper blocks partition all pairs of an \(n\)-point set. If \(A\) is their \(n\times b\) incidence matrix and \(r_v\) is the number of blocks through point \(v\), then

\[ AA^\mathsf T=J+\operatorname{diag}(r_v-1). \]

Every \(r_v\ge2\), since a point lying in only one block would force that block to contain all \(n\) points, contrary to properness. Thus the matrix on the right is positive definite:

\[ z^\mathsf TAA^\mathsf Tz =\left(\sum_vz_v\right)^2+\sum_v(r_v-1)z_v^2>0 \]

for nonzero \(z\). Hence \(\operatorname{rank}A=n\), so \(b\ge n\). Deleting the added missing-edge block leaves at least \(n-1\) cliques.

\(\square\)

Of course \(F(n,\binom n2)=1\) (a).

6. An exact linear-excess regime

Theorem 4 (b: Győri's triangle-packing theorem)

Let \(q=\lfloor n^2/4\rfloor\).

\(1\le m\le\tfrac32n-5\), then \[ \boxed{F(n,q+m)=q-m.} \]

\(1\le m\le2n-10\), then \[ \boxed{F(n,q+m)=q-m.} \]

Proof modulo the named theorem. The exact \(\phi_3(n,m)=m\) result recorded in Balogh–Wigal says that every graph in these ranges contains at least \(m\) edge-disjoint triangles. Corollary 2 gives

\[ \operatorname{cp}(G)\le q+m-2m=q-m. \]

Lemma 3 gives equality once its construction has enough internal edges. For \(n=2s\), its capacity is \(\lfloor s^2/4\rfloor\), which is at least \(3s-5\) for \(s\ge10\). For \(n=2s+1\), its capacity is \(\lfloor(s+1)^2/4\rfloor\), which is at least \(4s-8\) for \(s\ge11\); equality occurs at \(s=11\). \(\square\)

This is an exact answer to a growing, linear-width portion of the requested range. I do not claim that this consequence is new; it is not spelled out on the live page.

7. Density-sensitive bounds from verified modern results

Sparse excess (b: Győri, as recorded in Balogh–Wigal)

For every sequence \(m=o(n^2)\),

\[ \boxed{q-m\ \le\ F(n,q+m)\ \le\ q-m+O(m^2/n^2).} \]

The upper bound follows from \(\nu_3(G)\ge m-O(m^2/n^2)\) and Corollary 2. Since \(m=o(n^2)\), Lemma 3 applies for all sufficiently large \(n\) and gives the lower bound. Thus

\[ F(n,q+m)=q-m+o(m) \]

throughout the subquadratic-excess regime.

Full density range (b: Balogh–Wigal 2025)

Their main theorem for \(r=3\) gives \(\nu_3(G)\ge(2/3-o(1))m\), hence

\[ \boxed{F(n,q+m)\le q-(1/3-o(1))m.} \]

This is a genuine sharpening of the Erdős–Goodman–Pósa bound for every positive-density excess, though it is not expected to be sharp at all densities.

A finite large-\(n\) bound (b: Blumenthal et al. 2021)

For sufficiently large \(n\), take their decomposition into \(x\) edges and \(y\) triangles with

\[ 2x+3y\le n^2/2+1,\qquad e=x+3y. \]

Its number of blocks satisfies

\[ x+y=\frac{2(2x+3y)-e}{3} \le\frac{n^2+2-e}{3}. \]

Therefore

\[ \boxed{F(n,e)\le \left\lfloor\frac{n^2+2-e}{3}\right\rfloor} \qquad(n\ \text{sufficiently large}). \]

The standalone checker re-evaluates all integer specialisations of this algebra for \(3\le n\le30\).

8. Exact exhaustive computation through seven vertices

Result (d: computational-only)

For every labeled graph on \(n\le7\) vertices, the verifier computes \(\operatorname{cp}(G)\) exactly and then maximizes at each edge count. In each row below, the list is ordered by

\[ e=q+1,q+2,\ldots,\binom n2. \]

| \(n\) | \(q\) | \(F(n,q+1),\ldots,F(n,\binom n2)\) | |---:|---:|:---| | 2 | 1 | empty | | 3 | 2 | \(1\) | | 4 | 4 | \(3,1\) | | 5 | 6 | \(5,4,4,1\) | | 6 | 9 | \(8,7,6,5,5,1\) | | 7 | 12 | \(11,10,9,8,7,7,8,6,1\) |

The last row proves, at the computational level only, that this extremal function need not be monotone in the number of edges:

\[ \boxed{F(7,18)=7<8=F(7,19).} \]

An extremal 19-edge witness is \(K_7-\{34,56\}\). One certified eight-block partition is

\[ \{01\},\{02\},\{036\},\{045\}, \{1246\},\{13\},\{15\},\{235\}. \]

The exhaustive recurrence proves computationally that seven blocks are impossible for this witness and that no other 19-edge graph requires more than eight.

Why the computation is exact

Encode the \(\binom n2\) possible edges as bits. For a nonempty edge mask \(E\), fix one present edge \(a\). In every clique partition, exactly one block contains \(a\). Therefore

\[ \operatorname{cp}(E)= 1+\min_{\substack{Q\text{ a clique}\\a\in E(Q)\subseteq E}} \operatorname{cp}(E\setminus E(Q)). \]

Every state on the right is a smaller integer mask, so a bottom-up dynamic program evaluates every graph without an optimization oracle. The essential kernel is:

for graph in range(1, 1 << binom_n_2):
    anchor = graph & -graph
    anchor_index = anchor.bit_length() - 1
    best = 1 + cp[graph ^ anchor]       # anchor as a K_2
    for clique in cliques_by_edge[anchor_index]:
        if graph & clique == clique:
            best = min(best, 1 + cp[graph ^ clique])
    cp[graph] = best
    extrema[graph.bit_count()] = max(
        extrema[graph.bit_count()], best
    )

For every extremal witness, a separately memoized solver anchors at the highest present edge and traverses candidates in the reverse order. Recovered partitions are checked edge by edge. The program also constructs the Turán-plus-internal graphs, checks they contain no \(K_4\), checks that each triangle spends exactly one internal edge, validates the explicit partitions, and rechecks the capacity and floor arithmetic.

The complete standalone source is runs/erdos1017_wavew029_verify.py; it uses only the Python standard library and no saved result, SAT solver, ILP solver, graph library, or network access.

Run:

python3 runs/erdos1017_wavew029_verify.py --max-n 7
python3 runs/erdos1017_wavew029_verify.py --max-n 7 --show-witnesses

Observed clean output:

Exact f(n,k)=max_{|V|=n,e=k} cp(G), exhaustive over labelled graphs
n  floor(n^2/4)  values for k=floor(n^2/4)+1,...,C(n,2)
2             1  []
3             2  [1]
4             4  [3, 1]
5             6  [5, 4, 4, 1]
6             9  [8, 7, 6, 5, 5, 1]
7            12  [11, 10, 9, 8, 7, 7, 8, 6, 1]
Construction/integer checks: PASS
All opposite-anchor witness checks: PASS

Measured on this VM: 6.22 seconds wall time and 16,720 KiB maximum RSS.

9. Precise remaining wall

The exact reduction in Lemma 1 shows what is missing. One needs a sharp estimate of

\[ \Sigma(n,m)= \min_{e(G)=q+m} \max_{\mathcal Q} \sum_{Q\in\mathcal Q}\left(\binom{|Q|}{2}-1\right), \]

where the maximum is over edge-disjoint cliques of arbitrary order.

The verified machinery currently gives

\[ \Sigma(n,m)\ge \begin{cases} 2m-O(m^2/n^2),&m=o(n^2),\\ (4/3-o(1))m,&\text{all }m, \end{cases} \]

while Lemma 3 gives \(\Sigma(n,m)\le2m\) for \(m\le\lfloor\lceil n/2\rceil^2/4\rfloor\). These bounds match to first order only when \(m=o(n^2)\). For \(m=\Theta(n^2)\), the exact missing lemma is a sharp lower bound on this weighted all-clique packing, not merely on a triangle packing. Larger cliques can create substantially more saving, and the \(n=7\) table shows that divisibility/design effects can even destroy monotonicity near the complete graph.

(c) A fractional weighted-packing problem followed by a dense packing/nibble integrality step is a plausible route, but no source found in this run states the required sharp density function, and I did not derive it. It is therefore not presented as a theorem.

The full labeled DP at \(n=8\) would have \(2^{28}=268{,}435{,}456\) states and up to 64 anchored clique candidates per state—about \(1.7\times10^{10}\) subset tests and at least 256 MiB just for the byte table. Scaling from the measured \(n=7\) run suggests roughly 15–30 CPU-minutes in this Python implementation, outside the allowed few-minute budget, so it was not run. Canonical unlabeled generation could reduce the instance count, but would replace the from-scratch labeled enumeration by reliance on an external isomorph-free generator.

PARTIAL: proved two uniform closed forms, an exact linear-excess regime modulo Győri's verified packing theorem, a sharp subquadratic estimate, an exact weighted-packing reduction, and the exhaustive table through n=7; the full positive-density function remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger