Proof. Consider the set \(C\) of all colors appearing on the edges of these \(m\) triangles. Partition \(C\) randomly into \(C_1 \cup C_2\) by independently assigning each color to \(C_1\) or \(C_2\) with probability \(\frac{1}{2}\) each.

Fix any one of the \(m\) triangles, say with edge colors \(\{a, b, c\}\). Since the triangle is properly edge-colored, the three colors are distinct. The triangle is monochromatic under the random partition if and only if all three colors \(\{a, b, c\}\) fall into the same part, i.e., either all in \(C_1\) or all in \(C_2\). Therefore, \[\Pr[\text{triangle is monochromatic}] = \Pr[a,b,c \in C_1] + \Pr[a,b,c \in C_2] = \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3 = \frac{1}{4}.\] Consequently, \[\Pr[\text{triangle is heterochromatic}] = 1 - \frac{1}{4} = \frac{3}{4}.\]

Now let \(X\) be the random variable counting the number of heterochromatic triangles under this random partition. For each triangle \(T_i\), define the indicator \(X_i = \mathbf{1}[T_i \text{ is heterochromatic}]\). Then \(X = \sum_{i=1}^{m} X_i\), and by linearity of expectation:

\[\mathbb{E}[X] = \sum_{i=1}^{m} \mathbb{E}[X_i] = \sum_{i=1}^{m} \frac{3}{4} = \frac{3m}{4}.\] Since the expected number of heterochromatic triangles is \(\frac{3m}{4}\), there must exist at least one partition \(C = C_1 \cup C_2\) for which \(X \geq \frac{3m}{4}\). ◻

Proof. For any edge \(e = xy\), the number of triangles with \(e\) as one edge is equal to the size of the intersection of the neighborhoods of \(x\) and \(y\), i.e., \[|N(x) \cap N(y)| = |N(x)| + |N(y)| - |N(x) \cup N(y)|.\] Since \(|N(x) \cup N(y)| \leq n\) (as \(G\) has \(n\) vertices), we have \[|N(x) \cap N(y)| \geq d(x) + d(y) - n.\] Summing over all edges \(e \in E(G)\), we have \[3 N(G, K_3) \geq \sum_{x \in G} d^2(x) - nm,\] where this inequality holds since for a vertex \(x\), its degree \(d(x)\) is counted exactly \(d(x)\) times in the sum (once for each edge incident to \(x\)). By the Cauchy-Schwarz inequality, \(\sum_{x \in G} d^2(x) \geq \frac{1}{n} \left( \sum_{x \in G} d(x) \right)^2\). Since \(\sum_{x \in G} d(x) = 2m\) (the handshaking lemma), substituting this into the inequality gives \[3 N(G, K_3) \geq \frac{(2m)^2}{n} - n m = \frac{m(4m - n^2)}{n}.\] Consequently, we have \[N(G, K_3)\geq \frac{m(4m- n^2)}{3n}.\] This completes the proof. ◻

Proof of Lemma 1. Let \(G\) be a properly edge-colored graph with \(n\) vertices and \(\left\Vert G \right\Vert > \frac{1}{4}n^2 + 2M n^{1+s}\). We first show that \(G\) contains a rainbow subgraph isomorphic to \(H\).

By Lemma 3, the number of triangles in \(G\) satisfies \[N(G,K_3) > \left\Vert G \right\Vert \cdot \frac{4\left( \frac{1}{4}n^2 + 2M n^{1+s} \right) - n^2}{3n} = \left\Vert G \right\Vert \cdot \frac{8M n^{1+s}}{3n} = \frac{8}{3}M \left\Vert G \right\Vert n^s.\] By Lemma 2, there exists a partition of the color set \(C\) into \(C = C_1 \cup C_2\) (\(C_1 \cap C_2 = \emptyset\)) such that the number of heterochromatic triangles in \(G\) is greater than: \[\frac{3}{4} \cdot \frac{8}{3}M \left\Vert G \right\Vert n^s = 2M \left\Vert G \right\Vert n^s.\] Define the following sets and notations:

• \(N_i(x)\): the set of vertices adjacent to \(x\) via edges colored in \(C_i\) for \(i=1,2\);

• \(\left\Vert G[N_i(x)] \right\Vert_{3-i}\): the number of edges in the induced subgraph \(G[N_i(x)]\) that are colored in \(C_{3-i}\) for \(i=1,2\).

Note that for each \(i\in\{1,2\}\), \(\sum_{x \in G} \left\Vert G[N_i(x)] \right\Vert_{3-i}\) counts the number of heterochromatic triangles with exactly one \(C_{3-i}\)-colored edge (each such triangle is counted once at the vertex opposite the edge with color in \(C_{3-i}\)). Thus \[\sum_{x \in G} \left\Vert G[N_1(x)] \right\Vert_2 + \sum_{x \in G} \left\Vert G[N_2(x)] \right\Vert_1 > 2M \left\Vert G \right\Vert n^s= M n^s \left( \sum_{x \in G} d_1(x) + \sum_{x \in G} d_2(x) \right).\] This implies that there exists at least one vertex \(x \in G\) such that either \(\left\Vert G[N_1(x)] \right\Vert_2 > M n^s d_1(x)\) or \(\left\Vert G[N_2(x)] \right\Vert_1 > M n^s d_2(x)\). Without loss of generality, assume \(\left\Vert G[N_1(x)] \right\Vert_2 > M n^s d_1(x)\).

