1 Introduction
One of the central topics in extremal graph theory is the Turán type problem which asks, for a fixed graph H, what is the maximum number of edges in an H-freeFootnote
1
graph on n vertices. Such a maximum number is called the Turán number (or extremal number) of H and is denoted by
${\text {ex}}(n,H)$
. The well-known Mantel’s Theorem [Reference Mantel26] determines the Turán number for triangles, and Turán’s Theorem [Reference Turán32] generalizes the result from triangles to general cliques. Let
$T_{r-1}(n)$
be the
$(r-1)$
-partite Turán graph, that is, the complete
$(r-1)$
-partite graph on n vertices with part sizes as equal as possible. Let
$t_{r-1}(n)$
be the number of edges of
$T_{r-1}(n)$
. Turán’s Theorem says that
${\text {ex}}(n, K_r)=t_{r-1}(n)$
which is uniquely attained by
$T_{r-1}(n)$
. For a general graph H, the celebrated Erdős–Stone–Simonovits Theorem [Reference Erdős and Simonovits9, Reference Erdős and Stone10] shows that
${\text {ex}}(n, H)=\big (1-\frac {1}{\chi (H)-1}+o(1)\big )\frac {n^2}{2}$
, where
$\chi (H)$
is the chromatic number of H. A graph is called r-color-critical if it has chromatic number r, and it has an edge (called a critical edge) whose removal reduces the chromatic number to
$r-1$
. For any r-color-critical graph H and sufficiently large n, Simonovits [Reference Simonovits30] proved that
${\text {ex}}(n, H)=t_{r-1}(n)$
and
$T_{r-1}(n)$
is the unique extremal graph.
In the last two decades, the study of extremal problems for multicolor versions became an active research topic. Let
$\mathcal {G}=\{G_1, \ldots , G_k\}$
be a collection of not necessarily distinct graphs on the same vertex set V. A graph H with
$V(H)\subseteq V$
is called a multicolored (or rainbow) subgraph of
$\mathcal {G}$
if there exists an injection
$\varphi : E(H)\to [k]$
such that
$e\in E(G_{\varphi (e)})$
for each
$e\in E(H)$
. The following general question has been extensively studied.
-
Let
$\mathcal {G}=\{G_1, \ldots , G_k\}$
be a collection of graphs on the same vertex set V, and H be a graph with
$e(H)\leq k$
. Which extremal conditions, when imposed on
$\mathcal {G}$
, can lead to the existence of a multicolored copy of H?
Roughly speaking, two distinct types of extremal conditions have been studied:
-
• minimum-type:
$\min _{i\in [k]}e(G_i)$
[Reference Aharoni, DeVos, de la Maza, Montejano and Šámal1, Reference Babiński and Grzesik3, Reference Babiński, Grzesik and Prorok4, Reference Im, Kim, Lee and Seo17, Reference Kiselev and Kupavskii21] and
$\min _{i\in [k]}\delta (G_i)$
[Reference Cheng, Han, Wang and Wang8, Reference Falgas-Ravry, Markström and Räty11, Reference Falgas-Ravry, Markström and Räty12, Reference Joos and Kim18, Reference Lu, Wang and Yu23, Reference Lu, Yu and Yuan24]; -
• average-type:
$\sum _{i\in [k]}e(G_i)$
[Reference Babiński, Grzesik and Prorok4, Reference Chakraborti, Kim, Lee, Liu and Seo7, Reference Frankl13, Reference Gerbner, Grzesik, Palmer and Prorok14, Reference Keevash, Saks, Sudakov and Verstraëte20, Reference Ma and Hou25] and
$\prod _{i\in [k]}e(G_i)$
[Reference Falgas-Ravry, Markström and Räty12, Reference Frankl13, Reference He, Frankl, Győri, Lv, Salia, Tompkins, Varga and Zhu15].
Note that in the special case, when all
$G_i$
are identical (say G), the existence of a multicolored H is equivalent to the existence of a copy of H in G. Thus, the study on
$\min _{i\in [k]}e(G_i)$
generalizes the original Turán problem. On the other hand, if
$G_1, \ldots , G_k$
are pairwise edge-disjoint matchings, then
$\mathcal {G}$
is equivalent to a properly edge-colored graph. Thus, in this case, determining
$\sum _{i\in [k]}e(G_i)$
is equivalent to the rainbow Turán problem introduced by Keevash et al. [Reference Keevash, Mubayi, Sudakov and Verstraëte19].
In this article, we mainly focus on the multicolor Turán problem proposed by Keevash et al. [Reference Keevash, Saks, Sudakov and Verstraëte20] in 2004. The authors of [Reference Keevash, Saks, Sudakov and Verstraëte20] used a different notion rather than the collection of graphs. A simple k-coloring of a multigraph G is a decomposition of the edge multiset as a disjoint sum of k simple graphs which are referred to as colors. A multigraph with a simple k-coloring is called a simply k-colored multigraph. A subgraphFootnote
2
H of a multigraph G is called multicolored if its edges receive distinct colors in a given simple k-coloring of G. The k-color Turán number, denoted by
${\text {ex}}_k(n,H)$
, is the maximum number of edges in an n-vertex multigraph that has a simple k-coloring containing no multicolored copies of H. The simply k-colored multigraphs without multicolored copies of H that achieve this maximum are called the k-color extremal multigraphs of H.
If
$k \leq e(H)-1$
, there are no multicolored copies of H with k colors. In this case, the unique k-color extremal multigraph is the multigraph consisting of k copies of complete graphs. For
$k\geq e(H)$
, there are two natural candidates for the k-color extremal multigraphs on n vertices:
-
(i) the multigraph consisting of
$e(H)-1$
copies of the complete graph
$K_n$
; -
(ii) the multigraph consisting of k identical copies of a fixed extremal H-free graph
$G_{{\text {ext}}}$
.
We use
$(e(H)-1)\cdot K_n$
to denote the first multigraph, and
$k \cdot G_{{\text {ext}}}$
to denote the second multigraph. Keevash et al. [Reference Keevash, Saks, Sudakov and Verstraëte20] proved that the second construction is always extremal when k is sufficiently large.
Theorem 1.1 [Reference Keevash, Saks, Sudakov and Verstraëte20, Theorem 1.1]
Let H be a graph and
$k, n$
be two positive integers. If
$$ \begin{align*}k\geq {n \choose 2} -{\text{ex}}(n,H)+ e(H),\end{align*} $$
then
${\text {ex}}_k(n, H)=k\cdot {\text {ex}}(n,H)$
, and in any k-color extremal multigraph of H, all the k colors are identical copies of an extremal H-free graph.
The authors of [Reference Keevash, Saks, Sudakov and Verstraëte20] made the following general conjecture for color-critical graphs.
Conjecture 1.2 [Reference Keevash, Saks, Sudakov and Verstraëte20, Conjecture 1.3]
Let
$r\geq 3$
,
$k\geq h$
, and H be an r-color-critical graph with h edges. Then, for sufficiently large n, the n-vertex k-color extremal multigraph of H either consists of k colors all of which are identical copies of
$T_{r-1}(n)$
or consists of exactly
$h-1$
colors all of which are copies of
$K_n$
. In particular,
$$ \begin{align*}{\text{ex}}_k(n, H)= \left\{ \begin{aligned} &k\cdot t_{r-1}(n) & & \text{for }k\geq \frac{r-1}{r-2}(h-1),\\ &\left(h-1\right){n\choose 2} & & \text{for }h\leq k< \frac{r-1}{r-2}(h-1). \end{aligned} \right.\end{align*} $$
We should refer to the range
$k\geq \frac {r-1}{r-2}(h-1)$
as the upper range and the range
$h\leq k< \frac {r-1}{r-2}(h-1)$
as the lower range. The authors of [Reference Keevash, Saks, Sudakov and Verstraëte20] confirmed this for all cliques
$K_r$
when
$n>10^{4}r^{34}$
. Recently, Frankl [Reference Frankl13] and Ma and Hou [Reference Ma and Hou25] proved that for all
$n\geq r-1$
,
${\text {ex}}_k(n, K_r)\leq \max \big \{k\cdot t_{r-1}(n), \left ({r\choose 2}-1\right ){n\choose 2}\big \}$
holds in the cases
$r=3$
and
$r=4,5$
, respectively. Conjecture 1.2 was confirmed in full for
$r=3$
by Keevash et al. [Reference Keevash, Saks, Sudakov and Verstraëte20] and for
$r=4,$
by Chakraborti, Kim, Lee, Liu, and Seo [Reference Chakraborti, Kim, Lee, Liu and Seo7]. For
$r\geq 5$
, Chakraborti et al. [Reference Chakraborti, Kim, Lee, Liu and Seo7] proved that Conjecture 1.2 holds for a rich family of r-color-critical graphs whose edges are distributed somewhat evenly. Note that Theorem 1.1 implies that Conjecture 1.2 holds for
$k\geq (1+o(1))\frac {1}{r-1}{n\choose 2}$
.
In this article, we show that Conjecture 1.2 holds in the range of
$k\geq 2\frac {r-1}{r}(h-1)$
.
Theorem 1.3 Let
$r\geq 5$
and H be an r-color-critical graph with h edges. If n is sufficiently large and
$$ \begin{align*}k\geq 2\frac{r-1}{r}(h-1),\end{align*} $$
then
${\text {ex}}_k(n, H)=k\cdot t_{r-1}(n)$
, and the unique n-vertex k-color extremal multigraph of H consists of k colors all of which are identical copies of
$T_{r-1}(n)$
.
In fact, we prove a slightly stronger result (see Theorem 5.6), where the same statement holds under a weaker condition that
$$ \begin{align*}k> \max\left\{\frac{r-1}{r-2}(h-1), 2\frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right)\right\}.\end{align*} $$
This improves Theorem 1.1 from
$k\geq (1+o(1))\frac {1}{r-1}{n\choose 2}$
to
$k=\Omega (h)$
for all r-color-critical graphs. Our proof combines the stability argument of Chakraborti et al. [Reference Chakraborti, Kim, Lee, Liu and Seo7] with a novel graph packing technique for embedding multigraphs. For an illustration of the proof sketch, we refer readers to Section 3.
The remainder of this article is organized as follows. In the next section, we introduce some additional terminology and notation, and state some existing results that will be used in our proofs. In Section 3, we supply a proof sketch of our main result. In Section 4, we show the first step of our proof, that is, establishing an analogous statement for the so-called r-vertex r-color-critical multigraphs. In Section 5, we complete our proof of Theorem 1.3. Finally, we conclude the article with some remarks and open problems in Section 6; in particular, we prove a tight k-colored Turán type result for general graphs with h edges and chromatic number r when
$h\leq k\leq h+\big \lfloor \frac {r}{2}\big \rfloor -1$
.
2 Preliminaries
In this section, we introduce some additional terminology and notation, as well as several lemmas that will be used in our proof of the main result.
2.1 Terminology and some technical inequalities
Throughout this article, we consider both simple graphs and multigraphs (a multigraph refers to a multigraph with no loops). We will also view a simple graph as a multigraph in which every edge has multiplicity 1.
Let G be a multigraph with vertex set
$V(G)$
and edge multiset
$E(G)$
. Let 
. For any
$\{u,v\}\in {V(G)\choose 2}$
, we also write it as
$uv$
or
$vu$
. We shall call an element e in
${V(G)\choose 2}$
an edge, although the multiplicity of e could be 0 in G (i.e., e is in fact not an actual edge of G). For
$e\in {V(G)\choose 2}$
, the multiplicity of e in G is written as
$w_G(e)$
. For a subset
$E\subseteq {V(G)\choose 2}$
, let 
. For any
$v\in V(G)$
and
$U\subseteq V(G)$
, let 
. The degree
$d_G(v)$
of a vertex v in G is the number of edges (counted with multiplicity) incident with v, i.e.,
$d_G(v)=\sum _{u\in V(G)}w_G(vu)$
. Let 
be the minimum degree of G. We use
$e(G)$
to denote the number of edges (counted with multiplicity) of G, i.e.,
$e(G)=|E(G)|=\sum _{e\in {V(G)\choose 2}}w_G(e)$
.
Given two disjoint vertex sets
$U, V\subseteq V(G)$
, let
$E(U,V)$
be the set of edges between U and V in G, and let 
. For a vertex subset
$U\subseteq V(G)$
, the subgraph of G induced by U, denoted by
$G[U]$
, is the subgraph of G with vertex set U and edge multiset
$\{e\in E(G)\colon \, \text {both end-vertices of} e \text {are contained in} U\}$
. Moreover, let 
. For an edge sub-multiset
$E\subseteq E(G)$
, let
$G[E]$
be the edge-induced subgraph of G with vertex set
$\{v\in V(G)\colon \, v \text {is incident with some} e\in E\}$
and edge multiset E.
For a positive integer n, let 
. For a set S of real numbers and
$1\leq \ell \leq |S|$
, let
$\min _{\ell } S$
(resp.,
$\max _{\ell } S$
) be the
$\ell $
-th smallest (resp., largest) number in S. For the sake of clarity of presentation, we systematically omit floor and ceiling signs, whenever they are not crucial. When we say a result holds for
$0\leq a\ll b\leq 1$
, we mean that there exists a non-decreasing function f such that the result holds, whenever
$a\leq f(b)$
. Similarly, when we say a result holds for
$0\leq a\ll b,c\ll d\leq 1$
, we mean that there exist non-decreasing functions
$f_1$
and
$f_2$
such that the result holds, whenever
$a\leq f_1(b,c)$
and
$b,c\leq f_2(d)$
. Such hierarchies with more constants are defined in a similar way and are to be read from the right to the left. We will be using the following standard estimates on Turán graphs (for
$n\geq r\geq 2$
):
$$ \begin{align} \frac{r-2}{r-1}{n\choose 2} \leq {\text{ex}}(n, K_r)=t_{r-1}(n) \leq \frac{r-2}{r-1}\cdot \frac{n^2}{2}= \frac{r-2}{r-1}{n\choose 2}+\frac{r-2}{2(r-1)}n \end{align} $$
and
$$ \begin{align} \frac{r-2}{r-1}(n-1)\leq \delta(T_{r-1}(n))\leq \frac{r-2}{r-1}n. \end{align} $$
We shall also use the following two technical lemmas, and we postpone the proofs to Appendix A.
Lemma 2.1 Let
$r\geq 5$
,
$s=\left \lceil \frac {r}{2}\right \rceil $
and
$h\geq {r\choose 2}$
. If
$\ell $
and i are two integers satisfying one of the following statements:
-
(i)
$2\leq \ell \leq s-2$
and
$r-s+1 \leq i\leq r-1$
; or -
(ii)
$\ell = s-1$
and
$r-s+2 \leq i\leq r-1$
,
then
$\frac {2}{r}\big (r-2-\frac {\ell -1}{i-\ell }\big )\big (h-\frac {r(r-2)}{4}+1\big )\geq h-((\ell -1)s+r-i).$
Lemma 2.2 Let
$r\geq 5$
,
$s=\left \lceil \frac {r}{2}\right \rceil $
,
$2\leq \ell \leq s-1$
and
$h\geq {r\choose 2}$
. Then,
$$ \begin{align*}2\frac{r-\ell-1}{r-\ell}\cdot \frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right)\geq h-(\ell-1)s.\end{align*} $$
2.2 Graph packing
A packing of two graphs G and H is a bijection
$\sigma : V(G)\to V(H),$
where
$uv\in E(G)$
implies
$\sigma (u)\sigma (v)\notin E(H)$
. In other words, there is a packing of two graphs G and H if and only if
$G\subseteq \overline {H}$
. We shall use the following result of Sauer and Spencer [Reference Sauer and Spencer29].
Theorem 2.3 [Reference Sauer and Spencer29, Theorem 2]
Let G and H be two graphs with n vertices. If
$e(G)e(H)<{n\choose 2}$
, then there is a packing of G and H.
The following result was conjectured by Milner and Welsh [Reference Milner and Welsh27], and proved by Sauer and Spencer [Reference Sauer and Spencer29] and Bollobás and Eldridge [Reference Bollobás and Eldridge5] independently (see also [Reference Brandt6, Corollary 3.3]).
Theorem 2.4 [Reference Bollobás and Eldridge5, Reference Brandt6, Reference Sauer and Spencer29]
Let G and H be two graphs with n vertices. If
$e(G)+e(H)\leq \frac {3}{2}(n-1)$
, then there is a packing of G and H.
2.3 Existing results for multicolor Turán problems
In this section, we state several existing results from [Reference Chakraborti, Kim, Lee, Liu and Seo7, Reference Keevash, Saks, Sudakov and Verstraëte20] for the use of our proof. The underlying graph of a multigraph H is the simple graph with vertex
$V(H)$
and edge set
$\big \{e\in {V(H)\choose 2}\colon \, w_H(e)\geq 1\big \}$
. The chromatic number of a multigraph is given by the chromatic number of its underlying graph. A multigraph is called r-color-critical if it has chromatic number r, and it has an edge (i.e., a critical edge) whose removal decreases the chromatic number. We say that a simple k-coloring is nested if its colors form a chain under inclusion, i.e., a simply k-colored multigraph with colors
$G_1, \ldots , G_k$
is nested if
$G_{\pi (1)}\subseteq \cdots \subseteq G_{\pi (k)}$
for some permutation
$\pi $
on
$[k]$
. It was shown in [Reference Chakraborti, Kim, Lee, Liu and Seo7, Reference Keevash, Saks, Sudakov and Verstraëte20] that if G is a simply k-colored multicolored-H-free multigraph, then there is a simply k-nested-colored multicolored-H-free multigraph F with
$V(F)=V(G)$
and
$E(F)=E(G)$
. The following lemma reduces the upper range of Conjecture 1.2 to nested multigraphs with high minimum degree. This lemma is in fact a consequence of both [Reference Chakraborti, Kim, Lee, Liu and Seo7, Proposition 3.3] (an analogous idea was also used in the proofs of Theorems 3.1 and 3.2 in [Reference Keevash, Saks, Sudakov and Verstraëte20]) and [Reference Chakraborti, Kim, Lee, Liu and Seo7, Proposition 3.5] (see also [Reference Keevash, Saks, Sudakov and Verstraëte20, Lemma 2.1]).
Lemma 2.5 [Reference Chakraborti, Kim, Lee, Liu and Seo7, Reference Keevash, Saks, Sudakov and Verstraëte20]
Let
$r\geq 3$
,
$k\geq 1$
, and H be an r-color-critical multigraph. Suppose that there exists an
$n_0$
such that for all
$n\geq n_0$
, every n-vertex simply k-nested-colored multicolored-H-free multigraph G with
$e(G)\geq k\cdot t_{r-1}(n)$
and
$\delta (G)\geq k\delta (T_{r-1}(n))$
must be a
$k\cdot T_{r-1}(n)$
. Then, there exists an
$n_1$
such that for all
$n\geq n_1$
, every n-vertex simply k-colored multicolored-H-free multigraph G with
$e(G)\geq k\cdot t_{r-1}(n)$
must be a
$k\cdot T_{r-1}(n)$
.
To show a host multigraph under certain circumstances is
$(r-1)$
-partite, the following family of subgraphs with specified property serves as an intermediate step in our proof.
Definition 2.1 [Reference Chakraborti, Kim, Lee, Liu and Seo7, Definition 3.7]
Let
$k\geq \frac {r-1}{r-2}(h-1)$
, H be an r-color-critical multigraph with h edges, and K be a simply k-colored
$(r-1)$
-partite multigraph with partite sets
$W_1, \ldots , W_{r-1}$
of equal size t. We say that K is H-friendly
Footnote
3
if the multigraph obtained in the following way always contains a multicolored H: add a new vertex v to K and add edges incident to v with multiplicity at most k so that
$\sum _{i\in [r-1]}d_{W_i}(v)\geq (r-2)tk$
and
$d_{W_i}(v)\geq 1$
for all
$i\in [r-1]$
.
The following lemma, proved in [Reference Chakraborti, Kim, Lee, Liu and Seo7] using a stability argument, states that if there exists an H-friendly induced subgraph in a simply k-colored multigraph G with certain properties, then G possesses the desired
$(r-1)$
-partite global structure.
Lemma 2.6 [Reference Chakraborti, Kim, Lee, Liu and Seo7, Lemma 3.8]
Let
$0<\frac {1}{n}\ll \delta \ll \frac {1}{k}, \frac {1}{m}, \frac {1}{t} \leq 1$
,
$r\geq 4$
and
$k\geq \frac {r-1}{r-2}(h-1)$
. Let H be an m-vertex r-color-critical multigraph with h edges, and G be an n-vertex simply k-colored multicolored-H-free multigraph with
$\delta (G)\geq (1-\delta )k\delta (T_{r-1}(n))$
. If G contains a
$t(r-1)$
-vertex H-friendly subgraph as an induced subgraph, then G is
$(r-1)$
-partite.
We will use the following result from [Reference Chakraborti, Kim, Lee, Liu and Seo7] iteratively to find a subset of vertices such that, there are many edges with high multiplicities incident with them. The same idea was also employed in [Reference Keevash, Saks, Sudakov and Verstraëte20] (see, for example, the proof of [Reference Keevash, Saks, Sudakov and Verstraëte20, Theorem 3.2]).
Lemma 2.7 [Reference Chakraborti, Kim, Lee, Liu and Seo7, Proposition 3.4]
Let
$0<\frac {1}{n}\ll \delta \ll \frac {1}{k}, \frac {1}{d}, \frac {1}{t} <1$
. Suppose that G is an n-vertex simply k-colored multigraph with
$\delta (G)\geq (1-\delta )d(n-1)$
, and
$U\subseteq V(G)$
is a vertex subset of size t. Then, there is a vertex
$v\in V(G)\setminus U$
such that
$d_U(v)\geq dt$
.
Given two multigraphs H and G, we say that an injection
$\phi : V(H) \to V(G)$
is an embedding if
$w_G(\phi (u)\phi (v))\geq w_H(uv)$
for all
$uv\in {V(H)\choose 2}$
. For
$e=uv\in {V(H)\choose 2}$
, we also write
$\phi (e)$
for
$\phi (u)\phi (v)$
. The following lemma provides a sufficient condition that guarantees the existence of a multicolored subgraph. An intuitive explanation for this lemma is that we can greedily select colors of edges with respect to the ordering
$(f_1, \ldots , f_t)$
.
Lemma 2.8 [Reference Chakraborti, Kim, Lee, Liu and Seo7, Proposition 3.6]
Let G be a simply k-colored multigraph, H be a multigraph, and
$t=\big |\big \{e\in {V(H)\choose 2}\colon \, w_H(e)\geq 1 \big \}\big |$
. Suppose that there is an embedding
$\phi : V(H) \to V(G)$
. If there is an enumeration
$(f_1, \ldots , f_t)$
of the edges in
$\big \{e\in {V(H)\choose 2}\colon \, w_H(e)\geq 1\big \}$
such that
$w_G(\phi (f_i))\geq \sum _{\ell =1}^{i}w_H(f_{\ell })$
for all
$i \in [t]$
, then
$\phi (H)$
yields a multicolored copy of H in G.
3 Proof sketch of Theorem 1.3
In this section, we supply a proof sketch of Theorem 1.3. In fact, we will prove Theorem 1.3 in a slightly stronger form (Theorem 5.6). To illustrate the sketch of our proof, we need some additional definitions introduced in [Reference Chakraborti, Kim, Lee, Liu and Seo7]. For an r-color-critical multigraph H, we call a proper vertex-coloring c with color classes
$V_1, \ldots , V_r$
a critical coloring if there exists two colors
$i,j$
such that
$e(V_i, V_j)=1$
. Given its critical coloring c, the color-reduced multigraph of H, denoted as
$H_{c}$
, is the multigraph with vertex set
$[r]$
and
$w_{H_c}(ij)=e(V_i,V_j)$
for each
$ij\in {[r]\choose 2}$
. Note that
$H_c$
is an r-vertex r-color-critical multigraph. Intuitively, if we can prove a multicolor Turán-type result for such a multigraph
$H_c$
, then we can deal with the reduced multigraphs obtained by applying the multicolor Regularity Lemma to multicolored-H-free multigraphs, and finally deduce our main result using this intermediate result and the Embedding Lemma.
In our proof, expanding on the stability argument proposed by Chakraborti, Kim, Lee, Liu, and Seo [Reference Chakraborti, Kim, Lee, Liu and Seo7], we introduce a graph packing technique for embedding multigraphs. Our proof consists of two steps as follows:
-
Step I. Establishing the result for r-vertex r-color-critical multigraphs (see Theorem 4.1) via graph packing arguments.
-
Step II. Completing the proof of Theorem 5.6 (for general r-color-critical graphs) via stability arguments.
In Step I, the key is to prove Lemma 4.2, which states that for an r-vertex r-color-critical multigraph H, if a host multigraph with relatively large minimum degree contains no multicolored H, then it must be an
$(r-1)$
-partite multigraph. Once this lemma is proven, we can readily deduce Theorem 4.1. This theorem represents a result that is analogous to Theorem 5.6, but it specifically pertains to r-vertex r-color-critical multigraphs. In the proof of Lemma 4.2, our main task is to find a multicolored copy of H in certain r-vertex multigraph
$F^+$
. The multigraph
$F^+$
contains a subset
$E_1$
of edges with low multiplicities, while the multigraph H contains a subset
$E_2$
of edges with high multiplicities. When embedding H into
$F^+$
, one must embed edges of low multiplicities in H into the edge-set
$E_1$
. To this end, it suffices to show that there is a packing of
$F^+[E_1]$
and
$H[E_2]$
(we may add some isolated vertices if these two graphs have different orders), which we manage to achieve by carefully estimating the multiplicities of the relevant edges.
In Step II, we complete the proof of Theorem 5.6 (and also Theorem 1.3) by a routine application of the stability argument, which in this context was introduced in [Reference Chakraborti, Kim, Lee, Liu and Seo7]. In order to extend the result from r-vertex critical multigraphs to critical graphs with any number of vertices, we apply the multicolor version of Szemerédi’s Regularity Lemma to a multicolored-H-free multigraph, and get a reduced multigraph. By the Embedding Lemma, we argue this reduced multigraph must be multicolored-
$H_c$
-free, where
$H_c$
is an r-vertex r-color-critical multigraph. Finally, we make use of Theorem 4.1 given by Step I to derive the main result of this article.
4 Step I: graph packing of r-vertex multigraphs
In this section, we prove the following result for r-vertex r-color-critical multigraphs.
Theorem 4.1 Let
$r\geq 5$
and H be an r-vertex r-color-critical multigraph with h edges. If n is sufficiently large and
$$ \begin{align*}k> \max\left\{\frac{r-1}{r-2}(h-1), 2\frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right)\right\},\end{align*} $$
then
${\text {ex}}_k(n, H)=k\cdot t_{r-1}(n)$
, and the unique n-vertex k-color extremal multigraph of H consists of k colors all of which are identical copies of
$T_{r-1}(n)$
.
The following lemma is crucial in the proofs of Theorem 4.1 and a technical lemma in Section 5 (i.e., Lemma 5.2).
Lemma 4.2 Let
$r\geq 5$
,
$k>\max \big \{\frac {r-1}{r-2}(h-1), 2\frac {r-1}{r}\big (h-\frac {r(r-2)}{4}+1\big )\big \}$
and
$0 \ll \frac {1}{n} \ll \delta \ll \frac {1}{k}$
. Let H be an r-vertex r-color-critical multigraph with h edges, and G be an n-vertex simply k-colored multicolored-H-free multigraph with
$\delta (G)\geq (1-\delta )k\delta (T_{r-1}(n))$
. Then, G is
$(r-1)$
-partite.
Proof of Theorem 4.1 (assuming Lemma 4.2)
Let G be an n-vertex simply k-colored multicolored-H-free multigraph with
$e(G)\geq k\cdot t_{r-1}(n)$
. We shall show that
$G=k\cdot T_{r-1}(n)$
. By Lemma 2.5, we may assume that
$\delta (G)\geq k\delta (T_{r-1}(n))$
. By Lemma 4.2, G is
$(r-1)$
-partite. Since
$T_{r-1}(n)$
is the unique
$(r-1)$
-partite graph on n vertices with
$t_{r-1}(n)$
edges, we have
$e(G)\leq k\cdot t_{r-1}(n)$
. Thus,
$e(G)= k\cdot t_{r-1}(n)$
and
$G=k\cdot T_{r-1}(n)$
. The proof is complete.
In the proof of Lemma 4.2, we will repeatedly use the following simple observation.
Observation 4.3 Let H be an r-vertex r-color-critical multigraph with h edges. Then:
-
(i)
$w_H(e)\geq 1$
for every
$e\in {V(H)\choose 2}$
; -
(ii)
$w_H(E)\leq h-\left ({r\choose 2}-|E|\right )$
for any
$E\subseteq {V(H)\choose 2}$
; and -
(iii)
$d_H(v)\leq h-{r-1 \choose 2}$
for any vertex
$v\in V(H)$
.
We now devote the rest of this section to the proof of Lemma 4.2.
Proof of Lemma 4.2
Since
$\delta (G)\geq (1-\delta )k\delta (T_{r-1}(n))$
, we have
$\delta (G)\geq (1-\delta )k\frac {r-2}{r-1}(n-1)$
by Inequality (2.2). Thus,
$e(G)\geq \frac {1}{2}n\delta (G)\geq \frac {1}{2}n(1-\delta )k\frac {r-2}{r-1}(n-1)=(1-\delta )k \frac {r-2}{r-1}\binom {n}{2}.$
Since H is an r-vertex r-color-critical multigraph, we have
$h\geq {r\choose 2}$
by Observation 4.3(i). Let 
. Let
$K_{r-s}^{(h-r(r-2)/4+1)}$
be a complete multigraph on
$r-s$
vertices in which every edge has multiplicity at least
$h-\frac {r(r-2)}{4}+1$
.
Claim 1
G contains
$K_{r-s}^{(h-r(r-2)/4+1)}$
as a subgraph.
Proof Let 
and 
. It suffices to show that
$x>{\text {ex}}(n,K_{r-s})$
. Note that the multiplicity of an edge is a nonnegative integer, so for any
$e\in {V(G)\choose 2}\setminus X$
, we have
$w_G(e)\leq h-\frac {r(r-2)}{4}+1-\frac {1}{4}=h-\frac {r^2-2r-3}{4}$
. Then,
$$ \begin{align*} (1-\delta)k \frac{r-2}{r-1}\binom{n}{2}\leq e(G)\leq kx+\left(h-\frac{r^2-2r-3}{4}\right)\left(\binom{n}{2}-x\right), \end{align*} $$
and thus
$$ \begin{align*} x\geq \frac{1}{k-(h-(r^2-2r-3)/4)}\left((1-\delta)k\frac{r-2}{r-1}-\left(h-\frac{r^2-2r-3}{4}\right)\right)\binom{n}{2}. \end{align*} $$
Since
$k>2\frac {r-1}{r}\left (h-\frac {r(r-2)}{4}+1\right )$
,
$0 \ll \frac {1}{n} \ll \delta \ll \frac {1}{k}$
and
$s=\left \lceil \frac {r}{2}\right \rceil \geq \frac {r}{2}$
, we have
$$ \begin{align*} \begin{aligned} &~(1-\delta)k\frac{r-2}{r-1}-\left(h-\frac{r^2-2r-3}{4}\right)-\left(k-\left(h-\frac{r^2-2r-3}{4}\right)\right)\frac{r-s-2}{r-s-1}\\ =&~\frac{s}{(r-1)(r-s-1)}k-\delta\frac{r-2}{r-1}k-\frac{1}{r-s-1}\left(h-\frac{r^2-2r-3}{4}\right)\\> &~\frac{r/2}{(r-1)(r-s-1)}2\frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right)- \delta\frac{r-2}{r-1}k- \frac{1}{r-s-1}\left(h-\frac{r^2-2r-3}{4}\right)\\ =&~\frac{1}{4(r-s-1)}-\delta\frac{r-2}{r-1}k ~\geq \frac{1}{5(r-s-1)}. \end{aligned} \end{align*} $$
Thus,
$x\geq \frac {r-s-2}{r-s-1}\binom {n}{2}+\frac {1}{5(r-s-1)(k-(h-(r^2-2r-3)/4))}{n\choose 2}$
. Note that
$r-s\geq r-\frac {r+1}{2}\geq 2$
since
$r\geq 5$
. By Inequality (2.1), we have
${\text {ex}}(n,K_{r-s})=\frac {r-s-2}{r-s-1}\binom {n}{2}+O(n)$
. Then,
$x>{\text {ex}}(n,K_{r-s})$
. The result follows.
By Claim 1, we may assume that K is a copy of
$K_{r-s}^{(h-r(r-2)/4+1)}$
in G with
$V(K)=\{v_1, v_2, \ldots , v_{r-s}\}$
. Recall that
$\delta (G)\geq (1-\delta )k\frac {r-2}{r-1}(n-1)$
. Using Lemma 2.7 iteratively, we can find vertices
$v_{r-s+1}, \ldots , v_{r-1}\in V(G)\setminus V(K)$
such that for each
$r-s+1 \leq i \leq r-1$
, we have
$\sum _{j\in [i-1]} w_G(v_iv_j)\geq k\frac {r-2}{r-1}(i-1).$
Since
$k>\max \big \{\frac {r-1}{r-2}(h-1), 2\frac {r-1}{r}\big (h-\frac {r(r-2)}{4}+1\big )\big \}$
, for each
$r-s+1\leq i\leq r-1$
and
$2\leq \ell \leq i-2$
, we have
$$ \begin{align} ~&~\min \{w_G(v_iv_j)\colon\, 1\leq j\leq i-1\} \nonumber\\ \geq &~\sum\nolimits_{j\in[i-1]}w_G(v_iv_j)-(i-2)k ~\geq k\frac{r-2}{r-1}(i-1)-(i-2)k ~= k\frac{r-i}{r-1} \nonumber\\>&~2\frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right)\frac{r-i}{r-1} ~= (r-i)\frac{2}{r}\left(h-\frac{r(r-2)}{4}+1\right), \end{align} $$
$$ \begin{align} ~&~\min\nolimits_2\{w_G(v_iv_j)\colon\, 1\leq j\leq i-1\} \nonumber\\ \geq &~\frac{1}{2}\left(\sum\nolimits_{j\in[i-1]}w_G(v_iv_j)-(i-3)k\right) ~\geq \frac{1}{2}\left(k\frac{r-2}{r-1}(i-1)-(i-3)k\right) \nonumber\\ = &~\frac{1}{2}k\frac{2r-i-1}{r-1} ~> \frac{2r-i-1}{r}\left(h-\frac{r(r-2)}{4}+1\right) \nonumber\\ \geq &~\frac{2r-(r-1)-1}{r}\left(h-\frac{r(r-2)}{4}+1\right) ~= h-\frac{r(r-2)}{4}+1, \end{align} $$
$$ \begin{align} ~&~\max\{w_G(v_iv_j)\colon\, 1\leq j\leq i-1\} \nonumber\\ \geq &~\frac{1}{i-1}\sum\nolimits_{j\in[i-1]}w_G(v_iv_j) ~\geq \frac{1}{i-1}k\frac{r-2}{r-1}(i-1) ~> \frac{r-1}{r-2}(h-1)\frac{r-2}{r-1} ~= h-1, \end{align} $$
and
$$ \begin{align} ~&~\max\nolimits_{\ell}\{w_G(v_iv_j)\colon\, 1\leq j\leq i-1\}\nonumber\\ \geq &~\frac{1}{i-\ell}\left(\sum\nolimits_{j\in[i-1]}w_G(v_iv_j)-(\ell-1)k\right) ~\geq \frac{1}{i-\ell}\left(k\frac{r-2}{r-1}(i-1)-(\ell-1)k\right) \nonumber\\ = &~k\frac{1}{i-\ell}\cdot \frac{(r-2)(i-1)-(r-1)(\ell-1)}{r-1} ~= k\left(\frac{r-2}{r-1}-\frac{\ell-1}{(r-1)(i-\ell)}\right) \nonumber\\> &~2\frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right)\left(\frac{r-2}{r-1}-\frac{\ell-1}{(r-1)(i-\ell)}\right) \nonumber\\ = &~\frac{2}{r}\left(r-2-\frac{\ell-1}{i-\ell}\right)\left(h-\frac{r(r-2)}{4}+1\right). \end{align} $$
By Inequality (4.4) and Lemma 2.1, we have
$$ \begin{align} \max\nolimits_{\ell}\{w_G(v_iv_j)\colon\, 1\leq j\leq i-1\}\geq h-((\ell-1)s+r-i), \end{align} $$
when (i)
$2\leq \ell \leq s-2$
and
$r-s+1\leq i\leq r-1$
, or (ii)
$\ell =s-1$
and
$r-s+2\leq i\leq r-1$
.
Let 
. The remainder of the proof is devoted to showing that
$F$
is
$H$
-friendly, which together with Lemma 2.6 implies that G is
$(r-1)$
-partite. Let
$F^{+}$
be the multigraph obtained by adding a new vertex
$v_r$
to F and adding edges incident to
$v_r$
of multiplicity at most k such that
$\sum _{i\in [r-1]}w_{F^+}(v_rv_i)\geq (r-2)k$
and
$w_{F^+}(v_rv_i)\geq 1$
for all
$i\in [r-1]$
. It suffices to show that
$F^{+}$
contains a multicolored copy of H. Note that
$\min \{w_{F^+}(v_rv_i)\colon \, 1\leq i\leq r-1\}\geq 1.$
Since
$r\geq 5$
and
$k>\max \big \{\frac {r-1}{r-2}(h-1), 2\frac {r-1}{r}\big (h-\frac {r(r-2)}{4}+1\big )\big \}$
, we have
$$ \begin{align} ~&~\min\nolimits_2\{w_{F^+}(v_rv_i)\colon\, 1\leq i\leq r-1\} \nonumber\\ \geq &~\frac{1}{2}\left(\sum\nolimits_{i\in[r-1]}w_{F^+}(v_rv_i)-(r-3)k\right) ~\geq \frac{1}{2}((r-2)k-(r-3)k) \nonumber\\ = &~\frac{k}{2} ~> \frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right), \end{align} $$
$$ \begin{align} ~&~\min\nolimits_3\{w_{F^+}(v_rv_i)\colon\, 1\leq i\leq r-1\} \nonumber\\ \geq &~\frac{1}{3}\left(\sum\nolimits_{i\in[r-1]}w_{F^+}(v_rv_i)-(r-4)k\right) ~\geq \frac{1}{3}((r-2)k-(r-4)k) \nonumber\\ = &~\frac{2}{3}k ~> \frac{4}{3}\frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right) ~> h-\frac{r(r-2)}{4}+1, \end{align} $$
$$ \begin{align} ~&~\max\{w_{F^+}(v_rv_i)\colon\,1\leq i\leq r-1\} \nonumber\\ \geq &~\frac{1}{r-1}\sum\nolimits_{i\in[r-1]}w_{F^+}(v_rv_i) ~\geq \frac{r-2}{r-1}k ~> \frac{r-2}{r-1}\cdot \frac{r-1}{r-2}(h-1) =~h-1, \end{align} $$
and for
$2\leq \ell \leq s-1$
,
$$ \begin{align} ~&~\max\nolimits_{\ell}\{w_{F^+}(v_rv_i)\colon\, 1\leq i\leq r-1\}\nonumber\\ \geq &~\frac{1}{r-\ell}\left(\sum\nolimits_{i\in[r-1]}w_{F^+}(v_rv_i)-(\ell-1)k\right) ~\geq \frac{1}{r-\ell}((r-2)k-(\ell-1)k) \nonumber\\ = &~\frac{r-\ell-1}{r-\ell}k ~> 2\frac{r-\ell-1}{r-\ell}\cdot \frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right). \end{align} $$
Since the multiplicity of each edge is an integer, Inequality (4.8) implies that
$$ \begin{align} \max\{w_{F^+}(v_rv_i)\colon\, 1\leq i\leq r-1\}\geq h. \end{align} $$
Moreover, recall that
$h\geq {r\choose 2}$
, so by Inequality (4.9) and Lemma 2.2, we have
$$ \begin{align} \max\nolimits_{\ell}\{w_{F^+}(v_rv_i)\colon\, 1\leq i\leq r-1\}\geq h-(\ell-1)s, \end{align} $$
when
$2\leq \ell \leq s-1$
.
For each
$i\in [s]$
, let
$e_i$
be an edge in
$\{v_{r-i+1}v_j\colon \, 1\leq j\leq r-i\}$
with
$w_{F^{+}}(e_i)=\min \{w_{F^{+}}(v_{r-i+1}v_j)\colon \, 1\leq j\leq r-i\}$
(if there are more than one choice for
$e_i$
, we choose an arbitrary one). Then,
$w_{F^+}(e_1)\geq 1$
and
$$ \begin{align} w_{F^+}(e_i)\geq (i-1)\frac{2}{r}\left(h-\frac{r(r-2)}{4}+1\right), \end{align} $$
for
$2\leq i\leq s$
by Inequality (4.1). Let T be the simple graph induced by the set of edges
$\{e_1, \ldots , e_s\}$
. Note that for each
$i\in [s-1]$
,
$e_i$
has at most one end-vertex in
$T[\{e_{i+1}, \ldots , e_{s}\}]$
. Moreover, T is a forest on at most r vertices and T has s edges. Let
$e_{s+1}$
be an edge in
$\{v_rv_j \colon \, 1\leq j\leq r-1\}$
with
$w_{F^+}(e_{s+1})=\min _2\{w_{F^+}(v_rv_j)\colon \, 1\leq j\leq r-1\}$
(if there are more than one choice for
$e_{s+1}$
, we choose an arbitrary one, but it must be different from
$e_1$
). Let
$T^+$
be the simple graph induced by edges
$\{e_1, \ldots , e_s, e_{s+1}\}$
. In other words,
$T^{+}$
is the graph obtained from T by adding the edge
$e_{s+1}$
and its end-vertices (note that some of these two vertices may already be in T, and we do not add such vertices repeatedly).
Claim 2 There is an ordering
$e_{s+2}, e_{s+3}, \ldots , e_{{r\choose 2}}$
of the edges in
${V(F^{+})\choose 2}\setminus E(T^{+})$
such that for each
$j\in \{s+2, s+3, \ldots , {r\choose 2}\}$
, we have
$w_{F^{+}}(e_j)\geq h-\big ({r\choose 2}-j\big )$
.
Proof For each
$r-s+1\leq i\leq r$
, denote
$\{v_iv_{j}\colon \, 1\leq j\leq i-1\}$
by
$\{e_{i,1}, \ldots , e_{i,i-1}\}$
with
$w_{F^+}(e_{i,1})\geq \cdots \geq w_{F^+}(e_{i,i-1})$
. Then, for each
$1\leq \ell \leq i-1$
, we have
$w_{F^+}(e_{i,\ell })=\max _{\ell }\{w(v_iv_j)\colon \, 1\leq j\leq i-1\}$
. We now define the edges
$e_{s+2}, e_{s+3}, \ldots , e_{{r\choose 2}}$
. Let
$e_{{r\choose 2}}, e_{{r\choose 2}-1}, \ldots , e_{{r\choose 2}-s(s-2)+1}$
be the edges
$$ \begin{align*}e_{r,1}, e_{r-1,1}, \ldots, e_{r-s+1,1}, ~ e_{r,2}, e_{r-1, 2}, \ldots, e_{r-s+1,2}, ~ \ldots, ~ e_{r,s-2}, e_{r-1,s-2}, \ldots, e_{r-s+1,s-2},\end{align*} $$
respectively. Let
$e_{{r\choose 2}-s(s-2)}, \ldots , e_{{r\choose 2}-s(s-1)+2}$
be the edges
$$ \begin{align*}e_{r,s-1}, e_{r-1,s-1}, \ldots, e_{r-s+2,s-1},\end{align*} $$
respectively. Let
$e_{{r\choose 2}-s(s-1)+1}, \ldots , e_{s+2}$
be an arbitrary ordering of the remaining edges in
${V(F^{+})\choose 2}\setminus E(T^{+})$
.
By Inequalities (4.3) and (4.10), we have
$w_{F^+}(e_j)\geq h-\left ({r\choose 2}-j\right )$
for
${r\choose 2}-s+1\leq j\leq {r\choose 2}.$
For
$s+2\leq j\leq {r\choose 2}-s(s-1)+1$
, we have
$h-\left ({r\choose 2}-j\right )\leq h-s(s-1)+1\leq h-\frac {r(r-2)}{4}+1$
. By Inequalities (4.2) and (4.7) and since
$F^+\{v_1,\ldots ,v_{r-s}\}$
is a copy of
$K_{r-s}^{(h-r(r-2)/4+1)}$
, we have
$w_{F^+}(e_j)\geq h-\left ({r\choose 2}-j\right )$
for
$s+2\leq j\leq {r\choose 2}-s(s-1)+1$
.
Finally, we consider the case
${r\choose 2}-s(s-1)+2\leq j\leq {r\choose 2}-s$
. Note that for each
$r-s+1 \leq i\leq r$
and
$2\leq \ell \leq s-2$
, we have
$e_{i,\ell }=e_{{r\choose 2}-((\ell -1)s+(r+1-i))+1}=e_{{r\choose 2}-((\ell -1)s+r-i)},$
and for each
$r-s+2 \leq i\leq r$
, we have
$e_{i,s-1}=e_{{r\choose 2}-(s(s-2)+(r+1-i))+1}=e_{{r\choose 2}-(s(s-2)+r-i)}.$
Hence, it suffices to show that
$w_{F^+}(e_{i,\ell })\geq h-((\ell -1)s+r-i)$
when
$r-s+1 \leq i\leq r$
and
$2\leq \ell \leq s-2$
, and
$w_{F^+}(e_{i,s-1})\geq h-(s(s-2)+r-i)$
when
$r-s+2 \leq i\leq r$
. This is indeed true by Inequalities (4.5) and (4.11). This completes the proof of Claim 2.
Let
$e_{s+2}, e_{s+3}, \ldots , e_{{r\choose 2}}$
be the ordering of edges in
${V(F^{+})\choose 2}\setminus E(T^{+})$
obtained by Claim 2. Combining with Observation 4.3(ii), for any
$j\in \{s+2, s+3, \ldots , {r\choose 2}\}$
and any
$E\subseteq {V(H)\choose 2}$
with
$|E|=j$
, we have
$$ \begin{align} w_{F^{+}}(e_j)\geq h-\left({r\choose 2}-j\right)\geq w_H(E). \end{align} $$
The remainder of the proof focuses on showing that there exist edges
$f_1, \ldots, f_{s+1}\in {V(H)\choose 2}$
such that:
-
(i)
$H[\{f_1, \ldots , f_{s+1}\}]$
can be embedded into
$T^+$
in which
$f_i$
is embedded into
$e_i$
for each
$i\in [s+1]$
; and -
(ii)
$w_{F^{+}}(e_i)\geq \sum _{j=1}^{i}w_H(f_j)$
for each
$i\in [s+1]$
.
This together with Inequality (4.13) and Lemma 2.8 implies that
$F^+$
contains a multicolored copy of H, and thus F is H-friendly. We divide the rest of the proof into two cases based on the value of
$w_{F^+}(e_1)$
. Recall that
$w_{F^+}(e_1)= \min \{w_{F^+}(v_rv_i)\colon \, 1\leq i\leq r-1\}\geq 1$
.
Case 1.
$w_{F^+}(e_1)> \frac {r-2}{r}\big (h-\frac {r(r-2)}{4}+1\big ).$
By the assumption of Case 1 and Inequalities (4.6) and (4.12), we have
$w_{F^+}(e_1)\geq \frac {r-2}{r}\big (h-\frac {r(r-2)}{4}+1\big ), w_{F^+}(e_{s+1})\geq \frac {r-1}{r}\big (h-\frac {r(r-2)}{4}+1\big ),$
and
$w_{F^+}(e_j)\geq (j-1)\frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )$
for
$j\in \{2, \ldots , s\}$
. We use
$e_1', e_2', \ldots , e_{{r\choose 2}}'$
to denote the edges in
${V(F^{+})\choose 2}$
with 
for
$i\in [s-2]$
, 
, and 
for
$i\in \{s, s+1, \ldots , {r\choose 2}\}$
. Then,
$$ \begin{align} w_{F^+}(e_i')\geq \begin{cases} i\frac{2}{r}\big(h-\frac{r(r-2)}{4}+1\big) & \text{if }i\in [s-2],\\ \frac{r-2}{r}\big(h-\frac{r(r-2)}{4}+1\big) & \text{if }i=s-1,\\ \left(\left\lceil\frac{r}{2}\right\rceil-1\right)\frac{2}{r}\big(h-\frac{r(r-2)}{4}+1\big) & \text{if }i=s,\\ \frac{r-1}{r}\big(h-\frac{r(r-2)}{4}+1\big) & \text{if }i=s+1. \end{cases} \end{align} $$
Let
$f^{\prime }_1, f^{\prime }_2, \ldots , f^{\prime }_{{r\choose 2}}$
be an ordering of edges in
${V(H)\choose 2}$
with
$w_H(f^{\prime }_1)\geq w_H(f^{\prime }_2)\geq \cdots \geq w_H\big (f^{\prime }_{{r\choose 2}}\big )$
. For each
$j\in [s+1]$
, let 
Claim 3 For each
$j\in [s+1]$
, we have
$h_j\leq \frac {j}{s+j-1}\big (h-\frac {r(r-2)}{4}+1\big ).$
Proof We shall show that
$h_j\leq \frac {j}{s+j-1}\big (h-\big ({r\choose 2}-(s+j-1)\big )\big )$
, which implies the claim since
${r\choose 2}-(s+j-1)\geq {r\choose 2}-2s\geq {r\choose 2}-(r+1)\geq \frac {r(r-2)}{4}-1$
. Suppose for a contradiction that
$h_j> \frac {j}{s+j-1}\big (h-\big ({r\choose 2}-(s+j-1)\big )\big ).$
Then,
$w_{H}(f^{\prime }_s)\geq \frac {1}{j}h_j> \frac {1}{s+j-1}\big (h-\big ({r\choose 2}-(s+j-1)\big )\big )$
and thus
$w_H(f^{\prime }_1)\geq \cdots \geq w_H(f^{\prime }_{s-1})\geq w_{H}(f^{\prime }_s)> \frac {1}{s+j-1}\big (h-\big ({r\choose 2}-(s+j-1)\big )\big ).$
Combining with Observation 4.3(i), we have
$$ \begin{align*} e(H)= &~\sum\nolimits_{i=1}^{s-1}w_{H}(f^{\prime}_i) + \sum\nolimits_{i=s}^{s+j-1}w_{H}(f^{\prime}_i) + \sum\nolimits_{i=s+j}^{{r\choose 2}}w_{H}(f^{\prime}_i) \\> &~ (s-1)\frac{1}{s+j-1}\left(h-\left({r\choose 2}-(s+j-1)\right)\right) \\ ~&~~+ \frac{j}{s+j-1}\left(h-\left({r\choose 2}-(s+j-1)\right)\right) + {r\choose 2}-(s+j-1) \\ = &~ h, \end{align*} $$
a contradiction. The result follows.
Claim 4 For each
$j\in [s+1]$
, we have
$w_{F^+}(e_j')\geq h_j.$
Proof By Claim 3, it suffices to show that
$w_{F^+}(e_j')/\big (h-\frac {r(r-2)}{4}+1\big )\geq \frac {j}{s+j-1}$
for each
$j\in [s+1].$
We shall use the lower bound on
$w_{F^+}(e_j')$
given by Inequality (4.14). For
$j\in [s-2]$
, we have
$j\frac {2}{r}-\frac {j}{s+j-1}\geq j\big (\frac {2}{r}-\frac {1}{r/2+1-1}\big )= 0.$
For
$j=s-1$
, we have
$\frac {r-2}{r}-\frac {j}{s+j-1}= \frac {r-2}{r}-\frac {1}{2}> 0.$
For
$j=s$
, if
$r\geq 5$
is odd, then
$\left (\left \lceil \frac {r}{2}\right \rceil -1\right )\frac {2}{r}-\frac {j}{s+j-1}= \frac {r-1}{r}-\frac {r+1}{2r}>0$
; if
$r\geq 6$
is even, then
$\left (\left \lceil \frac {r}{2}\right \rceil -1\right )\frac {2}{r}-\frac {j}{s+j-1}= \frac {r-2}{r}-\frac {r}{2(r-1)}> 0$
. For
$j=s+1$
, we have
$\frac {r-1}{r}-\frac {j}{s+j-1}= \frac {r-1}{r}-\frac {s+1}{2s}\geq \frac {r-1}{r}-\frac {1}{2}-\frac {1}{r}> 0.$
The result follows.
Let
$H'$
be the simple graph with
$V(H')=V(H)$
and
$E(H')=\{f^{\prime }_1, f^{\prime }_2, \ldots , f^{\prime }_{s-1}\}$
. Recall that
$T^+$
is an
$(s+1)$
-edge graph on at most r vertices. Let
$T^{++}$
be the graph obtained from
$T^+$
by adding
$r-|V(T^+)|$
isolated vertices. Since
$e(T^{++})+e(H')=2s\leq r+1 \leq \frac {3}{2}(r-1)$
, there is a packing of
$T^{++}$
and
$H'$
by Theorem 2.4. Hence, there exist
$s+1$
edges
$f^{\prime }_{i_1}, \ldots , f^{\prime }_{i_{s+1}}\in {V(H)\choose 2}$
and an embedding
$\phi : V(H) \to V(F^+)$
such that:
-
(i)
$f^{\prime }_{i_1}, \ldots , f^{\prime }_{i_{s+1}}\in \big \{f^{\prime }_s, \ldots , f^{\prime }_{{r\choose 2}}\big \}$
; and -
(ii)
$\phi (f^{\prime }_{i_j})=e_j'$
for each
$j\in [s+1]$
.
Moreover, by Claim 4, we have
$$ \begin{align*}w_{F^+}(e_j')\geq h_j=\sum\nolimits_{\ell=s}^{s+j-1}w_{H}(f^{\prime}_{\ell}) \geq \sum\nolimits_{\ell=1}^{j}w_{H}(f^{\prime}_{i_{\ell}}),\end{align*} $$
for each
$j\in [s+1]$
. For each
$1\leq j\leq {r\choose 2}$
, let 
. Combining with Inequality (4.13), we have
$w_{F^{+}}(e_j')\geq \sum _{\ell =1}^{j}w_H(f^{\prime \prime }_{\ell })$
for each
$1\leq j\leq {r\choose 2}$
. By Lemma 2.8, there is a multicolored copy of H in
$F^+$
. Thus, F is H-friendly. By Lemma 2.6, G is
$(r-1)$
-partite. This completes the proof of Case 1.
Case 2.
$1\leq w_{F^+}(e_1)\leq \frac {r-2}{r}\big (h-\frac {r(r-2)}{4}+1\big ).$
In this case, we have
$$ \begin{align} w_{F^+}(e_{s+1}) = &~\min\nolimits_2\{w(v_rv_i)\colon\, 1\leq i\leq r-1\} \nonumber\\ \geq &~\sum\nolimits_{i\in[r-1]}w(v_rv_i)-(r-3)k-w_{F^+}(e_1) \nonumber\\ \geq &~(r-2)k-(r-3)k-\frac{r-2}{r}\left(h-\frac{r(r-2)}{4}+1\right) \nonumber\\> &~2\frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right)-\frac{r-2}{r}\left(h-\frac{r(r-2)}{4}+1\right) \nonumber\\ = &~h-\frac{r(r-2)}{4}+1 ~\geq h-\left({r\choose 2}-(s+1)\right). \end{align} $$
Combining this with Observation 4.3 and Inequality (4.13), we have
$w_{F^{+}}(e_j)\geq w_H(E)$
for any
$j\in \{s+1, s+2, \ldots , {r\choose 2}\}$
and any
$E\subseteq {V(H)\choose 2}$
with
$|E|=j$
.
Recall that T is a forest with s edges. Let
$T_1$
be the connected component of T containing the edge
$e_1$
. Let 
. Then,
$0\leq m\leq s-1$
. Let
$\{e_{i_1}, \ldots , e_{i_m}, e_1\}$
be the edge set of
$T_1$
. Since
$T_1$
is a tree, we may assume that for each
$j\in [m]$
, the edge
$e_{i_j}$
has exactly one end-vertex in
$T_1[\{e_{i_{j+1}}, \ldots , e_{i_m}, e_{1}\}].$
Let
$e_1=v_rv_{q}$
, where
$q\in [r-1]$
. By the definition of T, if an edge is adjacent to
$e_1$
in T, then this edge must be incident with
$v_q$
. We may further assume that
$\{e_{i_{m'}}, \ldots , e_{i_m}\}$
is the set of all edges adjacent to
$e_{1}$
in
$T_1$
. Then,
$\{e_{i_{m'}}, \ldots , e_{i_m}\}$
forms a star with center
$v_q$
.
Claim 5 If
$m'=1$
and
$m=s-1$
, then G is
$(r-1)$
-partite.
Proof If
$m'=1$
and
$m=s-1$
, then
$T=T_1$
is a star with center
$v_q$
. Let
$V(H)=\{u_1, u_2, \ldots , u_r\}$
and 
be a critical edge of H. So
$w_H(f_1)=1$
. Without loss of generality, we may assume that
$d_H(u_2)\leq d_H(u_1)$
and
$w_H(u_2u_3)\leq \cdots \leq w_H(u_2u_r)$
. Then, by Observation 4.3(i), we have
$$ \begin{align*}\sum\nolimits_{i=3}^{r}w_H(u_2u_i) & \leq \frac{1}{2}\left(h-\sum\nolimits_{e\in {V(H)\setminus \{u_1, u_2\}\choose 2}}w_H(e)-w_H(u_1u_2)\right) \\ &\leq \frac{1}{2}\left(h-{r-2 \choose 2}-1\right),\end{align*} $$
and moreover, for each
$2\leq j\leq s,$
we have
$$ \begin{align*}\sum\nolimits_{i=3}^{j+1}w_H(u_2u_{i})\leq \frac{j-1}{r-2}\sum\nolimits_{i=3}^{r}w_H(u_2u_i)\leq \frac{j-1}{r-2}\cdot \frac{1}{2}\left(h-{r-2 \choose 2}-1\right).\end{align*} $$
For each
$2\leq j\leq s$
, let 
, so
$$ \begin{align*}\sum\nolimits_{i=1}^{j}w_H(f_i) &= 1+\sum\nolimits_{i=2}^{j}w_H(u_2u_{i+1}) \\ &=1+\sum\nolimits_{i=3}^{j+1}w_H(u_2u_{i}) \\ &\leq 1+\frac{j-1}{r-2}\cdot \frac{1}{2}\left(h-{r-2 \choose 2}-1\right).\end{align*} $$
Recall that
$r\geq 5$
and
$h\geq {r\choose 2}$
. Then, for
$j\geq 2$
, we have
$$ \begin{align*} ~&~(j-1)\frac{2}{r}\left(h-\frac{r(r-2)}{4}+1\right)- 1-\frac{j-1}{r-2}\cdot \frac{1}{2}\left(h-{r-2 \choose 2}-1\right) \\ \geq &~(j-1)\frac{2}{r}\left({r\choose 2}-\frac{r(r-2)}{4}+1\right)- 1-\frac{j-1}{r-2}\cdot \frac{1}{2}\left({r\choose 2}-{r-2 \choose 2}-1\right) \\ = &~(j-1)\frac{2}{r}\left(\frac{r^2}{4}+1\right)-1-\frac{j-1}{2(r-2)}(2r-4) \\ = &~\frac{r}{2}(j-1)+\frac{2}{r}(j-1)-j ~> \frac{r}{2}(j-1)-j ~\geq \frac{5}{2}(j-1)-j ~= \frac{3}{2}j-\frac{5}{2} ~> 0, \end{align*} $$
where the first inequality holds since
$h\geq {r\choose 2}$
and
$(j-1)\frac {2}{r}-\frac {j-1}{r-2}\cdot \frac {1}{2}=(j-1)\big (\frac {2}{r}-\frac {1}{2(r-2)}\big )>0.$
Thus,
$\sum _{i=1}^{j}w_H(f_i)< (j-1)\frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )$
for
$2\leq j\leq s$
. This together with Inequality (4.12) implies that
$w_{F^+}(e_j)\geq \sum _{i=1}^{j}w_H(f_i)$
for each
$j\in [s]$
. Let
$\phi : V(H) \to V(F^+)$
be an embedding with
$\phi (f_j)=e_j$
for each
$j\in [s]$
. Combining with Observation 4.3, Inequalities (4.13), (4.15), and Lemma 2.8, we can deduce that
$F^+$
contains a multicolored copy of H. Thus, F is H-friendly. By Lemma 2.6, G is
$(r-1)$
-partite. This completes the proof of Claim 5.
By Claim 5, we may assume that either
$m'\neq 1$
or
$m\neq s-1$
in the following arguments.
Claim 6
H contains a subgraph
$H_1$
such that:
-
(i) the underlying graph of
$H_1$
is
$T_1$
; -
(ii) the edge corresponding to
$e_1$
is a critical edge of H; and -
(iii) each edge of
$H_1$
has multiplicity at most
$\frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )-1$
in H.
Proof If
$m=0$
, then
$T_1$
consists of the single edge
$e_1$
. In this case, the result holds clearly since H contains a critical edge. In the following, we may assume that
$m\geq 1$
. Let 
be a critical edge of H. Without loss of generality, we may assume that
$d_H(u_2)\leq d_H(u_1)$
. Then,
$u_2$
has a neighbor
$u_3\in V(H)\setminus \{u_1,u_2\}$
with
$w_H(u_2u_3)\leq \frac {1}{r-2}\cdot \frac {1}{2}\left (h-{r-2 \choose 2}-1\right )\leq \frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )-1.$
Let 
Assume that we have found
$f_{i_{\ell }}, \ldots , f_{i_m}, f_1\in {V(H)\choose 2}$
for some
$2\leq \ell \leq m$
such that for each
$j\in \{\ell , \ldots , m\}$
:
-
(i) the edge
$f_{i_j}$
has multiplicity at most
$\frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )-1$
; and -
(ii) the underlying graph of
is isomorphic to
$T_1[\{e_{i_j}, \ldots , e_{i_m}, e_1\}]$
.
is isomorphic to 
We shall find an edge
$f_{i_{\ell -1}}\in {V(H)\choose 2}$
with
$w_H(f_{i_{\ell -1}})\leq \frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )-1$
such that
$H[\{f_{i_{\ell -1}}, \ldots , f_{i_m}, f_1\}]$
is isomorphic to
$T_1[\{e_{i_{\ell -1}}, \ldots , e_{i_m}, e_1\}]$
.
Recall that
$e_{i_{\ell -1}}$
has exactly one end-vertex in
$T_1[\{e_{i_{\ell }}, \ldots , e_{i_m}, e_1\}]$
, say vertex w. Let
$w'$
be the vertex in
$H_{(\ell )}$
corresponding to w. Note that
$|V(H_{(\ell )})|=|E(H_{(\ell )})|+1= m-\ell +3$
. Let
$w"\in V(H)\setminus V(H_{(\ell )})$
with
$w_H(w'w")=\min _{x\in V(H)\setminus V(H_{(\ell )})}w_H(w'x).$
By Observation 4.3(i) and (iii), we have
$$ \begin{align*}w_H(w'w") &\leq \frac{d_H(w')-d_{H_{(\ell)}}(w')}{r-|V(H_{(\ell)})|} \\ &\leq \frac{h-{r-1 \choose 2}-(|V(H_{(\ell)})|-1)}{r-|V(H_{(\ell)})|} = 1+\frac{h-{r \choose 2}}{r-(m-\ell+3)}.\end{align*} $$
If
$r\geq 6$
is even, then
$$ \begin{align*}w_H(w'w")\leq 1+\frac{h-{r \choose 2}}{r-((s-1)-2+3)}= 1+\frac{h-{r \choose 2}}{r-r/2}\leq \frac{2}{r}\left(h-\frac{r(r-2)}{4}+1\right)-1;\end{align*} $$
if
$r\geq 5$
is odd and
$m-\ell \leq s-4$
, then
$$ \begin{align*}w_H(w'w")\leq 1+\frac{h-{r \choose 2}}{r-s+1}= 1+\frac{h-{r \choose 2}}{r-(r+1)/2+1}\leq \frac{2}{r}\left(h-\frac{r(r-2)}{4}+1\right)-1.\end{align*} $$
In both cases, we can choose
$f_{i_{\ell -1}}$
to be
$w'w"$
.
Now, we consider the remaining case that
$r\geq 5$
is odd and
$m-\ell \geq s-3$
. Since
$m\leq s-1$
and
$\ell \geq 2$
, we have
$m-\ell \leq s-3$
. Thus,
$m-\ell =s-3$
,
$m=s-1$
and
$\ell =2$
now. In the following, we shall find a desired edge
$f_{i_1}$
. Recall that we have either
$m'\neq 1$
or
$m\neq s-1$
. Thus,
$m'\neq 1$
. Then,
$e_{i_1}$
is not adjacent to
$e_1$
, so w is not an end-vertex of
$e_1$
. Thus,
$w'\notin \{u_1, u_2\}$
. If
$w_H(w'w")\leq \frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )-1$
, then we can choose
$f_{i_1}$
to be
$w'w"$
, and we are done. If
$w_H(w'w")>\frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )-1$
, then since
$w_H(w'w")=\min _{x\in V(H)\setminus V(H_{(\ell )})}w_H(w'x)$
and
$|V(H)\setminus V(H_{(2)})|=r-(m-\ell +3)= r-s= \frac {r-1}{2}$
, we have
$$ \begin{align*} \sum_{x\in V(H)\setminus V(H_{(2)})}w_H(w'x)> &~ |V(H)\setminus V(H_{(2)})|\left(\frac{2}{r}\left(h-\frac{r(r-2)}{4}+1\right)-1\right) \\ = &~\frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right)-\frac{r-1}{2}. \end{align*} $$
By Observation 4.3(i), for any
$e\in {V(H)\choose 2}\setminus \{w'x\colon \, x\in V(H)\setminus V(H_{(2)})\}$
, we have
$$ \begin{align*} w_H(e)\leq &~h-\sum_{x\in V(H)\setminus V(H_{(2)})}w_H(w'x)-\left({r \choose 2}-\left(|V(H)\setminus V(H_{(2)})|\right)-1\right) \\ < &~h-\left(\frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right)-\frac{r-1}{2}\right)-\left({r \choose 2}-\frac{r-1}{2}-1\right) \\ = &~\frac{1}{r}h+\frac{(r-1)(r-2)}{4}-\frac{r-1}{r} +(r-1)-{r\choose 2}+1 \\ = &~\frac{1}{r}h-\frac{(r-1)(r-2)}{4}+\frac{1}{r} ~< \frac{2}{r}\left(h-\frac{r(r-2)}{4}+1\right)-1. \end{align*} $$
Hence, we can choose two vertices
$w^{\ast }, w^{\ast \ast }\in V(H)\setminus V(H_{(2)})$
arbitrarily so that if we replace
$w'$
by
$w^{\ast }$
in
$H_{(2)}$
and let 
, then we get a desired
$H_1$
. This completes the proof of Claim 6.
Let 
and 
. Then,
$T_2$
is a forest on
$s-t_1$
edges. The following Claims 7 and 8 ensure the existences of the desired edges
$f_1, \ldots , f_{s}$
. We first show that we can find the desired edges
$f_1, \ldots , f_{s}$
in the case
$r=5$
. Note that
$s=3$
when
$r=5$
.
Claim 7 If
$r=5$
, then we can find edges
$f_1, f_2, f_{3} \in {V(H)\choose 2}$
such that:
-
(i)
$H[\{f_1, f_2, f_{3}\}]$
can be embedded into T in which
$f_i$
is embedded into
$e_i$
for each
$i\in [3]$
; and -
(ii)
$w_{F^{+}}(e_i)\geq \sum _{j=1}^{i}w_H(f_j)$
for each
$i\in [3]$
.
Proof Since
$|V(T)|\leq r=5$
, T has at most two components. Let
$V(H)=\{u_1, u_2, \ldots , u_5\}$
with
$w_H(u_1u_2)=1$
. If
$t_1=3=s$
, then we are done by Claim 6 and Inequality (4.12). So, we may assume that
$t_1\leq 2$
.
If
$t_1=1$
, then
$T_1=K_2$
and
$T_2=K_{1,2}$
. Note that
$$ \begin{align*}\min\left\{w_H(a)+w_H(b)\colon\, a, b\in \{u_3u_4, u_3u_5, u_4u_5\}, a\neq b\right\}\leq \frac{2}{3}(h-7),\end{align*} $$
since otherwise
$$ \begin{align*} e(H) &\geq ~\frac{1}{2}\big(w_H(u_3u_4)+w_H(u_3u_5)+w_H(u_3u_4)+w_H(u_4u_5)\\ &\quad +w_H(u_3u_5)+w_H(u_4u_5)\big)+7 \\ & > ~\frac{3}{2}\cdot \frac{2}{3}(h-7)+7 ~= h, \end{align*} $$
a contradiction. Let
$a, b\in \{u_3u_4, u_3u_5, u_4u_5\}$
with
$a\neq b$
,
$w_H(a)+w_H(b)\leq \frac {2}{3}(h-7) \leq \frac {4}{r}\big (h-\frac {r(r-2)}{4}+1\big )-1\leq w_{F^+}(e_3)-1$
and
$w_H(a)\leq w_H(b)$
. Then,
$w_H(a)\leq \frac {1}{3}(h-7) \leq \frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )-1\leq w_{F^+}(e_2)-1$
. In this case,
$u_1u_2$
forms a desired
$T_1$
, and a and b form a desired
$T_2$
. Hence, we can assign
$(f_1, f_2, f_3)$
to be
$(u_1u_2, a, b)$
.
If
$t_1=2$
, then
$T_1=K_{1,2}$
and
$T_2=K_2$
. Note that
$$ \begin{align*} & \min\left\{w_H(u_1u_3)+w_H(u_4u_5), w_H(u_1u_4)+w_H(u_3u_5), w_H(u_1u_5)+w_H(u_3u_4)\right\} \\ &\quad \leq \frac{1}{3}(h-4).\end{align*} $$
Without loss of generality, we may assume that
$w_H(u_1u_3)+w_H(u_4u_5)\leq \frac {1}{3}(h-4)\leq \frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )$
. Then,
$w_H(u_1u_3)\leq \frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )-1$
and
$w_H(u_4u_5)\leq \frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )-1$
. In this case,
$u_1u_2$
and
$u_1u_3$
form a desired
$T_1$
, and
$u_4u_5$
forms a desired
$T_2$
. Hence, we can assign
$(f_1, f_2, f_3)$
to be one of
$(u_1u_2, u_1u_3, u_4u_5)$
and
$(u_1u_2, u_4u_5, u_1u_3)$
. This completes the proof of Claim 7.
We next show that we can find the desired edges
$f_1, \ldots , f_{s}$
in the case
$r\geq 6$
. Note that the statement of Claim 8 below is similar to that of Claim 6. For the convenience of readers, we now point out their differences and connections. Claim 6 aims to find a subgraph
$H_1$
of H so that we can embed it into
$T_1$
, while Claim 8 aims to find a subgraph
$H_T$
of H so that we can embed it into T. Here,
$T_1$
is a connected component of T, and
$H_1$
is a connected component of
$H_T$
. In the proof of Claim 8, we shall find a required
$H_T$
on the basis of
$H_1$
given by Claim 6.
Claim 8 If
$r\geq 6$
, then H contains a subgraph
$H_T$
such that:
-
(i) the underlying graph of
$H_T$
is T; -
(ii) the edge corresponding to
$e_1$
is a critical edge of H; and -
(iii) each edge of
$H_T$
has multiplicity at most
$\frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )-1$
in H.
Proof Recall that
$t_1= |E(T_1)|$
and
$T_2= T\setminus T_1$
is a forest with
$s-t_1$
edges and at most
$r-(t_1+1)$
vertices. If
$t_1=s$
(i.e.,
$T=T_1$
), then the result follows from Claim 6. Hence, we may assume that
$t_1\leq s-1 \leq \frac {r-1}{2}$
.
Let 
Then,
$|E_1|< \frac {r}{2}$
; otherwise
$$ \begin{align*}e(H)> \frac{r}{2}\left(\frac{2}{r}\left(h-\frac{r(r-2)}{4}+1\right)-1\right)+{r\choose 2}-\frac{r}{2} = h-\frac{r(r-2)}{4}+{r-1 \choose 2} > h,\end{align*} $$
a contradiction. Since
$|E_1|$
is an integer, we further have
$|E_1|\leq s-1$
. Let
$H_1$
be the subgraph of H obtained by Claim 6. Let
$H^{\ast }$
be the subgraph of H with
$V(H^{\ast })=V(H)\setminus V(H_1)$
and
$E(H^{\ast })=\big \{e\in E(H[V(H^{\ast })])\colon \, w_H(e)\leq \frac {2}{r}\big (h-\frac {r(r-2)}{4}+1\big )-1\big \}.$
Let
$H^{\ast \ast }$
be the graph with
$V(H^{\ast \ast })=V(H^{\ast })=V(H)\setminus V(H_1)$
and
$E(H^{\ast \ast })=E_1\cap {V(H^{\ast \ast })\choose 2}$
. Let
$T_2'$
be the graph obtained from
$T_2$
by adding
$|V(H^{\ast \ast })|-|V(T_2)|$
isolated vertices. In order to prove the claim, we shall show that
$H^{\ast }$
contains a subgraph
$H_2$
whose underlying graph is
$T_2$
. It suffices to show that there is a packing of
$T_2'$
and
$H^{\ast \ast }$
.
Note that
$|V(T_2')|=|V(H^{\ast \ast })|=r-(t_1+1)$
,
$e(T_2')=e(T_2)=s-t_1$
and
$e(H^{\ast \ast })\leq |E_1|\leq s-1$
. Then,
$$ \begin{align*} ~&~\frac{3}{2}(|V(H^{\ast\ast})|-1)-e(T_2')-e(H^{\ast\ast}) \\ \geq &~\frac{3}{2}(r-t_1-2)-(s-t_1)-(s-1) ~= \frac{3r}{2}-2s-\frac{t_1}{2}-2 \\ \geq &~\frac{3r}{2}-2s-\frac{s-1}{2}-2 ~= \frac{1}{2}(3r-5s-3). \end{align*} $$
If
$r\geq 6$
is even, then
$3r-5s-3=3r-5\frac {r}{2}-3= \frac {r}{2}-3\geq 0$
; if
$r\geq 11$
is odd, then
$3r-5s-3=3r-5\frac {r+1}{2}-3= \frac {r-11}{2} \geq 0$
. Combining with Theorem 2.4, there is a packing of
$T_2'$
and
$H^{\ast \ast }$
, unless
$r\in \{7,9\}$
.
If
$r=9$
, then
$s=5$
,
$1\leq t_1\leq 4$
,
$e(T_2')=5-t_1$
and
$e(H^{\ast \ast })\leq |E_1|\leq 4$
. Thus,
$e(T_2')e(H^{\ast \ast })\leq 4(5-t_1)<{8-t_1\choose 2} ={|V(H^{\ast \ast })|\choose 2}$
. By Theorem 2.3, there is a packing of
$T_2'$
and
$H^{\ast \ast }$
.
If
$r=7$
, then
$s=4$
,
$1\leq t_1\leq 3$
and
$e(H^{\ast \ast })\leq |E_1|\leq 3$
. First, if
$t_1=1$
, then
$|V(H^{\ast \ast })|=7-2=5$
and
$e(T_2')=3$
. Since
$e(T_2')e(H^{\ast \ast })\leq 9<{5\choose 2}={|V(H^{\ast \ast })|\choose 2}$
, there is a packing of
$T_2'$
and
$H^{\ast \ast }$
by Theorem 2.3. Second, if
$t_1=2$
, then
$|V(H^{\ast \ast })|=7-3=4$
and
$e(T_2)=2$
. Let
$V(H_1)=\{u_1, u_2, u_3\}$
,
$V(H)\setminus V(H_1)=\{u_4, u_5, u_6, u_7\}$
, and
$u_1u_2$
be a critical edge. If
$\big |E_1\cap {V(H)\setminus V(H_1) \choose 2}\big |\leq 2$
, then one can easily find a desired
$T_2$
within
$V(H)\setminus V(H_1)$
. If
$\big |E_1\cap {V(H)\setminus V(H_1) \choose 2}\big |=3$
, then
$E_1\cap \{u_iu_j\colon \, i\in [3], j\in \{4, 5, 6, 7\}\}= \emptyset $
. Since
${|V(H)\setminus V(H_1)|\choose 2}=6>3$
, we may assume that
$u_4u_5\notin E_1$
without loss of generality. Then,
$u_1u_2$
and
$u_1u_6$
form a desired
$T_1$
, and
$u_4u_5$
and one edge in
$\{u_3u_4, u_3u_7\}$
form a desired
$T_2$
. Finally, if
$t_1=3$
, then
$T_1\in \{K_{1,3}, P_4\}$
,
$T_2=K_2$
and
$|V(H^{\ast \ast })|=7-4=3$
. Let
$V(H_1)=\{u_1, u_2, u_3, u_4\}$
,
$V(H)\setminus V(H_1)=\{u_5, u_6, u_7\}$
, and
$u_1u_2$
be a critical edge. If
${V(H)\setminus V(H_1) \choose 2}\setminus E_1\neq \emptyset $
, then we can find a desired
$T_2$
within
$V(H)\setminus V(H_1)$
. If
${V(H)\setminus V(H_1) \choose 2}\setminus E_1= \emptyset $
, then
$E_1\cap \big ({V(H)\choose 2}\setminus {V(H)\setminus V(H_1) \choose 2}\big )=\emptyset $
. Then, one can easily find a desired T consisting of edges in
${V(H)\choose 2}\setminus {V(H)\setminus V(H_1) \choose 2}$
. This completes the proof of Claim 8.
By Claims 7, and 8 and Inequality (4.12), there exist edges
$f_1, \ldots , f_{s} \in {V(H)\choose 2}$
and an embedding
$\phi : V(H) \to V(F^+)$
such that for each
$i\in [s]$
:
-
(i)
$\phi (f_i)=e_i$
; and -
(ii)
$w_{F^{+}}(e_i)\geq \sum _{j=1}^{i}w_H(f_j)$
.
Recall that
$e_{s+1}$
is an edge in
$\{v_rv_j \colon \, 1\leq j\leq r-1\}$
with
$w_{F^+}(e_{s+1})=\min _2\{w_{F^+}(v_rv_j)\colon \, 1\leq j\leq r-1\}$
, and
$e_{s+2}, e_{s+3}, \ldots , e_{{r\choose 2}}$
is the ordering of edges in
${V(F^{+})\choose 2}\setminus E(T^{+})$
obtained by Claim 2. For each
$s+1\leq i\leq {r\choose 2}$
, let 
. By Inequalities (4.13) and (4.15), we have
$w_{F^{+}}(e_i)\geq \sum _{j=1}^{i}w_H(f_j)$
for each
$s+1\leq i\leq {r\choose 2}$
. By Lemma 2.8, there is a multicolored copy of H in
$F^+$
. Thus F is H-friendly. By Lemma 2.6, G is
$(r-1)$
-partite. This completes the proof of Lemma 4.2.
5 Step II: completing the proof via stability
In this section, we finish the proof of Theorem 1.3. First, we prove a stability result for r-vertex r-color-critical multigraphs (i.e., Lemma 5.2) using the ideas in [Reference Chakraborti, Kim, Lee, Liu and Seo7, Reference Roberts and Scott28]. Second, we extend the stability result to r-color-critical graphs with any number of vertices (i.e., Lemma 5.5) using the multicolor version of Szemerédi’s Regularity Lemma and the Embedding Lemma. Last, we prove Theorem 5.6, which implies Theorem 1.3 immediately.
We will use the following observation which follows from a straightforward calculation.
Observation 5.1 [Reference Chakraborti, Kim, Lee, Liu and Seo7, Proposition 6.2]
Suppose
$0<\frac {1}{n}\ll \delta <1$
. Let G be an n-vertex multigraph with
$d{n\choose 2}$
edges. If
$B\subseteq V(G)$
is a vertex set with
$|B|=\frac {1}{2}\delta n$
and every
$v\in B$
satisfies
$d_G(v)<(1-\delta )dn$
, then
$G-B$
has at least
$\big (1+\frac {1}{2}\delta ^2\big )d{|V(G-B)|\choose 2}$
edges.
For two multigraphs G and H of the same order, the symmetric difference of G and H is defined by
Lemma 5.2 Let
$r\geq 5$
,
$k> \max \big \{\frac {r-1}{r-2}(h-1), 2\frac {r-1}{r}\big (h-\frac {r(r-2)}{4}+1\big )\big \}$
and
$0<\frac {1}{\sqrt {n}}\leq \eta \ll \eta _1, \frac {1}{k}<1$
. Let H be an r-vertex r-color-critical multigraph with h edges. Let G be an n-vertex simply k-colored multicolored-H-free multigraph with
$e(G)\geq k\cdot t_{r-1}(n)-\eta n^2$
. Then,
$|G\triangle (k\cdot T_{r-1}(n))|\leq \eta _1 n^2$
.
Proof Let
$\delta $
be such that
$0<\eta \ll \delta \ll \eta _1, \frac {1}{k}<1$
. We first show that G contains a subgraph of order at least
$(1-\delta ^{1/2})n$
with minimum degree at least
$(1-\delta ^{1/2})k\delta (T_{r-1}(n))$
. Let
$d>0$
be the number such that
$e(G)=d{n\choose 2}$
. Since
$e(G)\geq k\cdot t_{r-1}(n)-\eta n^2\geq k\frac {r-2}{r-1}{n\choose 2}-\eta n^2$
, we have
$d\geq k\frac {r-2}{r-1}-3\eta $
. Let 
.
Claim 9
$|L|<\delta \frac {n}{2}.$
Proof Suppose for a contradiction that
$|L|\geq \delta \frac {n}{2}$
. We choose
$B\subseteq L$
with
$|B|=\delta \frac {n}{2}$
. By Observation 5.1 and since
$\frac {1}{\sqrt {n}}\leq \eta \ll \delta $
, we have
$$ \begin{align*} e(G-B)\geq &~\left(1+\frac{1}{2}\delta^2\right)d{|V(G-B)|\choose 2} ~\geq \left(1+\frac{1}{2}\delta^2\right)\left(k\frac{r-2}{r-1}-3\eta\right){|V(G-B)|\choose 2} \\> &~\left(k\frac{r-2}{r-1}-3\eta + \frac{1}{2}\delta^2\right){|V(G-B)|\choose 2} ~> \left(k\frac{r-2}{r-1}+ \frac{1}{3}\delta^2\right){|V(G-B)|\choose 2} \\ > &~k\cdot t_{r-1}(|V(G-B)|). \end{align*} $$
On the other hand, since G (and thus
$G-B$
) is multicolored-H-free, we have
$e(G-B)\leq k\cdot t_{r-1}(|V(G-B)|)$
by Theorem 4.1. This contradiction completes the proof.
Let 
. By Claim 9, we have
$|L|<\delta \frac {n}{2}.$
Combining with
$r\geq 5$
,
$k> \frac {r-1}{r-2}(h-1)$
,
$0<\eta \ll \delta \ll \frac {1}{k}<1$
and Inequalities (2.1) and (2.2), we have
$$ \begin{align} \delta(M)\geq &~(1-\delta)dn-k|L| ~> (1-\delta)\left(k\frac{r-2}{r-1}-3\eta\right)n-k\delta\frac{n}{2} \nonumber\\ = &~\left(k\frac{r-2}{r-1}-3\eta-\left(k\left(\frac{r-2}{r-1}+\frac{1}{2}\right)-3\eta\right)\delta\right)n ~\geq \left(1-\delta^{1/2}\right)k\frac{r-2}{r-1}n \nonumber\\ \geq &~\left(1-\delta^{1/2}\right)k\delta(T_{r-1}(n)) ~\geq \left(1-\delta^{1/2}\right)k\delta(T_{r-1}(|V(M)|)), \end{align} $$
and
$$ \begin{align} e(M)\geq &~\frac{1}{2}\delta(M)|V(M)| ~> \frac{1}{2}\left(1-\delta^{1/2}\right)k\delta(T_{r-1}(|V(M)|))|V(M)| \nonumber\\ \geq &~\frac{1}{2}\left(1-\delta^{1/2}\right)k\frac{r-2}{r-1}(|V(M)|-1)|V(M)| ~= \left(1-\delta^{1/2}\right)k\frac{r-2}{r-1}{|V(M)|\choose 2} \nonumber\\ \geq &~k\frac{r-2}{r-1}\cdot \frac{|V(M)|^2}{2}-\delta^{2/5}n^2 ~\geq k\cdot t_{r-1}(|V(M)|)-\delta^{2/5}n^2. \end{align} $$
By Inequality (5.1) and Lemma 4.2, we can deduce that M is
$(r-1)$
-partite. Let
$V_1, \ldots , V_{r-1}$
be the partite sets of M. We claim that for each
$i\in [r-1]$
, we have
$\big ||V_i|-\frac {|V(M)|}{r-1}\big |\leq 2\delta ^{1/5}n.$
Otherwise, there exist some
$i\neq j$
such that
$|V_i|-|V_j|>2\delta ^{1/5}n$
, which implies that
$e(M)\leq k\cdot t_{r-1}(|V(M)|)-\delta ^{2/5}n^2$
, contradicting Inequality (5.2). Then, by deleting at most
$k(r-1)(2\delta ^{1/5}n)n<\delta ^{1/6}n^2$
edges of M, we obtain an
$(r-1)$
-partite multigraph
$M'$
with class sizes equal to that of
$T_{r-1}(|V(M)|)$
, and
$$ \begin{align*}e(M') & \geq e(M)-\delta^{1/6}n^2>k\cdot t_{r-1}(|V(M)|)-\delta^{2/5}n^2-\delta^{1/6}n^2 \\ & > k\cdot t_{r-1}(|V(M)|)- 2\delta^{1/6}n^2.\end{align*} $$
Then,
$$ \begin{align*}|G\triangle (k\cdot T_{r-1}(n))| & \leq |M\triangle (k\cdot T_{r-1}(|V(M)|))|+k|L|n \\ & < \delta^{1/6}n^2 + 2\delta^{1/6}n^2 + k\delta\frac{n^2}{2}< \eta_1 n^2.\end{align*} $$
The proof is complete.
In order to extend the stability result from r-vertex r-color-critical multigraphs to r-color-critical graphs with any number of vertices, we shall use the multicolor version of Szemerédi’s Regularity Lemma [Reference Szemerédi31] and the Embedding Lemma. Similar results for edge-colored graphs were also used in [Reference Hoppen, Lefmann and Odermann16]. Let G be a simply k-colored multigraph. The edge density of G is defined as 
. For two disjoint nonempty vertex sets X,
$Y,$
and a color
$\rho $
, the
$\rho $
-density of
$(X,Y)$
is defined to be 
where
$e_{\rho }(X,Y)$
is the number of edges between X and Y with color
$\rho $
. For
$\varepsilon>0$
, the pair
$(X,Y)$
is
$\varepsilon $
-regular if for every
$X'\subseteq X$
and
$Y'\subseteq Y$
with
$|X'|\geq \varepsilon |X|$
and
$|Y'|\geq \varepsilon |Y|$
, we have
$|d_{\rho }(X,Y)-d_{\rho }(X',Y')|\leq \varepsilon $
for every color
$\rho $
. A partition
$\mathcal {P}=(V_1, \ldots , V_m)$
of
$V(G)$
is an
$\varepsilon $
-regular partition of G if:
-
•
$\left ||V_i|-|V_j|\right |\leq 1$
for all
$1\leq i<j\leq m$
; and -
•
$(V_i, V_j)$
is
$\varepsilon $
-regular for all but at most
$\varepsilon m^2$
pairs
$(i,j)$
.
For
$\varepsilon , \gamma>0$
and a color
$\rho $
, the pair
$(X,Y)$
is
$(\varepsilon , \gamma; \rho )$
-lower-regular if for every
$X'\subseteq X$
and
$Y'\subseteq Y$
with
$|X'|\geq \varepsilon |X|$
and
$|Y'|\geq \varepsilon |Y|$
, we have
$d_{\rho }(X',Y')\geq \gamma $
. Given
$\varepsilon , \gamma>0$
and an
$\varepsilon $
-regular partition
$\mathcal {P}=(V_1, \ldots , V_m)$
of G, we define the
$(\varepsilon , \gamma , \mathcal {P})$
-reduced multigraph R as follows: R is a simply k-colored multigraph with colors
$\{R_1, \ldots , R_k\}$
and vertex set
$[m]$
, and for each
$ij\in {[m]\choose 2}$
and
$\rho \in [k]$
, we have
$ij \in E(R_{\rho })$
if and only if
$(V_i,V_j)$
is
$(\varepsilon , \gamma; \rho )$
-lower-regular.
Lemma 5.3 (Multicolor Regularity Lemma [Reference Chakraborti, Kim, Lee, Liu and Seo7, Reference Komlós and Simonovits22, Reference Szemerédi31])
For any
$\varepsilon>0$
and integers
$k, M_0\geq 1$
, there exist
$n'$
and M such that every simply k-colored multigraph G on
$n\geq n'$
vertices admits an
$\varepsilon $
-regular partition
$\mathcal {P}=(V_1, \ldots , V_m)$
with
$M_0\leq m\leq M$
. Moreover, for
$\gamma>0$
, the density of the
$(\varepsilon , \gamma , \mathcal {P})$
-reduced multigraph R satisfies
$d(R)\geq d(G)-2(\varepsilon + \gamma )$
.
Given a simply k-colored multigraph G with an
$\varepsilon $
-regular partition
$\mathcal {P}=(V_1, \ldots , V_m)$
and
$(\varepsilon , \gamma , \mathcal {P})$
-reduced multigraph R, we define a simply k-colored multigraph
$G^{\mathcal {P}}=G^{\mathcal {P}}(\varepsilon , \gamma )$
as follows. Let
$G^{\mathcal {P}}$
be a simply k-colored multigraph with colors
$\{G^{\mathcal {P}}_1, \ldots , G^{\mathcal {P}}_k\}$
and vertex set
$V(G)$
, in which for each
$ij\in {[m]\choose 2}$
and
$\rho \in [k]$
, the bipartite graph
$G^{\mathcal {P}}_{\rho }[V_i,V_j]$
is a complete bipartite graph if
$ij\in E(R_{\rho })$
, and an empty bipartite graph if
$ij\notin E(R_{\rho })$
, and there is no edge within each part.
Lemma 5.4 (Multicolor Embedding Lemma [Reference Chakraborti, Kim, Lee, Liu and Seo7, Reference Komlós and Simonovits22])
Suppose
$0 \leq \frac {1}{n} \ll \varepsilon \ll \gamma , \frac {1}{h}\leq 1$
. Let H be an r-vertex h-edge multigraph, and G be a simply k-nested-colored multigraph with an
$\varepsilon $
-regular partition
$\mathcal {P}$
. If
$G^{\mathcal {P}}(\varepsilon , \gamma )$
contains a multicolored copy of H, then G contains a multicolored copy of H.
Now, we prove a stability result for color-critical simple graphs with any number of vertices.
Lemma 5.5 Let
$r\geq 5$
,
$k> \max \big \{\frac {r-1}{r-2}(h-1), 2\frac {r-1}{r}\big (h-\frac {r(r-2)}{4}+1\big )\big \}$
and
$0<\frac {1}{n}\ll \eta \ll \mu , \frac {1}{k}<1$
. Let H be an r-color-critical graph with h edges. Let G be an n-vertex simply k-nested-colored multicolored-H-free multigraph with
$e(G)\geq k\cdot t_{r-1}(n)-\eta n^2$
. Then,
$|G\triangle (k\cdot T_{r-1}(n))|\leq \mu n^2$
.
Proof Let
$0<\frac {1}{n}\ll \varepsilon \ll \gamma \ll \eta \ll \eta ' \ll \mu , \frac {1}{k}<1$
. Let
$H_c$
be the color-reduced multigraph of H. Applying Lemma 5.3 to G with the constants
$\varepsilon , k, \frac {1}{\varepsilon }$
playing the roles of
$\varepsilon , k, M_0$
, we obtain an M and an
$\varepsilon $
-regular partition
$\mathcal {P}=\{V_1, \ldots , V_m\}$
with
$\frac {1}{\varepsilon }\leq m\leq M$
, and we may assume that
$n\gg M$
. Let R be the
$(\varepsilon , \gamma , \mathcal {P})$
-reduced multigraph of G. Let
$\{G_1, \ldots , G_k\}$
be the colors of G. Since G is nested, we may assume that
$G_1 \subseteq \cdots \subseteq G_k$
without loss of generality. For each
$1\leq \rho _1 <\rho _2 \leq k$
and
$ij\in {[m]\choose 2}$
, if
$(V_i,V_j)$
is
$(\varepsilon , \gamma; \rho _1)$
-lower-regular, then
$(V_i,V_j)$
is also
$(\varepsilon , \gamma; \rho _2)$
-lower-regular since
$G_{\rho _1}\subseteq G_{\rho _2}$
. This implies that if
$ij\in E(R_{\rho _1})$
, then we also have
$ij\in E(R_{\rho _2})$
. Hence, R is nested, and therefore,
$G^{\mathcal {P}}= G^{\mathcal {P}}(\varepsilon , \gamma )$
is nested by the definition of
$G^{\mathcal {P}}$
. Since G is multicolored-H-free, the multigraph
$G^{\mathcal {P}}$
is multicolored-H-free by Lemma 5.4. Then, R is multicolored-
$H_c$
-free, since otherwise
$G^{\mathcal {P}}$
contains a multicolored copy of H.
By Lemma 5.3, we have
$d(R)\geq d(G)-2(\varepsilon + \gamma )$
. Combining with
$0<\frac {1}{n}\ll \varepsilon \ll \gamma \ll \eta $
, we have
$$ \begin{align*} e(R) = &~d(R)m^2 \geq d(G)m^2-2(\varepsilon + \gamma)m^2 \\ \geq &~\left(k\cdot t_{r-1}(n)-\eta n^2\right)\frac{m^2}{n^2}-2(\varepsilon + \gamma)m^2 ~\geq k\cdot t_{r-1}(m)-2\eta m^2. \end{align*} $$
Note that
$|V(R)|=m\geq \frac {1}{\varepsilon }$
and
$0<\varepsilon \ll \eta \ll \eta ' \ll \frac {1}{k}<1$
. Then, by Lemma 5.2, we have
$|R\triangle (k\cdot T_{r-1}(m))|\leq \eta ' m^2$
. Thus, we can choose a copy A of
$k\cdot T_{r-1}(m)$
on vertex set
$V(R)=[m]$
such that
$|R\triangle A|\leq \eta ' m^2$
. Let
$U_1, \ldots , U_{r-1}$
be the partite sets of A. For each
$i\in [r-1]$
, let
$W_i=\bigcup _{j\in U_i}V_j$
. Let B be the complete
$(r-1)$
-partite graph with partite sets
$W_1, \ldots , W_{r-1}$
in which every edge has multiplicity k. Since
$|R\triangle A|\leq \eta ' m^2$
, we have
$|G^{\mathcal {P}}\triangle B|\leq \eta ' m^2\left \lceil \frac {n}{m}\right \rceil ^2< 2\eta ' n^2$
. Note that
$\big \lfloor \frac {m}{r-1}\big \rfloor \leq |U_{i_1}|\leq \big \lceil \frac {m}{r-1}\big \rceil $
for each
$i_1\in [r-1]$
, and
$\big \lfloor \frac {n}{m}\big \rfloor \leq |V_{i_2}|\leq \big \lceil \frac {n}{m}\big \rceil $
for each
$i_2\in [m]$
. Thus, for each
$1\leq i<j\leq r-1$
, we have
$\left ||W_i|-|W_j|\right |\leq \left \lceil \frac {n}{m}\right \rceil +\big \lfloor \frac {m}{r-1}\big \rfloor < 2\frac {n}{m}$
. Thus, we can obtain a copy of
$k\cdot T_{r-1}(n)$
by deleting or adding at most
$k(r-1)(2\frac {n}{m}) n$
edge from B. So
$|B\triangle (k\cdot T_{r-1}(n))|\leq k(r-1)(2\frac {n}{m}) n<2kr\frac {1}{m}n^2\leq 2kr\varepsilon n^2 \leq \eta ' n^2$
. Then,
$$ \begin{align*}|G^{\mathcal{P}}\triangle (k\cdot T_{r-1}(n))|\leq |G^{\mathcal{P}}\triangle B|+ |B\triangle (k\cdot T_{r-1}(n))|< 2\eta' n^2 + \eta' n^2 \leq 3\eta' n^2,\end{align*} $$
and thus
$$ \begin{align*}e(G^{\mathcal{P}})\leq k\cdot t_{r-1}(n)+3\eta' n^2 \leq e(G)+ 4\eta' n^2.\end{align*} $$
From the definition of
$G^{\mathcal {P}}$
, we know that there exists an edge subset
$E\subseteq E(G)$
with
$$ \begin{align*}|E|\leq k\left(\varepsilon m^2 \left(\frac{n}{m}\right)^2 + \frac{1}{m}\cdot \frac{n^2}{2} + \gamma n^2\right)=k\left(\varepsilon + \frac{1}{2m} + \gamma\right)n^2 \leq \eta' n^2\end{align*} $$
such that
$E(G)\setminus E \subseteq E(G^{\mathcal {P}})$
. Then,
$$ \begin{align*}|G\triangle G^{\mathcal{P}}|\leq |E|+\left(e(G^{\mathcal{P}})-|E(G)\setminus E|\right)\leq 2|E|+4\eta' n^2\leq 6\eta' n^2.\end{align*} $$
Thus,
$|G\triangle (k\cdot T_{r-1}(n))|\leq |G\triangle G^{\mathcal {P}}|+|G^{\mathcal {P}}\triangle (k\cdot t_{r-1}(n))|\leq 9\eta ' n^2\leq \mu n^2$
.
Now, we have all the ingredients to state and prove our main result. Note that Theorem 1.3 follows from Theorem 5.6 below immediately since
$2\frac {r-1}{r}(h-1)>\max \big \{\frac {r-1}{r-2}(h-1), 2\frac {r-1}{r}\big (h-\frac {r(r-2)}{4}+1\big )\big \}$
for
$r\geq 5$
.
Theorem 5.6 Let
$r\geq 5$
and H be an r-color-critical graph with h edges. If n is sufficiently large and
$$ \begin{align*}k> \max\left\{\frac{r-1}{r-2}(h-1), 2\frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right)\right\},\end{align*} $$
then
${\text {ex}}_k(n, H)=k\cdot t_{r-1}(n)$
, and the unique n-vertex k-color extremal multigraph of H consists of k colors all of which are identical copies of
$T_{r-1}(n)$
.
Proof Let
$0<\frac {1}{n}\ll \mu \ll \frac {1}{h} < 1$
. We may assume that H contains no isolated vertex, so
$|V(H)|\leq 2h$
. Let G be an n-vertex simply k-colored multicolored-H-free multigraph with
$e(G)\geq k\cdot t_{r-1}(n)$
. We shall show that
$G=k\cdot T_{r-1}(n)$
. By Lemma 2.5, we may assume that G is nested and
$\delta (G)\geq k\delta (T_{r-1}(n))$
. By Lemma 5.5, we have
$|G\triangle (k\cdot T_{r-1}(n))|\leq \mu n^2$
.
Let
$K^{(h)}$
be a complete
$(r-1)$
-partite multigraph with
$2h$
vertices in each part whose edges all have multiplicity at least h. Let
$K'$
be the underlying graph of
$K^{(h)}$
, i.e.,
$K'$
is a complete
$(r-1)$
-partite graph with
$2h$
vertices in each part. Let 
. Since
$|G\triangle (k\cdot T_{r-1}(n))|\leq \mu n^2$
, we have
$|X|\geq t_{r-1}(n)-\mu n^2> t_{r-2}(n)+\frac {1}{2r^2}n^2 > {\text {ex}}(n, K')$
by the Erdős–Stone–Simonovits Theorem. Thus, G contains
$K^{(h)}$
as a subgraph. Let K be a copy of
$K^{(h)}$
in G with partite sets
$W_1, \ldots , W_{r-1}$
.
Claim 10 K is H-friendly.
Proof Let
$K^{+}$
be the multigraph obtained by adding a new vertex v to K and adding edges incident to v of multiplicity at most k such that
$d_{K^+}(v)\geq (r-2)2hk$
and
$d_{W_i}(v)\geq 1$
for all
$i\in [r-1]$
. Without loss of generality, we may assume that
$d_{W_1}(v)=\min _{i\in [r-1]} d_{W_i}(v)$
, and let
$w\in W_1$
with
$w_{K^+}(vw)\geq 1$
. We claim that
$d_{W_i}(v)\geq kh$
for each
$i\geq 2$
. Indeed, if
$\min _{2\leq i\leq r-1} d_{W_i}(v)<kh$
, then
$d_{K^+}(v)<2kh+k(r-3)2h =(r-2)2hk$
, a contradiction.
Let
$ab$
be a critical edge of H with
$d_{H}(a)\leq d_H(b)$
. Since
$\chi (H)=r$
, we have
$\chi (H-\{a,b\})\geq r-2$
. Thus,
$h\geq {r\choose 2}$
and
$e(H-\{a,b\})\geq {r-2 \choose 2}$
. Then,
$d_H(a)+d_H(b)-1+{r-2 \choose 2}\leq h$
, so
$d_H(a)\leq \frac {h}{2}-1$
. Let 
.
For each
$i\in \{2, \ldots , r-1\}$
, let
$w_{i,1}, \ldots , w_{i,2h}$
be the vertices of
$W_i$
with
$w_{K^+}(vw_{i,1})\geq \cdots \geq w_{K^+}(vw_{i,2h})$
. We claim that for each
$i\in \{2, \ldots , r-1\}$
and
$j\in [d]$
, we have
$w_{K^+}(vw_{i,j})\geq d-j+2$
. To see this, note that
$$ \begin{align*}w_{K^+}(vw_{i,j})\geq \frac{1}{2h-j+1}\left(d_{W_i}(v)-\sum\nolimits_{\ell =1}^{j-1}w_{K^+}(vw_{i,\ell})\right)\geq \frac{1}{2h-j+1}(kh-k(j-1))\end{align*} $$
and
$$ \begin{align*} ~&~kh-k(j-1)-(2h-j+1)(d-j+2) \\ \geq &~kh-k(j-1)-(2h-j+1)\left(\frac{h}{2}-2-j+2\right) \\ = &~-j^2-\left(k-\frac{5}{2}h-1\right)j+ k(h+1)-h^2-\frac{h}{2}. \end{align*} $$
Let 
. Then,
$\min \{f(x)\colon \, 1\leq x\leq d\}\geq \min \{f(x)\colon \, 1\leq x\leq \frac {h}{2}\}\geq \min \{f(1), f(\frac {h}{2})\}\geq 0$
. Thus,
$w_{K^+}(vw_{i,j})\geq d-j+2$
for each
$i\in \{2, \ldots , r-1\}$
and
$j\in [d]$
.
Consider a critical coloring of H with color classes
$V_1, \ldots , V_r$
, where
$a\in V_r$
,
$b\in V_1$
and
$e(V_1, V_r)=1$
. Since
$e(V_1, V_r)=1$
, we may further assume that
$V_r=\{a\}$
by putting the vertices of
$V_r\setminus \{a\}$
into
$V_1$
if necessary. For each
$2\leq i\leq r-1$
, let
$V_i'=N_H(a)\cap V_i$
. Take an embedding
$\phi : V(H) \to V(K^+)$
and an ordering
$(e_1, \ldots , e_h)$
of the edges of H with
$e_1=ab$
and
$\{e_2, \ldots , e_{d+1}\}=\{au\colon \, u\in N_H(a)\setminus \{b\}\}$
such that:
-
(i)
$\phi (a)=v$
,
$\phi (b)=w$
,
$\phi (V_1)\subseteq W_1$
; -
(ii)
$\phi (V_i')=\{w_{i,1}, \ldots , w_{i,|V_i'|}\}$
and
$\phi (V_i)\subseteq W_i$
for each
$2\leq i\leq r-1$
; and -
(iii)
$w_{K^+}(\phi (e_2))\leq \cdots \leq w_{K^+}(\phi (e_{d+1}))$
.
Then, for each
$2\leq j\leq d+1$
and
$2\leq i\leq r-1$
, since
$w_{K^+}(\phi (e_j))=\max _{d+2-j}\{w_{K^+}(\phi (e_2)), \ldots , w_{K^+}(\phi (e_{d+1}))\}$
and
$w_{K^+}(vw_{i,d+2-j})=\max _{d+2-j}\{w_{K^+}(vw_{i,1}), \ldots , w_{K^+}(vw_{i,2h})\}$
, we have
$w_{K^+}(\phi (e_j))\geq w_{K^+}(vw_{i,d+2-j})\geq j=\sum _{i=1}^{j}w_H(e_i)$
. Thus,
$w_{K^+}(\phi (e_j))\geq \sum _{i=1}^{j}w_H(e_i)$
for each
$1\leq j\leq h$
. By Lemma 2.8,
$K^+$
contains a multicolored copy of H. Thus, K is H-friendly.
By Claim 10, K is H-friendly. Moreover, K is an induced subgraph of G, since any additional edge within a color class of K yields a multicolored copy of H. By Lemma 2.6, G is
$(r-1)$
-partite. Since
$T_{r-1}(n)$
is the unique
$(r-1)$
-partite graph on n vertices with
$t_{r-1}(n)$
edges, we have
$e(G)\leq k\cdot t_{r-1}(n)$
. Thus,
$e(G)= k\cdot t_{r-1}(n)$
, and
$G=k\cdot T_{r-1}(n)$
. This completes the proof of Theorem 5.6.
6 Concluding remarks
In this article, we prove that Conjecture 1.2 holds for
$k\geq 2\frac {r-1}{r}(h-1)$
. We now give a remark regarding the challenges in employing our current arguments to fully resolve Conjecture 1.2. The main challenge in settling the full upper range
$k\geq \frac {r-1}{r-2}(h-1)$
lies in improving the lower bound on k in Lemma 4.2. Essentially, the proof of this key lemma is completed in two steps:
-
(1) we first find a multigraph F on
$r-1$
vertices in G via Turán’s Theorem and Lemma 2.7, and then obtain a multigraph
$F^+$
by adding a new vertex and several new edges to F; -
(2) we show that
$F^+$
contains a multicolored copy of H utilizing certain packing arguments, which implies that F is H-friendly and therefore G is
$(r-1)$
-partite by Lemma 2.6.
In the first step, the main task is to identify a complete multigraph on
$r-s$
vertices with edges of high multiplicities, where
$s= \left \lceil \frac {r}{2}\right \rceil $
. If our focus is solely on this particular task, then as the value of s increases, the required value of k decreases accordingly. In the second step, the main task is to show that there is a packing of two graphs. In this step, if the value of s increases, then the required multiplicity on the edges in
$F^+$
must increase, and the required value of k increases accordingly. Therefore, there is a trade-off between the two steps. After conducting a thorough trade-off analysis, we have selected
$s= \left \lceil \frac {r}{2}\right \rceil $
and
$k\geq 2\frac {r-1}{r}(h-1)$
as the optimal parameter values. Although in the small case
$r=5$
, we can improve the bound on k from
$\frac {8}{5}(h-1)$
to
$\frac {3}{2}(h-1)$
using some complicated analysis (which we decide to not include here), the packing method presented here cannot be used to significantly improve the lower bound on k for general r. Hence, some novel ideas for embedding are called for.
We next provide some remarks on our new arguments compared to the previous papers [Reference Chakraborti, Kim, Lee, Liu and Seo7, Reference Keevash, Saks, Sudakov and Verstraëte20] on the same topic. Note that the graphs considered in [Reference Chakraborti, Kim, Lee, Liu and Seo7, Reference Keevash, Saks, Sudakov and Verstraëte20] possess some nice properties. Thus, by some clever arguments, they can find a multicolored H in a multigraph with one edge of high multiplicity. However, when dealing with general color-critical (multi)graphs, the presence of merely a single edge with high multiplicity is insufficient for us to identify a multicolored H. We must find a complete multigraph on
$r-s$
vertices with edges of high multiplicities, where
$s= \left \lceil \frac {r}{2}\right \rceil $
by conducting a trade-off analysis as mentioned above. And finally, we use a novel graph packing technique to find the required multicolored copy of H.
Let H be a non-color-critical graph with h edges and
$\chi (H)\geq 3$
. Chakraborti, Kim, Lee, Liu, and Seo (see [Reference Chakraborti, Kim, Lee, Liu and Seo7, Proposition 1.6]) proved that
${\text {ex}}_k(n, H)> \max \big \{(h-1){n\choose 2}, k\cdot {\text {ex}}(n, H)\big \}$
when
$k\geq \frac {r-1}{r-2}(h-1)$
and n is sufficiently large. Thus, Conjecture 1.2 does not hold for general h-edge graphs with chromatic number r when
$k\geq \frac {r-1}{r-2}(h-1)$
. However, we can prove the following result for any general graph (not necessarily color-critical) with chromatic number at least three, showing that this conjecture stays true in the range
$h\leq k \leq h+\big \lfloor \frac {r}{2}\big \rfloor -1$
.
Theorem 6.1 For any graph H with h edges and
$\chi (H)=r\geq 3$
, if n is sufficiently large and
$$ \begin{align*}h\leq k \leq h+\left\lfloor\frac{r}{2}\right\rfloor-1,\end{align*} $$
then
${\text {ex}}_k(n, H)=(h-1){n\choose 2}$
and the unique n-vertex k-color extremal multigraph of H consists of exactly
$h-1$
colors each of which is a copy of
$K_n$
.
We supply a proof sketch in Appendix B. It would be interesting to determine the maximum k such that
${\text {ex}}_k(n, H)=(h-1){n\choose 2}$
for every graph H with h edges and
$\chi (H)\geq 3$
.
Besides the sum condition
$\sum _{i\in [k]}e(G_i)$
, the product condition
$\prod _{i\in [k]}e(G_i)$
for multicolored triangles was also studied in [Reference Falgas-Ravry, Markström and Räty12, Reference Frankl13, Reference He, Frankl, Győri, Lv, Salia, Tompkins, Varga and Zhu15]. Further research on the product condition for general cliques or color-critical graphs could be fruitful. On the other hand, it is also natural to study multicolored spanning structures instead of a fixed small subgraph, such as Hamilton paths and cycles [Reference Aharoni, DeVos, de la Maza, Montejano and Šámal1, Reference Joos and Kim18], perfect matchings [Reference Cheng, Han, Wang and Wang8, Reference Joos and Kim18, Reference Lu, Wang and Yu23], and graph factors [Reference Allen, Böttcher, Hladký and Piguet2, Reference Cheng, Han, Wang and Wang8].
Appendix
A Proof of Lemmas 2.1 and 2.2
For convenience, we will restate Lemmas 2.1 and 2.2.
Lemma 2.1 Let
$r\geq 5$
,
$s=\left \lceil \frac {r}{2}\right \rceil $
and
$h\geq {r\choose 2}$
. If
$\ell $
and i are two integers satisfying one of the following statements:
-
(i)
$2\leq \ell \leq s-2$
and
$r-s+1 \leq i\leq r-1$
; or -
(ii)
$\ell = s-1$
and
$r-s+2 \leq i\leq r-1$
,
then
$\frac {2}{r}\big (r-2-\frac {\ell -1}{i-\ell }\big )\big (h-\frac {r(r-2)}{4}+1\big )\geq h-((\ell -1)s+r-i).$
Proof Let 
We shall show that
$f(r,i,\ell )\geq 0$
. Note that in both cases, we have
$i-\ell \geq r-2s+3$
. Since
$h\geq {r\choose 2}$
and
$$ \begin{align*} \frac{2}{r}\left(r-2-\frac{\ell -1}{i-\ell}\right)-1 = &~1-\frac{4}{r}-\frac{2}{r}\cdot \frac{\ell -1}{i-\ell} ~\geq 1-\frac{4}{r}-\frac{2}{r}\cdot\frac{s-2}{r-2s+3} \\ \geq &~1-\frac{4}{r}-\frac{2}{r}\cdot \frac{(r+1)/2-2}{r-(r+1)+3} ~= \frac{r-5}{2r} ~\geq 0, \end{align*} $$
we have
$$ \begin{align*} f(r,i,\ell) \geq &~\frac{2}{r}\left(r-2-\frac{\ell -1}{i-\ell }\right)\left({r \choose 2}-\frac{r(r-2)}{4}+1\right)-{r \choose 2}+(\ell-1)s+r-i \\ = &~-\frac{r}{2}\left(1+\frac{\ell-1}{i-\ell}\right)+(\ell-1)s+r-i+\frac{2}{r}\left(r-2-\frac{\ell -1}{i-\ell }\right) \\ \geq &~-\frac{r}{2}\left(1+\frac{\ell-1}{i-\ell}\right)+(\ell-1)s+r-i+1. \end{align*} $$
If
$\ell \geq 3$
, then
$$ \begin{align*} f(r,i,\ell) \geq &~-\frac{r}{2}\left(1+\frac{\ell-1}{i-\ell}\right)+(\ell-1)s+r-i+1 \\ \geq &~-\frac{r}{2}\left(1+\frac{\ell-1}{r-2s+3}\right)+(\ell-1)\frac{r}{2}+r-(r-1)+1 \\ \geq &~-\frac{r}{2}\left(2+\frac{\ell-1}{r-(r+1)+3}-\ell\right)+2 ~= \frac{r}{2}\cdot \frac{\ell-3}{2}+2 ~> 0. \end{align*} $$
If
$\ell =2$
, then
$$ \begin{align*} f(r,i,\ell) & \geq -\frac{r}{2}\left(1+\frac{\ell-1}{i-\ell}\right)+(\ell-1)s+r-i+1 \\ & \geq -\frac{r}{2}\left(1+\frac{1}{i-2}\right)+\frac{r}{2}+r-i+1 \\ & = \frac{1}{2(i-2)}\left(-2i^2 + (2r+6)i -5r -4 \right) \\ & \geq \frac{1}{2(i-2)}\min\bigg\{-2\bigg(\frac{r+1}{2}\bigg)^2 + (2r+6)\frac{r+1}{2} -5r -4, \\ & \quad -2(r-1)^2 + (2r+6)(r-1) -5r -4\bigg\} \\ & =\frac{1}{4(i-2)}\min\left\{r^2-4r-3, 2(3r-12)\right\} ~> 0, \end{align*} $$
where the third inequality holds since
$i\geq r-s+1\geq \frac {r+1}{2}$
and
$i\leq r-1$
. This completes the proof.
Lemma 2.2 Let
$r\geq 5$
,
$s=\left \lceil \frac {r}{2}\right \rceil $
,
$2\leq \ell \leq s-1$
and
$h\geq {r\choose 2}$
. Then,
$$ \begin{align*}2\frac{r-\ell-1}{r-\ell}\cdot \frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right)\geq h-(\ell-1)s.\end{align*} $$
Proof Since
$\ell \leq s-1\leq (r-1)/2$
, we have
$$ \begin{align*}2\frac{r-\ell-1}{r-\ell}\cdot \frac{r-1}{r}-1\geq 2\frac{r-1-(r-1)/2}{r-(r-1)/2}\cdot \frac{r-1}{r}-1= \frac{r^2-5r+2}{r(r+1)}>0.\end{align*} $$
Thus,
$$ \begin{align*} &~2\frac{r-\ell-1}{r-\ell}\cdot\frac{r-1}{r}\left(h-\frac{r(r-2)}{4}+1\right)-h+(\ell -1)s \\ \geq &~\frac{2(r-\ell -1)(r-1)}{r(r-\ell )}\left({r \choose 2}-\frac{r(r-2)}{4}+1\right)-{r \choose 2}+(\ell -1)s \\ \geq &~\frac{2(r-\ell-1)(r-1)}{r(r-\ell)}\cdot \frac{r^2+4}{4}-{r\choose 2}+ (\ell -1)\frac{r}{2} \\ \geq &~\frac{1}{2r(r-\ell)}\left(-r^2\ell ^2+(r^3+r^2-4r+4)\ell -2r^3+5r^2-8r+4\right) \\ \geq &~\frac{1}{2r(r-\ell)}\min\bigg\{-r^2\cdot 2^2+(r^3+r^2-4r+4)\cdot 2 -2r^3+5r^2-8r+4, \\ &~\hspace{2.45cm} -r^2\cdot \bigg(\frac{r-1}{2}\bigg)^2+(r^3+r^2-4r+4)\cdot \bigg(\frac{r-1}{2}\bigg) -2r^3+5r^2-8r+4\bigg\} \\ \geq &~\frac{1}{8r(r-\ell)}\min\left\{4(3r^2-16r+12), r^4-6r^3+9r^2-16r+8\right\}. \end{align*} $$
Since
$r\geq 5$
, we have
$3r^2-16r+12>0$
. If
$r\geq 6$
, then
$r^4-6r^3\geq 0$
and
$9r^2-16r\geq 0$
, so
$r^4-6r^3+9r^2-16r+8> 0$
. If
$r=5$
, then
$r^4-6r^3+9r^2-16r+8=5(125-150+45-16)+8>0$
. This completes the proof.
B Proof of Theorem 6.1
The proof of Theorem 6.1 follows from the following four lemmas. Lemma B.2 can be proved using Lemma B.1 and a deleting argument. The proofs of Lemmas B.3, B.4, and the final proof of Theorem 6.1 can be completed by a routine application of the stability argument introduced in [Reference Chakraborti, Kim, Lee, Liu and Seo7], so we omit the details and we only supply a proof of Lemma B.1.
Lemma B.1 Let
$r\geq 3$
,
$h\leq k\leq h+\big \lfloor \frac {r}{2}\big \rfloor -1$
and
$0 \ll \frac {1}{n} \ll \delta \ll \frac {1}{k}<1$
. Let H be an r-vertex h-edge multigraph with
$w_H(e)\geq 1$
for each
$e\in {V(H)\choose 2}$
, and G be an n-vertex simply k-colored multicolored-H-free multigraph with
$\delta (G)\geq (1-\delta )(h-1)(n-1)$
. Then,
$w_G(e)\leq h-1$
for each
$e\in {V(G)\choose 2}$
.
Lemma B.2 Let
$r\geq 3$
,
$h\leq k\leq h+\big \lfloor \frac {r}{2}\big \rfloor -1$
, n be sufficiently large, and H be an r-vertex h-edge multigraph with
$w_H(e)\geq 1$
for each
$e\in {V(H)\choose 2}$
. Then,
${\text {ex}}_k(n, H)=(h-1){n\choose 2}$
, and the n-vertex k-color extremal multigraph of H consists of exactly
$h-1$
colors each of which is a copy of
$K_n$
.
Lemma B.3 Let
$r\geq 3$
,
$h\leq k\leq h+\big \lfloor \frac {r}{2}\big \rfloor -1$
and
$0<\frac {1}{n}\ll \eta \ll \varepsilon , \frac {1}{k}<1$
. Let H be an r-vertex h-edge multigraph with
$w_H(e)\geq 1$
for each
$e\in {V(H)\choose 2}$
. Let G be an n-vertex simply k-nested-colored multicolored-H-free multigraph with
$e(G)\geq (h-1){n\choose 2}-\eta n^2$
. Then,
$|G\triangle ((h-1)\cdot K_n)|\leq \varepsilon n^2$
.
Lemma B.4 Let
$r\geq 3$
,
$h\leq k\leq h+\big \lfloor \frac {r}{2}\big \rfloor -1$
and
$0<\frac {1}{n}\ll \eta \ll \mu , \frac {1}{k}<1$
. Let H be an h-edge graph with
$\chi (H)=r$
. Let G be an n-vertex simply k-nested-colored multicolored-H-free multigraph with
$e(G)\geq (h-1){n\choose 2}-\eta n^2$
. Then,
$|G\triangle ((h-1)\cdot K_n)|\leq \mu n^2$
.
Proof of Lemma B.1
Suppose for a contradiction that G contains an edge
$v_1v_2$
of multiplicity at least h. Applying Lemma 2.7 iteratively, we can find vertices
$v_{3}, \ldots , v_{r}\in V(G)\setminus \{v_1, v_2\}$
such that for each
$3 \leq i \leq r$
, we have
$\sum _{j\in [i-1]} w_G(v_iv_j)\geq (h-1)(i-1).$
For each
$3\leq i\leq r$
, we denote the edges in
$\{v_iv_{\ell }\colon \, 1\leq \ell \leq i-1\}$
by
$e_{i,1}, \ldots , e_{i,i-1}$
with
$w_G(e_{i,1})\geq \cdots \geq w_G(e_{i,i-1})$
. Then, for each
$3\leq i\leq r$
and
$1\leq \ell \leq i-1$
, we have
$$ \begin{align*} w_G(e_{i, \ell})\geq &~\frac{1}{(i-1)-(\ell-1)}\left(\sum\nolimits_{j\in [i-1]} w_G(v_iv_j)-(\ell-1)k\right) \\ \geq &~\frac{1}{i-\ell}\left((h-1)(i-1)-(\ell-1)\left(h+\left\lfloor\frac{r}{2}\right\rfloor-1\right)\right) \\ = &~h-\frac{1}{i-\ell}\left(i-1+\left(\left\lfloor\frac{r}{2}\right\rfloor-1\right)(\ell-1)\right). \end{align*} $$
In particular, we have
$w_G(e_{i,1})\geq h-1$
for all
$3\leq i\leq r$
.
We use
$e_1, e_2, \ldots , e_{{r\choose 2}}$
to denote the edges
$$ \begin{align*}v_1v_2, ~ e_{r,1}, \ldots, e_{3,1}, ~ e_{r,2}, \ldots, e_{3,2}, ~ e_{r,3}, \ldots, e_{4,3}, ~ \ldots, ~ e_{r,r-2}, e_{r-1,r-2}, ~ e_{r,r-1},\end{align*} $$
respectively. We shall show that
$w_{G}(e_j)\geq h-(j-1)$
for all
$1\leq j\leq {r\choose 2}$
. This holds clearly for
$1\leq j\leq r-1$
since
$e_1=v_1v_2$
and
$w_G(e_{i,1})\geq h-1$
for all
$3\leq i\leq r$
. Next, we consider
$r\leq j\leq {r\choose 2}$
, that is, we consider
$e_{i,\ell }$
with
$3\leq i\leq r$
and
$2\leq \ell \leq i-1$
. Now
$e_{i,\ell } = e_j$
with
$j=r-1+\sum _{t=2}^{\ell } (r-t) - (i-\ell -1)=r-i+\ell +\frac {1}{2}(\ell -1)(2r-\ell -2)$
. It suffices to show that
$h-\big (r-i+\ell +\frac {1}{2}(\ell -1)(2r-\ell -2)-1\big )\leq h-\frac {1}{i-\ell }\left (i-1+\left (\left \lfloor \frac {r}{2}\right \rfloor -1\right )(\ell -1)\right ).$
If
$2\leq \ell \leq i-2$
, then
$$ \begin{align*} ~ &~r-i+\ell+\frac{1}{2}(\ell-1)(2r-\ell-2)-1-\frac{1}{i-\ell}\left(i-1+\left(\left\lfloor\frac{r}{2}\right\rfloor-1\right)(\ell-1)\right) \\ \geq &~r-i+\ell+\frac{1}{2}(\ell-1)(2r-\ell-2)-1-\frac{1}{2}\left(i-1+\left(\frac{r}{2}-1\right)(\ell-1)\right) \\ = &~\frac{1}{2}(\ell-1)\left(\frac{3}{2}r-\ell-1\right) + r-\frac{3}{2}i+\ell-\frac{1}{2} \\ \geq &~\frac{1}{2}\left(\frac{3}{2}r-\ell-1\right) + r-\frac{3}{2}i+\ell-\frac{1}{2} ~= \frac{7}{4}r-\frac{3}{2}i +\frac{\ell}{2}-1 ~> 0. \end{align*} $$
If
$\ell =i-1$
, then
$$ \begin{align*} ~ &~r-i+\ell+\frac{1}{2}(\ell-1)(2r-\ell-2)-1-\frac{1}{i-\ell}\left(i-1+\left(\left\lfloor\frac{r}{2}\right\rfloor-1\right)(\ell-1)\right) \\ = &~r-i+\ell+\frac{1}{2}(\ell-1)(2r-\ell-2)-1-\left(i-1+\left(\left\lfloor\frac{r}{2}\right\rfloor-1\right)(\ell-1)\right) \\ = &~(\ell-1)\left(\left\lceil\frac{r}{2}\right\rceil-\frac{\ell}{2}\right)+r-2i+\ell ~= (i-2)\left(\left\lceil\frac{r}{2}\right\rceil-\frac{i-1}{2}\right)+r-i-1\\ \geq &~(i-2)\left(\left\lceil\frac{r}{2}\right\rceil-\frac{r-1}{2}\right)+r-i-1 ~\geq 0. \end{align*} $$
Thus,
$w_{G}(e_j)\geq h-(j-1)$
for all
$1\leq j\leq {r\choose 2}$
. For each
$1\leq j\leq {r\choose 2}$
, let 
, so
$w_{G}(e_j')\geq h-({r\choose 2}-j)$
. Since
$w_H(e)\geq 1$
for each
$e\in {V(H)\choose 2}$
, we can deduce that for any
$E\subseteq {V(H)\choose 2}$
with
$|E|=j$
, we have
$\sum _{e\in E}w_H(e)\leq h- ({r\choose 2}-j)\leq w_{G}(e_j')$
. Therefore,
$G[\{v_1, v_2, \ldots , v_r\}]$
contains a multicolored copy of H by Lemma 2.8, a contradiction. This completes the proof of Lemma B.1.
Acknowledgement
The authors are grateful to the anonymous referees for valuable comments and suggestions which improved the presentation of this article. Jie Ma is supported by National Key Research and Development Program of China (Grant No. 2023YFA1010201) and National Natural Science Foundation of China (Grant No. 12125106). Xihe Li is supported by the National Natural Science Foundation of China (Grant No. 12501492), Shaanxi Province Postdoctoral Science Foundation (Grant No. 2024BSHSDZZ155) and the Fundamental Research Funds for the Central Universities (Grant No. GK202506024). The authors would like to thank Dilong Yang for helpful discussions.
