Rainbow triangles sharing one common vertex or edge¹¹1BN was partially supported by NSFC (No. 11971346).

In 1907, Mantel [28] proved that every triangle-free graph on $n$ vertices has size at most $\lfloor\frac{n^{2}}{4}\rfloor$. Rademacher (see [12, pp.91]) showed that there are indeed at least $\lfloor\frac{n}{2}\rfloor$ triangles in a graph $G$ on $n$ vertices and at least $\frac{n^{2}}{4}+1$ edges but not only one triangle. The $k$-fan (usually called friendship graph), denoted by $F_{k}$, is a graph which consists of $k$ triangles sharing a common vertex. The book $B_{k}$ is a graph which consists of $k$ triangles sharing a common edge. Erdős [11] extended Mantel’s theorem and conjectured that there is a $B_{\lceil\frac{n}{6}\rceil}$ in $G$ if $e(G)>\frac{n^{2}}{4}$, which was later confirmed by Edwards in an unpublished manuscript [9] and independently by Khadžiivanov and Nikiforov [23]. Erdős, Füredi, Gould, and Gunderson [12] also studied Turán numbers of $F_{k}$, and proved that $ex(n,F_{k})=\lfloor\frac{n^{2}}{4}\rfloor+k^{2}-k$ if $k$ is odd; and $ex(n,F_{k})=\lfloor\frac{n^{2}}{4}\rfloor+k^{2}-\frac{3k}{2}$ if $k$ is even, for $n\geq 50k^{2}$. These results immediately imply the fact that every graph on $n$ vertices with minimum degree at least $\frac{n+1}{2}$ contains a $B_{k}$ for $n\geq 6k$ and also a $F_{k}$ for $n\geq 50k^{2}$. In this paper, we consider edge-colored versions of these extremal problems.

A subgraph of an edge-colored graph is properly colored (rainbow) if every two adjacent edges (all edges) have pairwise different colors. The rainbow and properly-colored subgraphs have been shown closely related to many graph properties and other topics, such as classical stability results on Turán functions [29], Bermond-Thomassen Conjecture [16], and Caccetta-Häggkvist Conjecture [1], etc. For more rainbow and properly-colored subgraphs under Dirac-type color degree conditions, we refer to [17, 18, 10, 6, 8].

The study of rainbow triangles has a rich history, and there are many classical open problems on them. In some classical problems, the host graph is complete. One conjecture due to Erdős and Sós [14] asserts that the maximum number of rainbow triangles in a 3-edge-coloring of the complete graph $K_{n}$, denoted by $F(n)$, satisfied that $F(n)=F(a)+F(b)+F(c)+F(d)+abc+abd+acd+bcd$, where $a+b+c+d=n$ and $a,b,c,d$ are as equal as possible. By using Flag Algebra, Balogh et al. [2] confirmed this conjecture for $n$ sufficiently large and $n=4^{k}$ for any $k\geq 1$. The other example is a recent conjecture by Aharoni (see [1]), which can imply Caccetta-Häggkvist Conjecture [5], a big and fundamental open problem in digraph. The conjecture says that given any positive integer $r$, if $G$ is an $n$-vertex edge-colored graph with $n$ color classes, each of size at least $n/r$, then $G$ contains a rainbow cycle of length at most $r$. For more recent developments on Aharoni’s conjecture, we refer to the work [7, 20, 21] and more references therein. A special case of Aharoni’s conjecture is about rainbow triangles. The relationship between directed triangles and rainbow triangles has been extensively used before (see [27, 24, 25]).

We would like to introduce a construction from Li [24]. Suppose that $D$ is an $n$-vertex digraph satisfying out-degree of every vertex is at least $n/3$. Let $V(D)=\{v_{1},v_{2},\ldots,v_{n}\}$. We construct an edge-colored graph $G$ such that: $V(G)=V(D)$; for each arc $v_{i}v_{j}\in A(D)$, we color the edge $v_{i}v_{j}$ with the color $j$. In this way, the number of colors appearing on edges incident with $v_{i}$ different from $i$ equals to $d^{+}_{D}(v_{i})$. Thus, finding a directed triangle in $D$ is equivalent to finding a rainbow triangle in such an edge-colored graph. More importantly for us, the idea of constructing the auxiliary digraph will also be an important constitution for our proofs in this paper.