Consider the subgraph \(T\) of \(G\) with vertex set \(N_1(x)\) and edge set consisting of all \(C_2\)-colored edges in \(G[N_1(x)]\). Then \(\left\Vert T \right\Vert = \left\Vert G[N_1(x)] \right\Vert_2 > M n^s d_1(x)>M |T|^{1+s}\), where the last inequality holds since \(d_1(x) = |N_1(x)| = |T|<n\). By the hypothesis of Lemma 1, \(T\) contains a rainbow subgraph isomorphic to \(H'\) (the graph obtained by deleting one vertex from \(H\)).

Note that all vertices in \(T\) are adjacent to \(x\) via \(C_1\)-colored edges. Thus, the rainbow \(H'\) in \(T\) and the vertex \(x\) together form a subgraph isomorphic to \(H\). We verify that this \(H\) is rainbow: first, edges colored with colors in \(C_1\) (connecting \(x\) to \(T\)) are distinct from edges colored with colors in \(C_2\) (forming \(H'\) in \(T\)); second, all \(C_1\)-colored edges are incident to \(x\), so they have distinct colors (due to proper edge coloring); finally, all \(C_2\)-colored edges form a rainbow \(H'\) and thus, they also have distinct colors. Therefore, the rainbow Turán number of \(H\) satisfies \[\text{ex}^*(n, H) \leq \frac{1}{4}n^2 + 2M n^{1+s}.\] This completes the proof of Lemma 1. ◻

Proof. We first claim that \((G_F,\phi)\) does not contain a rainbow \(t\)-fan \(F_t\). Suppose, for contradiction, that \(G_F\) contains a rainbow \(F_t\). Since the complete bipartite graph \(K_{a,b}\) has no triangles, the rainbow \(F_t\) must contain at least \(t\) edges from the newly added matchings (i.e., the non-bipartite edges). However, these newly added edges use only \((t-1)\) distinct colors. This contradicts the definition of a rainbow subgraph (all edges must have distinct colors). Thus, \(G_F\) is a properly edge-colored graph without rainbow \(F_t\).

Next, we calculate the number of edges in \(G_F\). Clearly, \[\left\Vert G_F \right\Vert = ab+ (t-1) \left( \left\lfloor \frac{a}{2} \right\rfloor+ \left\lfloor \frac{b}{2} \right\rfloor \right).\] We analyze two cases based on the value of \(n \mod 4\).

\(n \not\equiv 2 \pmod{4}\).
Let \(|A| = \left\lfloor \frac{n}{2} \right\rfloor\) or \(|B| = \left\lceil \frac{n}{2} \right\rceil\), then \(b\geq a\geq 2t-1\) and at most one of \(a = \left\lfloor \frac{n}{2} \right\rfloor\) or \(b = \left\lceil \frac{n}{2} \right\rceil\) is odd,. For such \(n\), we have \[\left\lfloor \frac{1}{2}\left\lfloor \frac{n}{2} \right\rfloor \right\rfloor + \left\lfloor \frac{1}{2}\left\lceil \frac{n}{2} \right\rceil \right\rfloor = \left\lfloor \frac{n}{2} \right\rfloor.\] Substituting this into the edge count of \(G_F\) gives \[\left\Vert G_F \right\Vert = \left\lfloor \frac{n^2}{4} \right\rfloor + (t-1)\left\lfloor \frac{n}{2} \right\rfloor.\] Therefore, \[\text{ex}^*(n, F_t) \geq \left\lfloor \frac{n^2}{4} \right\rfloor + (t-1)\left\lfloor \frac{n}{2} \right\rfloor.\]

\(n \equiv 2 \pmod{4}\).
Let \(n = 4k + 2\) (\(k\geq t\)) for some integer \(k \geq 1\) and let \(a=2k\) and \(b=2k+2\), then \(b\geq a\geq2t-1\). Then \[\begin{align} \left\Vert G_F \right\Vert& =& 2k(2k+2) + (t-1)k + (t-1)(k+1)\\ & =& (2k+1)^2 - 1 + (t-1)(2k+1)\\ &=&\left\lfloor \frac{n^2}{4} \right\rfloor + (t-1)\left\lfloor \frac{n}{2} \right\rfloor-1. \end{align}\] Therefore, \[\text{ex}^*(n, F_t) \geq \left\lfloor \frac{n^2}{4} \right\rfloor + (t-1)\left\lfloor \frac{n}{2} \right\rfloor - 1.\]

Combining these two cases, we obtain that \[\text{ex}^*(n, F_t) \geq \left\lfloor \frac{n^2}{4} \right\rfloor + (t-1)\left\lfloor \frac{n}{2} \right\rfloor - \Delta(n)= f(n, t).\] ◻

Proof. We first claim that \(G_W\) contains no rainbow \(W_{2t}\). For clarity, we define the following: cross edges are the edges of the original complete bipartite graph, connecting vertices from different partitions \(A\) and \(B\); internal edges are the newly added edges, connecting vertices within the same partition \(A\) or \(B\).

Suppose for contradiction that \(G_W\) contains a rainbow \(W_{2t}\). Let \(x\) be the hub of this rainbow \(W_{2t}\); removing \(x\) from \(W_{2t}\) yields a rainbow \(2t\)-cycle \(C_{2t}\).

Without loss of generality, assume the hub \(x \in A\). Let \(r\) be the number of vertices of \(C_{2t}\) that lie in partition \(A\). Since all these \(r\) vertices are adjacent to \(x\) and \(d_A(x)\leq t-1\), we have \(r < t\). Thus, there are at most \(r\) internal edges between \(x\) and \(C_{2t}\). Next, analyze the \(2t\) edges of \(C_{2t}\): each cross edge has one endpoint in \(A\) (one of the \(r\) vertices) and one in \(B\). Since \(C_{2t}\) is a cycle, each vertex in \(A\) is adjacent to at most 2 edges of \(C_{2t}\). Thus the total number of cross edges in \(C_{2t}\) is at most \(2r\). Therefore, the number of internal edges in \(C_{2t}\) is at least \(2t - 2r\). In summary, the rainbow \(W_{2t}\) contains at least \((2t - 2r) + r = 2t - r>t\) internal edges. However, the internal edges of \(G_W\) are colored with only \(t\) distinct colors. Therefore, \(G_W\) does not contain a rainbow \(W_{2t}\).

Next, we calculate the number of edges in \(G_W\). To ensure that the graph \(G\) has exactly \(g(n)\) edges, we choose the sizes of parts \(A\) and \(B\) according to the residue of \(n\) modulo 4. If \(n \equiv 2 \pmod{4}\) (i.e., \(n = 4k + 2\) for some positive integer \(k\)), then set \(|A| = 2k + 2\) and \(|B| = 2k\); Otherwise set \(|A| = \left\lfloor \frac{n}{2} \right\rfloor\) and \(|B| = \left\lceil \frac{n}{2} \right\rceil\). We always have \(b\geq a\geq 2t-1\). Then the number of cross edges in \(G\) is \(|A| \cdot |B| = \left\lfloor \frac{n^2}{4} \right\rfloor-\Delta(n)\). Note that \(a+b=n\) and at least one of \(a\) and \(b\) is even. One can check directly that the total number of internal edges added to \(A\) and \(B\) is \[\left\lfloor \frac{(t-1)a}{2} \right\rfloor + \left\lfloor \frac{(t-1)b}{2} \right\rfloor=\left\lfloor \frac{(t-1)n}{2} \right\rfloor.\] Therefore, the total number of edges in \(G\) is exactly \(g(n)\). Since \(G\) is a properly edge-colored graph on \(n\) vertices with \(\left\Vert G \right\Vert = g(n)\) that contains no rainbow \(W_{2t}\). We conclude that for any \(W_{2t} \subseteq H \subseteq K_{1,s,t}\) \[\text{ex}^*(n, H)\ge \text{ex}^*(n, W_{2t}) \geq g(n).\] ◻

Proof. Since \(\left\Vert G \right\Vert \geq 2nt\), the average degree of \(G\) is \(d = \frac{2\left\Vert G \right\Vert}{n} \geq 4t\). We may assume \(\delta(G)\ge 2t\). Indeed, if there exists a vertex \(v \in G\) with \(d(v)< 2t\), then deleting \(v\) and all its incident edges yields a graph \(G'\) with average degree \[d' > \frac{2(\left\Vert G \right\Vert - 2t)}{n-1} \geq \frac{4nt - 4t}{n-1} = \frac{4t(n-1)}{n-1} = 4t.\] Repeating this deletion process eventually produces a subgraph of \(G\) with minimum degree at least \(2t\).

Note that for a properly edge-colored graph, the color degree of a vertex equals its degree. By Lemma 6, \(G\) contains a rainbow matching of size at least \(\left\lfloor \frac{\delta(G)}{2} \right\rfloor \geq t\). This completes the proof. ◻

Proof. Let \(H'\) be the graph obtained from \(F_t\) by deleting the common vertex of the triangles, i.e., \(H'\) is a matching of size \(t\). By Lemma 7, \(\text{ex}^*(n, H') \leq 2nt\). Apply Lemma 1 to \(H'\) with parameters \(M = 2t\) and \(s = 0\), and note that \(G\) is \(F_t\)-free, we obtain that:
(1). The number of triangles in \(G\) is at most \(\frac{16t}{3}\left\Vert G \right\Vert\);
(2). \(\left\Vert G \right\Vert \leq \frac{1}{4}n^2 + 2Mn^{1+s} = \frac{1}{4}n^2 + 4nt\). ◻

Proof. We construct a sequence of subgraphs by deleting vertices one by one: \(G = G_0 \supset G_1 \supset \dots \supset G_{n-m}\), where \(G_{i+1}\) is obtained by deleting a vertex \(v \in G_i\) if its degree in \(G_i\) is \(\leq 0.46|G_i|\).

We first show that the process stops when \(m > 150t\). Since \(G\) contains no rainbow \(F_t\), \(G_{n-m}\) also contains no rainbow \(F_t\). By Lemma 8, \(\left\Vert G_{n-m} \right\Vert \leq \frac{1}{4}m^2 + 4mt\). Thus \[\label{eq:e40G41} \frac{1}{4}m^2 + 4mt \geq \left\Vert G_{n-m} \right\Vert = \left\Vert G \right\Vert - \sum_{i=0}^{n-m-1} \left( \left\Vert G_i \right\Vert - \left\Vert G_{i+1} \right\Vert \right).\tag{1}\] Since we delete vertices with degree \(\leq 0.46|G_i|\), the sum of deleted edges satisfies \[\sum_{i=0}^{n-m-1} \left( \left\Vert G_i \right\Vert - \left\Vert G_{i+1} \right\Vert \right) \leq \sum_{i=0}^{n-m-1} 0.46(n-i) = 0.23(n+m+1)(n-m).\] Substituting \(\left\Vert G \right\Vert > f(n) \geq \frac{1}{4}n^2 - 1 + (t-1)\left\lfloor \frac{n}{2} \right\rfloor - 1\) (since \(\Delta(n)\leq 1\)) into inequality (1 ), we have \[\frac{1}{4}m^2 + 4mt \geq \left( \frac{1}{4}n^2 - 2 + (t-1)\left\lfloor \frac{n}{2} \right\rfloor \right) - 0.23(n+m+1)(n-m)\geq 0.02n^2 + 0.23m^2 .\] Thus \[0.02m^2 + 4mt > 0.02n^2> 0.02(230t)^2 = 1058t^2.\] Solving the quadratic inequality for \(m\), we obtain \[m > \frac{-4t + \sqrt{16t^2 + 4 \times 0.02 \times 1058t^2}}{2 \times 0.02} \approx 150.7t > 150t.\]

Next, we show that \(\left\Vert G_{n-m} \right\Vert > f(m)\). For \(k > 60\), the difference of \(f(k)\) satisfies \[f(k) - f(k-1) \geq \left( \frac{k^2}{4} - \frac{(k-1)^2}{4} - 1 \right) - 1 = 0.5k - 2.25 > 0.46k.\] Since \(\left\Vert G \right\Vert > f(n)\) and each deletion removes at most \(0.46|G_i|\) edges (from a vertex with degree \(\leq 0.46|G_i|\)), we can inductively prove \(\left\Vert G_i \right\Vert > f(|G_i|)\) for all \(0 \leq i \leq n-m\). In particular, \(\left\Vert G_{n-m} \right\Vert > f(m)\).

Setting \(G' = G_{n-m}\) completes the proof. ◻

Proof. Take \(t\) vertices \(y_1, y_2, \dots, y_t \in N(x)\) (or \(y_1, \dots, y_t \in A\) for case (2)) satisfying \(|N(y_i) \cap N(x)| \geq 6t\) (or \(|N(y_i) \cap (N(x) \setminus A)|\ge 5t\) for case (2)) for \(1 \leq i \leq t\). If we can sequentially select vertices \(z_1, z_2, \dots, z_t\) such that \(z_i \in N(x) \cap N(y_i)\) (or \(z_i \in N(y_i)\cap (N(x)\setminus A)\) for case (2)) for each \(i\) and the triangles \(xy_1z_1\), \(xy_2z_2\), \(\dots, xy_tz_t\) have pairwise distinct colors, then these \(t\) triangles form a rainbow \(F_t\) with center \(x\).

We now verify such \(z_i\)’s exist. When selecting \(z_{k+1} \in N(x) \cap N(y_{k+1})\) (or \(z_{k+1} \in N(y_{k+1})\cap (N(x)\setminus A)\)), the following constraints each eliminate at most a certain number of candidates:

• the edge \(xz_{k+1}\) must receive a color different from the colors of \(y_1z_1, \dots, y_kz_k\); this rules out at most \(k\) vertices;

• the edge \(y_{k+1}z_{k+1}\) must receive a color different from the colors of edges \(xy_1, \dots, xy_t\), \(xz_1, \dots, xz_k\), and \(y_1z_1, \dots, y_kz_k\), this rules out at most \(t + 2k\) vertices;

• \(z_{k+1}\) must be distinct from \(y_1, \dots, y_t\) and \(z_1, \dots, z_k\), excluding at most \(t + k\) vertices (in case (2), \(z_{k+1}\) are automatically distinct from \(y_1, \dots, y_t\) since \(z_{i}\in N(x)\setminus A\), and only \(z_1, \dots, z_k\) need to be avoided. Consequently, at most \(k\) vertices are excluded in this case).

Therefore, at most \(k + (t + 2k) + (t + k) = 2t + 4k\) (or \(k + (t + 2k) + k = t +4k\) for case (2)) vertices are removed from \(|N(x) \cap N(y_{k+1})|\) (or \(N(y_{k+1})\cap (N(x)\setminus A)\) for case (2)). Since \(k \leq t-1\), we have \(2t+4k\le 2t + 4(t-1) = 6t - 4 < 6t\le |N(x) \cap N(y_{k+1})|\) (or \(t+4k\le t + 4(t-1) = 5t - 4 < 5t\le |N(y_{k+1})\cap (N(x)\setminus A)|\) for case (2)). Thus at least one admissible vertex remains, proving that a suitable \(z_{k+1}\) exists.

This completes the proof. ◻

Proof. By Lemma 8, \(N(G, K_3)\le \frac{16t}{3}\left\Vert G \right\Vert\). For an edge \(e = xy\), define \(h(e) = n - |N(x) \cup N(y)|\) (the number of vertices not in \(N(x) \cup N(y)\)), and let \(h\) be the average value of \(h(e)\) over all \(e \in E(G)\). The number of triangles containing the edge \(e\) is \[|N(x) \cap N(y)| = d(x) + d(y) - |N(x) \cup N(y)| = d(x) + d(y) - (n - h(e)).\] Summing over all edges \(e \in E(G)\), we have \[3\cdot N(G, K_3) \geq \sum_{x \in G} d^2(x) - n\left\Vert G \right\Vert + \sum_{e \in E(G)} h(e).\] By the Cauchy-Schwarz inequality, \(\sum_{x \in G} d^2(x) \geq \frac{1}{n}\left( \sum_{x \in G} d(x) \right)^2 = \frac{4\left\Vert G \right\Vert^2}{n}\). Substituting \(N(G, K_3)\leq \frac{16t}{3}\left\Vert G \right\Vert\) into this inequality, we obtain \[3 \cdot \frac{16t}{3}\left\Vert G \right\Vert \geq \frac{4\left\Vert G \right\Vert^2}{n} - n\left\Vert G \right\Vert + h\left\Vert G \right\Vert.\] Dividing both sides by \(\left\Vert G \right\Vert\) (since \(\left\Vert G \right\Vert > 0\)) yields that \[16t \geq \frac{4\left\Vert G \right\Vert}{n} - n + h.\] Since \(\left\Vert G \right\Vert > f(n) \geq \frac{n^2}{4}\) (for \(t \geq 2\) and \(n > 0\)), we have \(\frac{4\left\Vert G \right\Vert}{n} - n > 0\). Consequently, \(h < 16t\). Therefore, there exists an edge \(e = xy\) with \(h(e) < 16t\), i.e., \(|N(x) \cup N(y)| > n - 16t\). This completes the proof. ◻

Proof. By Lemma 11, we can choose an edge \(e = x_0y_0\) with \(|N(x_0) \cup N(y_0)| > n - 16t\). Hence there are at most \(16t\) vertices outside of \(N(x_0) \cup N(y_0)\) in \(G\).

By Lemma 10 (1), \(N(x_0)\) contains at most \(t-1\) vertices \(y\) with \(|N(y) \cap N(x_0)| \geq 6t\); otherwise, \(G\) has a rainbow \(F_t\). Deleting these (at most \(t-1\)) vertices from \(N(x_0)\) gives \(A'_1 \subset N(x_0)\). Similarly, \(N(y_0)\) also has at most \(t-1\) vertices \(z\) with \(|N(z) \cap N(y_0)| \geq 6t\). Deleting these from \(N(y_0)\) yields \(A'_2 \subset N(y_0)\).

We claim \(A'_1 \cap A'_2 = \emptyset\). Suppose for contradiction that there exists \(z \in A'_1 \cap A'_2\). Then \[\begin{align} d(z) &=& |N(z) \cap N(x_0)| + |N(z) \cap N(y_0)| + |N(z) \cap (V(G) \setminus (N(x_0) \cup N(y_0)))| \\ &<& 6t + 6t + 16t = 28t. \end{align}\] Therefore, we have \(0.46n < d(z)<28t\). This contradicts to the assumption that \(n>150t\).

Moreover, \(|A'_1| \geq |N(x_0)| - (t-1) > 0.46n - t\) and \(|A'_2| \geq |N(y_0)| - (t-1) > 0.46n - t\). Hence the sizes of \(A_1'\) and \(A_2'\) satisfy the requirement of the statement (2).

Next, we show \(A_1'\) and \(A_2'\) satisfy the requirement of the statement (1). For any \(z \in A'_1\), \[\begin{align} |N(z) \cap A'_2|&=&|N(z)|-|N(z) \cap A'_1|-|N(z) \cap (V(G) \setminus (A'_1 \cup A'_2))|\\ &>& 0.46n - 6t - 18t\\ &=& 0.46n - 24t \\ &>& 0.3n, \end{align}\] where the second inequality holds since \(|N(z) \cap A'_1| \leq |N(z) \cap N(x)| < 6t\), and \(|V(G) \setminus (A'_1 \cup A'_2)| \leq 16t + 2(t-1) < 18t\); the last inequality holds since \(n > 150t\). The same holds for \(z \in A'_2\).

Finally, we extend \(A'_1\) and \(A'_2\) to be a partition of \(V(G)\). The number of vertices outside of \(A'_1 \cup A'_2\) is at most \(16t + 2(t-1) <18t\). For each \(z\notin A'_1 \cup A'_2\), we claim that there exists an \(i \in \{1,2\}\) such that \(|N(z) \cap A'_i| > 0.3n\), and thus we add \(z\) to \(A'_i\). Suppose for contradiction that \(|N(z) \cap A'_1| \leq 0.3n\) and \(|N(z) \cap A'_2| \leq 0.3n\). Set \(A = N(z) \cap A'_1\). Then \[|A| > |N(z)| - |N(z) \cap A'_2| - |V(G)\setminus (A'_1 \cup A'_2)| > 0.46n - 0.3n - 18t > t.\] For any \(u \in A\), \[\begin{align} |N(u) \cap (N(z) \setminus A)| &\geq& |N(u) \cap (N(z) \setminus A'_1)| \\ &= &|(N(u) \setminus A'_1) \cap (N(z) \setminus A'_1)|\\ &\geq& |N(u) \setminus A'_1| + |N(z) \setminus A'_1| - |V(G)\setminus A'_1|\\ & >& (0.46n - 6t) + 0.16n - (0.54n + t)\\ &=& 0.08n - 7t \\ &>& 5t, \end{align}\] where the forth inequality holds since \(|N(u) \setminus A'_1| > 0.46n - 6t\), \(|N(z) \setminus A'_1| > 0.46n - 0.3n = 0.16n\), and \(|V(G) \setminus A'_1| < n - (0.46n - t) = 0.54n + t\). By Lemma 10 (2), \(G\) contains a rainbow \(F_t\) with center \(z\), a contradiction. Therefore, by suitably placing each vertex outside \(A_1'\cup A_2'\) into either \(A'_1\) or \(A'_2\), we obtain a desired partition \(A_1, A_2\) of \(V(G)\). This completes the proof. ◻

Proof. For \(i=1,2\) and a vertex \(x \in A_i\), define the internal degree of \(x\) in \(A_i\) to be \(d'(x) = |N(x) \cap A_i|\). We consider two cases.

Without loss of generality, assume \(x \in A_1\) and \(y_1, y_2, \dots, y_t \in N(x) \cap A_1\). For each \(y_i \in \{y_1, \dots, y_t\}\), \[\begin{align} |N(x) \cap N(y_i)| &\geq& |N(x) \cap N(y_i) \cap A_2|\\ &\geq& |N(x) \cap A_2| + |N(y_i) \cap A_2| - |A_2|\\ &>& 0.3n + 0.3n - (0.54n + t)\\ &=& 0.06n - t\\ &>& 6t. \end{align}\] where the third inequality holds since \(|N(x) \cap A_2| > 0.3n\), \(|N(y_i) \cap A_2| > 0.3n\), and \(|A_2| < n - (0.46n - t) = 0.54n + t\), and the last inequality holds since \(n>150t\). By Lemma 10, \(G\) contains a rainbow \(F_t\) with center \(x\).

We first show there exists \(i \in \{1,2\}\) such that \(\left\Vert G[A_i] \right\Vert > (t-1)\left\lfloor \frac{|A_i|}{2} \right\rfloor\). Suppose for contradiction that \(\left\Vert G[A_1] \right\Vert \leq (t-1)\left\lfloor \frac{|A_1|}{2} \right\rfloor\) and \(\left\Vert G[A_2] \right\Vert \leq (t-1)\left\lfloor \frac{|A_2|}{2} \right\rfloor\). Then \[\left\Vert G \right\Vert \leq |A_1||A_2| + \left\Vert G[A_1] \right\Vert + \left\Vert G[A_2] \right\Vert \leq \left\lfloor \frac{n^2}{4} \right\rfloor + (t-1)\left( \left\lfloor \frac{|A_1|}{2} \right\rfloor + \left\lfloor \frac{|A_2|}{2} \right\rfloor \right).\] Since \(\left\Vert G \right\Vert > f(n) = \left\lfloor \frac{n^2}{4} \right\rfloor + (t-1)\left\lfloor \frac{n}{2} \right\rfloor - \Delta(n)\), we have \[\left\lfloor \frac{n^2}{4} \right\rfloor + (t-1)\left( \left\lfloor \frac{|A_1|}{2} \right\rfloor + \left\lfloor \frac{|A_2|}{2} \right\rfloor \right) > \left\lfloor \frac{n^2}{4} \right\rfloor + (t-1)\left\lfloor \frac{n}{2} \right\rfloor - \Delta(n).\] The only way to avoid a contradiction is \(\Delta(n)= 1\) and \(\left\lfloor \frac{|A_1|}{2} \right\rfloor + \left\lfloor \frac{|A_2|}{2} \right\rfloor = \left\lfloor \frac{n}{2} \right\rfloor\). However, \(\Delta(n)= 1\) implies \(n \equiv 2 \pmod{4}\). Suppose \(n = 4k + 2\). Then \(\left\lfloor \frac{n}{2} \right\rfloor = 2k + 1\). Given that \(|A_1| + |A_2| = 4k + 2\), \(|A_1||A_2| = \left\lfloor \frac{n^2}{4} \right\rfloor = (2k+1)^2 - 1\) implies \(|A_1| = |A_2| = 2k + 1\). But then \[\left\lfloor \frac{|A_1|}{2} \right\rfloor + \left\lfloor \frac{|A_2|}{2} \right\rfloor = k + k = 2k \neq 2k + 1 = \left\lfloor \frac{n}{2} \right\rfloor,\] a contradiction. Therefore, there exists an \(i \in \{1,2\}\) with \(\left\Vert G[A_i] \right\Vert > (t-1)\left\lfloor \frac{|A_i|}{2} \right\rfloor\); without loss of generality, assume \(i = 2\).

Let \(|A_1| = a\), \(|A_2| = b\), and \(N = |A_1||A_2| - e(A_1, A_2)\) (the number of non-edges between \(A_1\) and \(A_2\)). By the handshaking lemma, the sum of internal degrees satisfies \[\begin{align} \label{eqn:A1A2} \frac{1}{2}(t-1)n\geq\frac{1}{2}\sum_{x \in V(G)} d'(x) &=& \left\Vert G[A_1] \right\Vert + \left\Vert G[A_2] \right\Vert\nonumber\\ &=& \left\Vert G \right\Vert - e(A_1, A_2)\nonumber\\ &\geq& f(n)+1 - (|A_1||A_2| - N) \nonumber\\ &\geq&(t-1)\left\lfloor \frac{n}{2} \right\rfloor + N \\ &\geq&(t-1) \frac{n-1}{2}+N\nonumber, \end{align}\tag{2}\] where the forth inequality holds since \(f(n) = \left\lfloor \frac{n^2}{4} \right\rfloor + (t-1)\left\lfloor \frac{n}{2} \right\rfloor - \Delta(n)\) and \(|A_1||A_2| \leq \left\lfloor \frac{n^2}{4} \right\rfloor\). Consequently, we have \(N \leq \frac{t-1}{2}\).

Define \(C = \{x \in A_1 \mid e(x, A_2)<|A_2| \text{ and } d'(x) = t-1\}\) and \(D = \{x \in A_1 \mid e(x, A_2)=|A_2| \text{ and } d'(x) = t-1\}\). Let \(c=|C|\). Then \(c \leq N \leq \frac{t-1}{2}\). Let \(d=|D|\). We claim that \(d > 60t\). By the inequality (2 ), we have \(\left\Vert G[A_1] \right\Vert + \left\Vert G[A_2] \right\Vert \geq (t-1)\left\lfloor \frac{n}{2} \right\rfloor\). Since \(\left\Vert G[A_2] \right\Vert \leq (t-1)\frac{b}{2}\), we have \[\left\Vert G[A_1] \right\Vert \ge (t-1)\left( \left\lfloor \frac{n}{2} \right\rfloor - \frac{b}{2} \right) \geq (t-1)\frac{a-1}{2}.\] Summing \(d'(x)\) over all vertices of \(A_1 \setminus C\), we obtain \[\sum_{x \in A_1 \setminus C} d'(x) = \sum_{x \in A_1} d'(x) - \sum_{x \in C} d'(x) \geq 2\left\Vert G[A_1] \right\Vert - c(t-1) \ge (a-c-1)(t-1).\] On the other hand, \(\sum_{x \in A_1 \setminus C} d'(x) = \sum_{x \in D} d'(x) + \sum_{x \in A_1 \setminus (C \cup D)} d'(x) \leq (t-1)d + (t-2)(a - c - d)\). Consequently, we have \[(t-2)(a - c) + d \ge (a-c-1)(t-1)\] i.e., \(d\ge a - c - (t-1)\). Since \(a > 0.46n - t\), \(c \leq \frac{t-1}{2}\), and \(n > 150t\), we have \[d \ge 0.46 \cdot 150t - t - \frac{t-1}{2} - (t-1) > 69t - 2.5t = 66.5t > 60t.\]

We now show \(G\) contains a rainbow \(F_t\). Take a vertex \(x \in D\), let \(N(x) \cap A_1 = \{y_1, y_2, \dots, y_{t-1}\}\). By the assumption that \(\left\Vert G[A_2] \right\Vert > (t-1)\left\lfloor \frac{b}{2} \right\rfloor\) and each color in a properly edge-colored graph has at most \(\left\lfloor \frac{b}{2} \right\rfloor\) edges (no adjacent edges share the same color), \(G[A_2]\) contains at least \(t\) distinct colors. Thus there must exist a color \(c_0\) that is different from the color of every edge \(xy_1, xy_2, \dots, xy_{t-1}\). Pick an edge \(uv\) in \(A_2\) colored with \(c_0\).

Remove all vertices \(z\) in \(A_2\) satisfying the following conditions:

1. \(z = u\) or \(v\);

2. the end \(z\) of the edge \(xz\) with color \(c_0\) (there is at most one such vertex);

3. the ends \(z\) of the edges \(y_iz\) (for \(1\le i\le t-1\)) with colors different from those of the edges \(xu, xv, uv\) (there are at most \(3(t-1)\) such vertices \(z\)).

Let \(R\) be the set of vertices remaining in \(A_2\). Then \[|R| \geq b - (2 + 1 + 3(t-1)) > 0.46n - t - 3t > 65t.\] Since \(x\in D\), we have \(N(x)\cap A_2=A_2\). Consequently, \(N(x)\cap R=R\). Hence, for each \(y_i\) (\(1\le i\le t-1\)), \[|N(y_i)\cap N(x) \cap R| = |N(y_i) \cap R| \geq |R| - N > 65t - \frac{1}{2}(t-1) > 6(t-1).\] By Lemma 10 (1), the subgraph \(G[A_1\cup R]\) (also \(G\)) contains a rainbow \(F_{t-1}\) centered at \(x\), consisting of triangles \(\triangle xy_1z_1, \triangle xy_2z_2, \dots, \triangle xy_{t-1}z_{t-1}\) (with \(z_i \in R\)). By the construction of \(R\), all colors appearing in this fan are distinct from those of the triangle \(\triangle xuv\). Therefore, adding \(\triangle xuv\) to this fan yields a rainbow \(F_t\).

This completes the proof. ◻

Proof of Theorem 2:. By contradiction, suppose \(G\) is a properly edge-colored graph with \(|G| = n > 230t\), \(\left\Vert G \right\Vert > f(n)\), and no rainbow \(F_t\). By Lemma 8, \(G\) has a bounded number of edges and triangles. Furthermore, by Lemma 9, \(G\) contains a subgraph \(G'\) such that \(|G'| > 150t\), \(\left\Vert G' \right\Vert > f(|G'|)\), and \(\delta(G') > 0.46|G'|\). Then applying Lemma 12 to \(G'\), we obtain a partition \(V(G')=A_1 \cup A_2\) satisfying conditions (1) and (2). Finally, by Lemma 13, \(G'\) (and hence \(G\)) contains a rainbow \(F_t\), a contradiction. Therefore, we have \[\text{ex}^*(n, F_t) \leq f(n) = \left\lfloor \frac{n^2}{4} \right\rfloor + (t-1)\left\lfloor \frac{n}{2} \right\rfloor - \Delta(n).\] Combining with the lower bound (Lemma 4), we conclude that \(\text{ex}^*(n, F_t) = f(n)\) for \(n > 230t\).

This completes the proof of Theorem 2. ◻

Proof. For edge \(e\in E(G)\), let \(t(e)\) be the number of triangles containing \(e\) in \(G\).

For any triangle \(\triangle xyz\), summing \(t(xy) + t(xz) + t(yz)\) over all vertices \(u \in G\) gives: \[\begin{align} t(xy) + t(xz) + t(yz) &\geq&\sum_{u \in V(G)} \left( e(u, \{x,y,z\}) - 1 \right) \\ &= & d(x) + d(y) + d(z) - n\\ &>& 3\left(\frac{1}{2} - \alpha\right)n - n \\ &=& \left(\frac{1}{2} - 3\alpha\right)n. \end{align}\] where the third inequality holds since \(\delta(G)>(\frac{1}{2} - \alpha)n\). Consequently, at least one edge in \(\triangle xyz\) satisfies \(t(e) > \frac{1}{3}\cdot(\frac{1}{2} - 3\alpha)n = \left( \frac{1}{6} - \alpha \right)n\).

Delete all edges \(e\) with \(t(e) > \left( \frac{1}{6} - \alpha \right)n\) to obtain \(G_1\). Since each such edge belongs to at least \(\left( \frac{1}{6} - \alpha \right)n\) triangles, the number of deleted edges is at most \(\frac{3\beta n^3}{(\frac{1}{6} - \alpha)n} = \frac{18\beta n^2}{1 - 6\alpha}\). By Claim 1, \(G_1\) contains no triangles.

Next, delete vertices \(x \in V(G_1)\) with \(d_{G_1}(x) < (\frac{1}{2} - \varepsilon)n\) (where \(\varepsilon = 6\sqrt{\frac{\beta}{1 - 6\alpha}}+\alpha\)) to obtain \(G_2\). For each such deleted vertex, at least \((\frac{1}{2} - \alpha)n - (\frac{1}{2}- \varepsilon)n = (\varepsilon - \alpha)n\) edges were removed during the construction of \(G_1\). Consequently, the number of such deleted vertices is less than \[\frac{2 \cdot \frac{18\beta n^2}{1 - 6\alpha}}{(\varepsilon - \alpha)n} = 6\sqrt{\frac{\beta }{1 - 6\alpha}}n.\] For each vertex \(x \in V(G_2)\), \(d_{G_2}(x) > (\frac{1}{2} - \varepsilon)n - 6\sqrt{\frac{\beta }{1 - 6\alpha}}n>{(\frac 12 - \gamma)n}\).

Finally, we build \(B_1\) and \(B_2\). Take an edge \(e = xy \in E(G_2)\). Set \(B_1 = N_{G_2}(x)\) and \(B_2 = N_{G_2}(y)\). Then for each \(i=1,2\), \(|B_i| > (\frac{1}{2}-\gamma)n\) since \(\delta(G_2)>(\frac{1}{2}-\gamma)n\). Since \(G_2\) is triangle-free, \(B_1 \cap B_2 = \emptyset\). For each \(z \in B_i\), \(e(z, B_{3-i}) \geq d_G(z) - |G \setminus (B_1 \cup B_2)| > (\frac{1}{2} - \gamma)n - 2\gamma n = (\frac{1}{2} - 3\gamma)n\). ◻

Proof. Denote the three vertex parts of \(K_{1,t,s'}\) by \(\{x\}\) (called the center), \(B\) (of size \(t\)), and \(C\) (of size \(s'\)). Since \(K_{1,t,s'}\) is properly edge-colored, the edges connecting \(x\) and \(B\) use \(t\) distinct colors. Thus the number of vertices in \(C\) adjacent to \(B\) via edges whose colors belong to the set of \(t\) colors used by the edges from \(x\) to \(B\) is at most \(t^2\). Delete these \(t^2\) vertices from \(C\) to obtain \(C'\).

We now greedily select \(z_1, z_2, \dots, z_s\) from \(C'\) as follows. After choosing \(z_i\), we delete from the remaining \(C'\) all vertices that share any color on an edge from \(z_i\) to \(B \cup \{x\}\). This ensures that each subsequent vertex will have all its edge colors distinct from those of previously selected vertices. At each step, at most \((t + 1)^2\) vertices are removed, because each of the \(t + 1\) vertices in \(B \cup \{x\}\) is incident to at most \(t + 1\) vertices in \(C'\) via a given color. Since \(|C'| \geq s' - t^2 \geq (s - 1)(t + 1)^2 + 1\), we can continue until select all \(z_1, \dots, z_s\). Together with \(x\) and \(B\), these vertices form a rainbow \(K_{1,t,s}\). ◻

Proof. Similar as in the above lemma, let \(\{x\}\) (called the center), \(B\) (of size \(t\)), and \(C\) (of size \(s\)) be the three vertex parts of \(K_{1,t,s}\). Deleting the center \(x\) from \(K_{1,t,s}\) yields a complete bipartite graph \(K_{t,s}\). Keevash et al. [1] proved that \(\text{ex}^*(n, K_{t,s}) = O(n^{2 - \frac{1}{t}})\), so there exists a constant \(M\) such that \(\text{ex}^*(n, K_{t,s}) \leq M n^{2 - \frac{1}{t}}\).

For sufficiently large \(n\), \(\beta n^3 > \frac{8}{3}M n^{3 - \frac{1}{t}} > \frac{8}{3}M \left\Vert G \right\Vert n^{1 - \frac{1}{t}}\). By Lemma 1 \(G\) contains a rainbow \(K_{1,t,s}\). ◻

Proof. Since \(0 < \alpha \ll \gamma\), we choose \(\beta\) small enough to satisfy Lemma 15. By Lemma 17, \(G\) has fewer than \(\beta n^3\) triangles (otherwise, \(G\) contains a rainbow \(K_{1,t,s}\), a contradiction). Thus, by Lemma 15, \(G\) contains two disjoint subsets \(B_1, B_2 \subset V(G)\) satisfying that \(|B_i| > (\frac{1}{2}-\gamma)n\) and \(e(x, B_{3-i}) > (\frac{1}{2}- 3\gamma)n\) for each \(i\in\{1,2\}\) and every \(x\in B_i\).

We expand \((B_1, B_2)\) to a bipartition \((A_1, A_2)\) of \(V(G)\). For any \(x \notin B_1 \cup B_2\), assume \(e(x, B_1) \geq e(x, B_2)\) (the other case is symmetric). Then \[\begin{align} e(x, B_1) &\geq& \frac{1}{2}\left( d(x) - |V(G)\setminus (B_1 \cup B_2)| \right)\\ &>& \frac{1}{2}\left( \big(\frac{1}{2}-\alpha\big)n - 2\gamma n \right)\\ &=& \left( \frac{1}{4} - \frac{\alpha}{2} - \gamma \right)n > t. \end{align}\] Take \(t\) vertices \(C \subset N(x) \cap B_1\). Since each vertex in \(B_1\) has at most \(4\gamma n\) non-neighbors in \(B_2\), there are at most \(4\gamma t n\) vertices in \(B_2\) that are non-adjacent to \(C\). If \(e(x, B_2) - 4\gamma t n \ge s' = t^2 + (s - 1)(t + 1)^2 + 1\), then \(G\) contains a copy of \(K_{1,t,s'}\). By Lemma 16, \(G\) contains a rainbow \(K_{1,t,s}\), a contradiction. Therefore, \(e(x, B_2) - 4\gamma t n < s'\). Consequently, \[\begin{align} e(x, B_1) &\geq& d(x) - |V(G)\setminus (B_1 \cup B_2)| - e(x, B_2)\\ &>& \left(\frac{1}{2} - \alpha\right)n - 2\gamma n - s' - 4\gamma t n\\ &>& \left(\frac{1}{2} - \delta\right)n. \end{align}\] Adding \(x\) to \(A_1\) preserves the partition conditions. Repeating this process for all such \(x\) yields \(A_1, A_2\) that satisfy the conditions of Lemma 18. ◻

Proof. By Remark A, \(g(n)\) is the maximum number of edges in an \(n\)-vertex graph with a bipartition where every vertex has internal degree \(\leq t-1\). Since \(\left\Vert G \right\Vert > g(n)\), \(G\) has at least one vertex \(x\) with internal degree \(\geq t\). Without loss of generality, assume \(x \in A_1\). Suppose \(y_1, \dots, y_t \in N(x) \cap A_1\). Since \(e(y, A_2) > (\frac{1}{2} - \delta)n\) for each vertex \(y\in A_1\) and \(|A_2| < (\frac{1}{2} + \gamma)n\), each vertex in \(A_1\) has at most \((\gamma + \delta)n\) non-neighbors in \(A_2\). Thus \(A_2\) has at most \((\gamma + \delta)(t + 1)n\) vertices non-adjacent to \(\{x, y_1, \dots, y_t\}\). Therefore, for sufficiently large \(n\), the number of vertices in \(A_2\) adjacent to all of \(\{x, y_1, \dots, y_t\}\) is at least \[|A_2| - (\gamma + \delta)(t + 1)n > (\frac{1}{2} - \gamma)n - (\gamma + \delta)(t + 1)n \geq s' = t^2 + (s - 1)(t + 1)^2 + 1.\] Consequently, \(G\) contains a properly edge-colored \(K_{1,t,s'}\). By Lemma 16, this \(K_{1,t,s'}\) (thus \(G\)) contains a rainbow \(K_{1,t,s}\). ◻