Fix an integer r≥3. Let Kr denote the complete graph on r vertices and tr−1(n) the Turán number for Kr. For each integer k satisfying 0≤k≤(2n)−tr−1(n), \rev{ϕ_r(n,k)} denotes the minimum, over all n-vertex graphs with tr−1(n)+k edges, of the maximum size of a Kr-packing \rev{(a family of edge-disjoint copies of Kr)} in the graph. The problem of characterizing the behavior of ϕr(n,k) has a long history and dates back to Erdős for the case r=3. \rev{Győri} proved that ϕr(n,k)=(1−o(1))k whenever k=o(n2). We characterize the range of k for which ϕr(n,k)=(1−o(1))k, showing that this equality holds if and only if k=o(n2). Moreover, we obtain an \rev{asymptotic} upper bound (which falls below 1) for ϕr(n,k)/k whenever k/n2 converges to a constant δ satisfying 0<δ≤2(r−1)1.
Introduction
Throughout the paper, all graphs considered are finite and simple. For a graph G, V(G) denotes its vertex set and E(G) its edge set. Let Kr be the complete graph on r vertices. A Kr-packing of G is a family of edge-disjoint copies of Kr in G, and νr(G) denotes the maximum cardinality of such a family. Denote by tr−1(n) the number of edges of the Turán graph on n vertices with r−1 parts, which is the complete (r−1)-partite graph whose partition classes have sizes differing by at most 1. Set e(G):=∣E(G)∣. Define the function ϕr(n,k)=minGνr(G), where the minimum is taken over all n-vertex graphs G satisfying e(G)=tr−1(n)+k. By Turán’s Theorem, ϕr(n,0)=0. The problem of characterizing the behavior of ϕr(n,k) for 0<k≤(2n)−tr−1(n) has a long history and dates back to Erdős for the case r=3[2]. He proved that ϕ3(n,k)=k whenever 0<k<cn, where c<1/2 is a constant. This result was subsequently refined by Győri [3, 5].
Theorem 1.1 (Győri, [3, 5]). For all sufficiently large n, ϕ3(n,k)=k if k≤2n−10 for odd n, or if k≤23n−5 for even $n.
Examples in [5] show that the upper bounds for k in Theorem 1.1 are sharp. The graph G is Kr-free if it contains no copy of Kr. A very precise result of Győri and Keszegh [6] exhibits a much larger admissible range of k with k of order Θ(n2) rather than linear in n, for the guarantee of at least k edge-disjoint triangles under the additional K4-free constraint.
Theorem 1.2 (Győri and Keszegh, [6]). Any K4-free graph on n vertices with ⌊n2/4⌋+k edges, where k≥0 is an integer, contains at least k pairwise edge-disjoint triangles.
Theorem 1.3 (Győri, [3, 4]). Let r≥3 be fixed. For all sufficiently large n,
(i) If r≥4, ϕr(n,k)=k whenever k≤3⌊r−1n+1⌋−5;
(ii) ϕr(n,k)=(1−o(1))k whenever k=o(n2).
Balogh and Wigal [1] gave constructions for certain sequences k=Θ(n2) for which ϕ3(n,k)≤(1−c)k with a fixed c>0. They also asked for the range of k in which ϕr(n,k)=(1−o(1))k. We answer this question by proving the equality holds if and only if k=o(n2).
Theorem 1.4. Fix an integer r≥3, and let k=k(n) be a sequence of integers satisfying 1≤k≤(2n)−tr−1(n) for all sufficiently large n. Then, as n→∞,
ϕr(n,k(n))=(1−o(1))k if and only if k(n)=o(n2).
By Wilson’s Theorem [7], applied to the complete graph Kn (i.e. k=(2n)−tr−1(n)), ϕr(n,k)=r(2−o(1))k. Indeed, one may choose n′=n−Or(1) satisfying Wilson’s divisibility conditions and decompose a copy of Kn′ inside Kn. A result of Balogh and Wigal [1] implies that ϕr(n,k)≥r(2−o(1))k, for all 0<k≤(2n)−tr−1(n). Our second result gives an explicit asymptotic upper bound for ϕr(n,k)/k, strictly smaller than 1, when n2k→δ.
Theorem 1.5. Fix an integer r≥3, and let k=k(n) be a sequence of integers satisfying 1≤k≤(2n)−tr−1(n) for all sufficiently large n. Let 0<δ≤2(r−1)1 be any real and set s:=1−1−2(r−1)δ. If n2k→δ, then
n→∞limsupkϕr(n,k)≤1−r(2−s)s(r−2)<1.
Notation and Terminology
Throughout the paper, all asymptotic notation is understood as n→∞, where n is the number of vertices and r≥3 is a fixed integer (independent of n). Let f(n) and g(n) be real-valued sequences with g(n)>0 for all sufficiently large n. We write f(n)=o(g(n)) if f(n)/g(n)→0 as n→∞; we write f(n)=O(g(n)) if there exists a constant C>0 such that ∣f(n)∣≤Cg(n) for all sufficiently large n; and we write f(n)=Θ(g(n)) if there exist positive constants c and C such that cg(n)≤f(n)≤Cg(n) for all sufficiently large n. All implied constants are allowed to depend on the fixed parameter r (and on any other fixed parameters, such as ε), but not on n. Whenever we wish to emphasize that the implied constant depends only on r, we attach the subscript and write Or(⋅), or(⋅), or Θr(⋅); for instance, f(n)=Or(g(n)) means that the constant C above depends only on r, and the bound holds uniformly for all n sufficiently large.
For a graph G, let V(G) be its vertex set and E(G) its edge set. For a vertex set S⊆V(G), G[S] denotes the subgraph of G induced by S. An independent set (or stable set) in a graph G is a subset S⊆V(G) of vertices such that no two distinct vertices in S are adjacent. The join G∨H of two vertex-disjoint graphs G and H is the graph containing all edges of G and $H, plus every edge between V(G) and V(H). More generally, for vertex-disjoint graphs X and Y in a common ambient graph, we write E(X,Y) for the set of edges with one endpoint in V(X) and the other in V(Y); thus E(G∨H)=E(G)∪E(G,H)∪E(H). A graph G is Kr-free if it contains no copy of Kr. For positive integers r and n, the Turán graph Tr(n) is the complete r-partite graph on n vertices whose parts differ in size by at most one. Its size tr(n):=e(Tr(n)) is the Turán number for Kr+1, namely the maximum size of an n-vertex Kr+1-free graph.
A Kr-packing of G is a family of edge-disjoint copies of Kr in G, and νr(G) denotes the maximum cardinality of such a family. For an n-vertex graph with tr−1(n)+k edges, the integer k is its number of excess edges above tr−1(n). Note that 0≤k≤kn:=(2n)−tr−1(n). Define
In other words, ϕr(n,k) is the minimum possible number of edge-disjoint copies of Kr in a maximum Kr-packing of an n-vertex graph with exactly tr−1(n)+k edges. A graph attaining this minimum is called an extremal graph for ϕr(n,k). Let Kr(G) denote the set of all copies of Kr in G. The following definition is a fractional relaxation of Kr-packing.
Definition 2.1 (Fractional Kr-packing). A fractional Kr-packing of a graph G is a function ω:Kr(G)→[0,1] such that for every e∈E(G),
H∈Kr(G)e∈E(H)∑ω(H)≤1.
The weight of ω is ∣ω∣=∑H∈Kr(G)ω(H). The fractional Kr-packing number of G, denoted by νr∗(G), is the maximum weight of a fractional Kr-packing of G.
Every Kr-packing can be viewed as a fractional Kr-packing whose weights are restricted to {0,1}. Consequently,
νr(G)≤νr∗(G).
A closely related notion is that of a Kr-cover. A Kr-cover of G is a set of edges that intersects every copy of Kr in G, and τr(G) denotes the minimum cardinality of a Kr-cover of G. There is also a fractional relaxation of this notion.
Definition 2.2 (Fractional Kr-cover). A fractional Kr-cover of a graph G is a function φ:E(G)→[0,1] such that for every H∈Kr(G),
e∈E(H)∑φ(e)≥1.
The weight of φ is defined as ∣φ∣=∑e∈E(G)φ(e), and the fractional Kr-covering number of G, denoted by τr∗(G), is the minimum weight of a fractional Kr-cover of G.
A Kr-cover of G can be identified with a fractional Kr-cover taking values in {0,1}. Consequently,
τr∗(G)≤τr(G).
By strong duality in linear programming, the fractional Kr-packing number equals the fractional Kr-covering number. Therefore,
νr(G)≤νr∗(G)=τr∗(G)≤τr(G).(2)
A construction and its fractional cover
To prove the necessity of Theorem 1.4, we construct a family of graphs equipped with explicit fractional Kr-covers whose weights are substantially smaller than their numbers of excess edges over the Turán number for Kr. This construction also yields asymptotic upper bounds for ϕr(n,k) when k=Θ(n2).
The Constructions
Given integers a∈{0,1,…,n} and r≥3, let
Ga=Ka∨Tr−1(n−a)(3)
denote the join of the complete graph Ka and the Turán graph Tr−1(n−a). Let
ka:=e(Ga)−tr−1(n)(4)
be the number of edges of Ga in excess of the Turán number tr−1(n) for Kr. Observe that G0=Tr−1(n) and Gn=Kn, whence k0=0 and kn=(2n)−tr−1(n). We shall establish an exact formula for ka in the following subsection, which in particular shows that ka is monotone non-decreasing in a. Consequently, k0=0 and kn=(2n)−tr−1(n) are precisely the two boundary values for the range of k.
Next, we assign weights to the edges of Ga to obtain a fractional cover. For an edge e∈E(Ga), define
Write Wa:=∣wa∣=∑e∈E(Ga)wa(e) for its total weight. We will show in the next subsection that wa is indeed a fractional Kr-cover of Ga; that is, every copy C of Kr in Ga satisfies ∑e∈E(C)wa(e)≥1.
Edge counts and cover weights
First we give an exact expression for ka showing that ka is monotone in a. Thus the excess edge number ka satisfying 0=k0≤ka≤kn=(2n)−tr−1(n) falls exactly within our target range of k. Before stating the lemma, we introduce notation to control rounding effects on the part sizes of Turán graphs. For each integer m≥0, write m=(r−1)ℓ+ρm, where ℓ and ρm are integers with ℓ≥0 and 0≤ρm<r−1. Let
ηr−1(m):=2(r−1)ρm((r−1)−ρm).
Recall that the Turán graph Tr−1(m) has ρm parts of size ℓ+1 and (r−1)−ρm parts of size ℓ. Counting the edges between different parts yields the exact formula
It remains to prove (ii). Put m:=n−a≥1. To pass from Ga to Ga+1, take a vertex v of Tr−1(m) lying in a part of maximum size and move it into the clique Ka, turning the join into Ka+1∨Tr−1(m−1). Removing v from that maximum part leaves a copy of Tr−1(m−1) and affects no edge outside v; hence only the edges incident to v change. In Ga, the vertex v is adjacent to the a vertices of Ka and to the m−⌈m/(r−1)⌉ vertices of Tr−1(m) outside its own part; in Ga+1, it is adjacent to the a vertices of the original clique and to all m−1 vertices of Tr−1(m−1). Its degree therefore changes by (m−1)−(m−⌈m/(r−1)⌉), and since the fixed constant tr−1(n) is subtracted from both e(Ga) and e(Ga+1), we obtain
ka+1−ka=(m−1)−(m−⌈r−1m⌉)=⌈r−1m⌉−1,
which proves (ii). Since 1≤m≤n, each increment lies in [0,⌈n/(r−1)⌉−1], so ka is non-decreasing in a, and consecutive distinct values of ka differ by Or(n).
We proceed by proving that the function wa defined by (5) in the preceding subsection is in fact a fractional Kr-cover of Ga; its total weight is also determined simultaneously.
Lemma 3.2. The function wa is a fractional Kr-cover of Ga, and
Proof. Let Q be an arbitrary copy of Kr in Ga, where Ga=Ka∨Tr−1(n−a) by (3). Set j:=∣V(Q)∩V(Ka)∣. Since the subgraph induced by V(Ga)∖V(Ka) is Tr−1(n−a), which is Kr-free, every Kr-copy must intersect V(Ka). So 1≤j≤r. The edges of Q with positive weight are of two types: the (2j) edges induced by V(Q)∩V(Ka) each carrying weight r(r−1)2 by (5), and the j(r−j) edges between Ka and Tr−1(n−a) each carrying weight r−11 by (5); all other edges are assigned weight zero. Thus
e∈E(Q)∑wa(e)=r(r−1)2(2j)+r−1j(r−j)
=rj(r+1−j)
=1+r(j−1)(r−j)
≥1.
The inequality holds because both (j−1) and (r−j) are nonnegative for 1≤j≤r. Therefore, by Definition 2.2, wa is a fractional Kr-cover of Ga. The first part of the lemma follows.
We next calculate the total weight of wa. Counting the (2a) edges inside Ka each of weight r(r−1)2 by (5) and the a(n−a) edges between Ka and Tr−1(n−a) each of weight r−11 by (5), we obtain
Let Da:=ka−Wa be the difference of the excess edge number and the total cover weight. By Definition 2.2, τr∗(Ga)≤∣wa∣=Wa. Combined with (2), this implies
νr(Ga)≤τr∗(Ga)≤Wa=ka−Da.(7)
Now we bound Da from below to obtain an upper bound on νr(Ga).
Lemma 3.3. For every integer a with 0≤a≤n, we have
The last equality is justified as follows: By (6), the difference ηr−1(n)−ηr−1(n−a) is bounded in absolute value by (r−1)/8; the linear term in a is Or(a). As r is fixed, each of these is Or(a+1), so the non-quadratic terms are Or(a+1) as claimed.
When a is a positive fraction of n, the quadratic term in the formula of Lemma 3.3 is of order n2. Although by construction ka satisfies 0≤ka≤(2n)−tr−1(n), it may skip certain integers and hence need not take all the admissible values. To ensure that every admissible integer is attained, we add edges to Ga, assigning weight 1 to each new edge. Each addition increases the excess edge count and the cover weight by the same amount, so the difference ka−Wa=Da is preserved. Every integer in the admissible range is thus realized.
Lemma 3.4. For every integer k with 0≤k≤(2n)−tr−1(n), there exist an integer a∈{0,1,…,n} and an n-vertex graph H such that
e(H)=tr−1(n)+kandνr(H)≤k−Da,
where ka≤k<ka+1 if a<n, and k=kn if a=n.
Proof. If k=kn, take a=n and H=Gn=Kn. Lemma 3.2 together with (7) then yields νr(H)≤Wn=k−Dn, as required. Suppose now that k<kn, and choose a maximal subject to ka≤k. Since k0=0≤k<kn, such an index a exists and satisfies 0≤a<n. Maximality of a indicates that k<ka+1. Let d:=k−ka. By Lemma 3.1-(ii)
0≤d<ka+1−ka=⌈r−1n−a⌉−1.
We construct H from Ga by adding d edges. First note that the number of non-edges of Ga is
(2n)−e(Ga)=kn−ka≥k−ka=d,
so Ga contains sufficiently many missing edges for the required adjustment. Since e(Ga)=tr−1(n)+ka and d=k−ka, we have
e(H)=e(Ga)+d=tr−1(n)+k.
Finally, we extend wa to E(H) by retaining the weights on E(Ga) and assigning unit weight to each added edge. To verify that the resulting weighting is a fractional Kr-cover, let Q be an arbitrary copy of Kr in H. If Q contains an added edge, then that edge alone carries weight 1. Otherwise every edge of Q lies in Ga, and its total weight is at least 1 by Lemma 3.2. The extended weighting is therefore a fractional Kr-cover of total weight Wa+d. By Definition 2.2 and (2),
νr(H)≤Wa+d=Wa+(k−ka)=k−Da,
which completes the proof of this lemma.
Now we are ready to prove our main theorems.
Proof of Theorem 1.4
The sufficiency of Theorem 1.4 follows from Theorem 1.3-(ii). It remains to prove the necessity of the theorem. We argue by contradiction. Let 1≤k≤(2n)−tr−1(n) and n sufficiently large. Suppose that ϕr(n,k)=(1−o(1))k and k=o(n2). Since k is not o(n2), there exist a constant ε>0 and an infinite subsequence k=k(n) such that k≥εn2. By decreasing ε if necessary, we may assume that ε≤2(r−1)1. For each such k=k(n), apply Lemma 3.4, there exist an integer a∈{0,…,n} and an n-vertex graph H such that
In the last inequality, a≤n and sufficiently large n allow the Or(a+1) error to be absorbed into half of the quadratic term. Since k≤(2n)−tr−1(n)<n2/2, we have
By (1), we know that ϕr(n,k)≤νr(H)≤(1−8r(r−2)(r−1)ε2)k. Thus the ratio ϕr(n,k)/k is bounded above by a constant strictly smaller than 1 along this subsequence, a contradiction. This finishes our proof of Theorem 1.4.
Proof of Theorem 1.5
Suppose that n2k tends to δ, when n tends to infinity. By Lemma 3.4, for each k, there exist an integer a∈{0,…,n} and an n-vertex graph H such that
e(H)=tr−1(n)+k,νr(H)≤k−Da,ka≤k<ka+1 or k=kn.
Put sn:=a/n, so that 0≤sn≤1. If a<n, Lemma 3.1-(ii) gives 0≤k−ka<ka+1−ka=Or(n); if a=n, then k=ka. Hence k−ka=Or(n) in both cases, and ka/n2→δ. By Lemma 3.1-(i) and (6),
n2ka=2(r−1)sn(2−sn)+Or(1/n).
Since 0≤sn≤1, it follows that
sn=1−1−sn(2−sn)⟶1−1−2(r−1)δ=s.
In particular, δ=s(2−s)/(2(r−1)).
Lemma 3.3 indicates that Da=2r(r−1)r−2a2−Or(a+1). By (1),
Fuhong Ma is supported by the National Natural Science Foundation of China (Grant number 12401458) and Natural Science Foundation of Shandong Province (Grant number ZR2024QA239). Jin Yan is supported by the National Natural Science Foundation of China (Grant number 12571373) and Natural Science Foundation of Shandong Province (Grant number ZR2025MS05).
Declaration on the use of AI
During the early stages of this research, the authors constructed the counterexample graph Ga=Ka∨Tr−1(n−a) and obtained computational evidence supporting the main theorem, but had not yet found a rigorous mathematical proof. In subsequent discussions with AI, GPT-6 Astra suggested an approach based on assigning weights to edges. The authors adopted this suggestion and developed it further, ultimately obtaining the rigorous mathematical proof presented in this manuscript. AI models also assisted with proof checking, proofreading, and language editing. The authors take full responsibility for all AI-assisted work and for the content of the manuscript.
References
[1]J. Balogh and M. C. Wigal, Packing edge disjoint cliques in graphs, Combinatorica 45 (2025), no. 5, Paper No. 56.arxiv.org/abs/2502.16683
[2]P. Erdős, Some unsolved problems in graph theory and combinatorial analysis, in: Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press, London–New York, 1971, pp. 97–109.
[3]E. Győri, On the number of edge disjoint triangles in graphs of given size, in: Combinatorics (Eger, 1987), Colloq. Math. Soc. János Bolyai, vol. 52, North-Holland, Amsterdam, 1988, pp. 267–276.
[4]E. Győri, On the number of edge disjoint cliques in graphs of given size, Combinatorica 11 (1991), 231–243.DOI
[5]E. Győri, Edge disjoint cliques in graphs, in: Sets, Graphs, and Numbers (Budapest, 1991), Colloq. Math. Soc. János Bolyai, vol. 60, North-Holland, Amsterdam, 1992, pp. 357–363.
[6]E. Győri and B. Keszegh, On the number of edge-disjoint triangles in K₄-free graphs, Combinatorica 37 (2017), 1113–1124.
[7]R. M. Wilson, Decomposition of complete graphs into subgraphs isomorphic to a given graph, in: Proceedings of the Fifth British Combinatorial Conference, Congr. Numer. XV, Utilitas Math., Winnipeg, 1976, pp. 647–659.