Our theme of this paper is closely related to the color degree conditions for rainbow triangles. Let $G$ be an edge-colored graph. For every vertex $v\in V(G)$, the color degree of $v$, denoted by $d^{c}_{G}(v)$, is the number of distinct colors appearing on the edges which are incident to $v$. The minimum color degree of $G$, denoted by $\delta^{c}(G)$ (or in short, $\delta^{c}$), equals to $\min\{d^{c}(v):v\in V(G)\}$. It is an easy observation that every graph on $n$ vertices contains a triangle if minimum degree is at least $\frac{n+1}{2}$. H. Li and Wang [27] considered a rainbow version and conjectured that the minimum color degree condition $\delta^{c}(G)\geq\frac{n+1}{2}$ ensures the existence of a rainbow triangle in $G$. This conjecture was confirmed by H. Li [24] in 2013.

Independently, B. Li, Ning, Xu and Zhang [25] proved a weaker condition $\sum_{v\in V(G)}d^{c}(v)\geq\frac{n(n+1)}{2}$ suffices for the existence of rainbow triangles, and moreover, characterized the exceptional graphs under the condition $\delta^{c}(G)\geq\frac{n}{2}$. Very recently, X. Li, Ning, Shi and Zhang [26] proved a counting version of Theorem 1, i.e., there are at least $\frac{1}{6}\delta^{c}(G)(2\delta^{c}(G)-n)n$ rainbow triangles in an edge-colored graph $G$, which is best possible.

Hu, Li and Yang [22] proposed the following conjecture: Let $G$ be an edge-colored graph on $n\geq 3k$ vertices. If $\delta^{c}\geq\frac{n+k}{2}$ then $G$ contains $k$ vertex-disjoint rainbow triangles. Besides the work on Turán numbers of books and $k$-fans mentioned before, our another motivation is to study the converse of Hu-Li-Yang’s conjecture, i.e., rainbow triangles sharing vertices or edges. As the selections for us, we shall study the existence of rainbow triangles sharing one common vertex or an edge under color degree conditions, in views of the famous books and friendship graphs in graph theory.

Our original result is the following one which improves Li’s theorem. Indeed, we can go farther.

This paper is organized as follows. In Section 2, we will list our main theorems. In Section 3, we introduce some necessary notations and terminology and prove some lemmas. In Section 4, we prove general versions of Theorem 2, i.e., Theorems 3 and 4. We conclude this paper with some more discussions on the sharpness of our results, together some propositions on $F_{k}$ and $B_{k}$ on uncolored graphs.

Our main results are given as follows.

Setting $\delta^{c}(G)=\frac{n+k-1}{2}$ in Theorem 3, the following example shows that the bound “$n\geq 3k-2$” is sharp. Furthermore, it follows from Example 1 that the tight color degree should be at least $\delta^{c}\geq\frac{n+k}{2}$ when $n\leq 3k-3$.

The main novelty of our proof of Theorem 3 is a combination of the recent new technique for finding rainbow cycles due to Czygrinow, Molla, Nagle, and Oursler [6] and some recent counting technique from [26]. In particular, Czygrinow et al. [6] extended H. Li’s theorem by proving that for every integer $\ell$, every edge-colored graph $G$ on $n\geq 432\ell$ many vertices satisfying $\delta^{c}(G)\geq\frac{n+1}{2}$ admits a rainbow $\ell$-cycle $C_{\ell}$. One novel concept introduced in [6] is called restriction color, and it will be used in our proof. The proof of Theorem 4 is with the aid of the machine implicitly in the work of Turán number for matching numbers due to Erdős and Gallai [13]. (For details, see the proof of Lemma 13.)

Meantime, both Theorem 3 and Theorem 4 improve Theorem 1 (by setting $k=2$). On the other hand, Theorem 4 slightly improves Theorem 9 in [26] by a different method.

Some of our notations come from [6, 26]. Let $G$ be an edge-colored graph. Let $\mathcal{C}:E(G)\rightarrow\{1,2,\ldots,k\}$ be an edge-coloring of $G$. For a color $\alpha\in\mathcal{C}(G)$ and a vertex $v\in V(G)$, define the $\alpha$-neighborhood of $v$ as

$$N_{\alpha}(v)=\{u\in N(v)\mid c(uv)=\alpha\},$$

$\alpha$-neighborhood in $X$ of $v$ as

$$N_{\alpha}(v,X)=\{u\in N(v)\cap X\mid c(uv)=\alpha\}$$

where $X\subseteq V(G)$, and $N(v)$ is the neighborhood of $v$ in $G$. Define

$$N_{!}(v)=\bigcup_{\alpha\in\mathcal{C}(G)}\{N_{\alpha}(v)\mid|N_{\alpha}(v)|=1\}.$$

For the sake of simplicity, let $d_{\alpha}(v)=|N_{\alpha}(v)|$ and $d_{\alpha}(v,X)=|N_{\alpha}(v,X)|$. Moreover, let $N[v]=N(v)\cup\{v\}$. The monochromatic degree of $v$, denoted by $d^{mon}(v)$, is the maximum number of edges incident to $v$ colored with a same color (i.e., $d^{mon}(v)=\text{max}\{d_{\alpha}(v)\mid\alpha\in\mathcal{C}(G)\}$.) For a graph $G$, we denote the monochromatic degree of $G$ by $\Delta^{mon}(G)=\text{max}\{d^{mon}(v)\mid v\in V(G)\}$.

W.l.o.g., assume that $d_{1}(v)\geq d_{2}(v)\geq\cdots\geq d_{s}(v)$ and $s:=s(v)=d^{c}(v)$ for each vertex $v\in V(G)$. (When there is no danger of ambiguity, we use $s$ for short.)

The following concept of restriction was firstly introduced in [6, Section 3].

Denote by $rt(v)$ the number of rainbow triangles containing $v$; by $rt(v,x)$ the number of rainbow triangles containing both $v$ and $x$ (i.e., containing the edge $vx$); and $rt(v,X)=\sum_{x\in X}rt(v,x)$.

According to the definition of restriction color, we have the following proposition.

The form of the following lemma is motivated by [26], but its proof is a mixture of techniques from [6, 26]. For the sake of simplicity, define the color set $\mathcal{C}(G)=\{1,2,\cdots,c(G)\}$.

Note that $|Y_{i}|=d(v)-d_{i}=\sum_{1\leq j\leq s}d_{j}-d_{i}=d^{c}(v)+\sum_{1\leq j\leq s}(d_{j}-1)-d_{i}$. Combining Ineqs (1) and (2), we can get that

		$\displaystyle\sum_{x\in X_{i}}\sigma_{v,Y_{i}}(x)$
	$\displaystyle\geq$	$\displaystyle\sum_{x\in X_{i}}\Big{(}d^{c}(x)+|Y_{i}|+1-n\Big{)}-\sum_{y\in N_{!}(v)}d_{c(vy)}(y,X_{i})$
	$\displaystyle\geq$	$\displaystyle\sum_{x\in X_{i}}\Big{(}d^{c}(x)+d^{c}(v)+\sum_{1\leq j\leq s}(d_{j}-1)-d_{i}+1-n\Big{)}-\sum_{y\in N_{!}(v)}d_{c(vy)}(y,X_{i})$
	$\displaystyle\geq$	$\displaystyle\sum_{x\in X_{i}}\Big{(}d^{c}(x)+d^{c}(v)-n\Big{)}+d_{i}\Big{(}\sum_{1\leq j\leq s}(d_{j}-1)\Big{)}-d_{i}\big{(}d_{i}-1\big{)}-\sum_{y\in N_{!}(v)}d_{c(vy)}(y,X_{i}).$

The proof is complete. $\hfill\blacksquare$

Since $rt(v)\geq\frac{1}{2}\sum_{1\leq i\leq d^{c}(v)}rt(v,N_{i}(v))$, we have the following corollary.