ON THE MAXIMAL NUMBER OF TRIANGLES WITH A COMMON EDGE

Abstract

$\\ \S 1$ Let $G=(V,E)$ be a graph, $|V|=n,|E|=e,T$ is set of triangles in $G,|T|=t$, and $q$ is the number of tetrahedrons in $G$. For a vertex $v$ we denote by $A(v)$ the set of its neighbours, so that $d(v)=|A(v)|$ is the degree of $v$. Put $t[u, v] = |A(u) \cap A(v)|, t[u,v] = |V/A(u) \cup A(v))| , \overline{t}=\sum_{[u,v] \in E} \overline{t}[u,v]$ Put also $q[u, v, w] = |A(u) \cap A(v) \cap A(w)|$, $\overline{q}[u, v, w]= |V/ A(u) \cup A(v) \cup A(w)| $, $\overline{q}=\sum \overline{q}[u, v, w], \hat{t}=max \{ t[u,v]|[u,v] \in E \}$ Theorem1. For any graph $G$ we have the inequality (15) $(3t+\overline{t}) \hat{t} \geq nt$ and the equality holds iff $q = \overline{q} = 0$ and $t[u,v]$ is the same for all $[u, v] \in E$, such that $t[u,v]+\overline{t[u,v]} > 0$. There is another proof of (14) in [2]. For $n \equiv 0 $ (mod 6) and $n \equiv 0 $ (mod 9) two extremal graphs (i.e. graphs for which the equality in (14) holds) are constructed. The following two consequences are deduced from (14): Corollary 1. If (20) $\sum_{v \in V} d^2(v) > ne$ then (21) $\hat{t} > \frac{n}{6}$ Corollary 2. If $t > 0$ and (22) $\sum_{v \in V} d^2(v) \geq ne$ then (23) $\hat{t} \geq \frac{n}{6}$ $\\ \S 2$ Lemma 1. The inequality (25) $e \hat{t} \geq \sum_{v \in V} d^2(v)-ne$ is true and the equality holds if $G$ is a complete r-partite graph and $G$ is regular in addition for $r \geq 3$ Lemma 2. The inequality (26) $\hat{t} \geq \frac{4e}{n}-n$ is true and the equality holds iff $G$ is a regular complete $r$-partite graph with $r \geq 2$. By applying Lemmas I and 2 the following Theorem is proved: Theorem 2. If (30) $e \geq \frac{r-1}{2r}n^2$ then (31) $\hat{t} \geq \frac{r-2}{r} n$ and the equality holds in (31) if $2 \leq r|n$ and $G$ is a regular complete $r$-partite graph. Lemma 4. If (32) $e \geq \Bigg[ \frac{n^2}{4} \Bigg]$ then (33) $\sum_{v \in V} d^2(v) \ geq ne$ and if (32) is strict, then (33) is strict also. From Corollary 1 and Lemma 4 we obtain: Corollary 3. If $e > \Bigg[ \frac{n^2}{4} \Bigg]$ then $\hat{t} > \frac{n}{6}$. This corollary is obtained in [2]. It gives a positive solution on the following Erdos' conjecture. If $e > \frac{n^2}{4}$,then $\hat{t} \geq \frac{n}{6}$. Closely connected with Corollary 3 is the following assertion, proved in [2], which is immediately deduced from Corollary 2 and Lemma 4. Corollary 4. If $e \geq \Bigg[ \frac{n^2}{4} \Bigg]$ and $t > 0$,then $\hat{t} \geq \frac{n}{6}$ Put $\hat{t}(n)=min\Bigg\{ \hat{t}(G)|e(G) \geq \Bigg[\frac{n^2}{4} \Bigg], t(G) > 0 |\Bigg\}$ The conclusion in Corollary 4 cannot be improved under the assumption of this corollary, since from it and by using appropriate examples we obtain: Corollary 5. For each $n (n \geq 4)$ we have (35) $\hat{t}(n) = \Bigg] \frac{n}{6} \Bigg[$ Note. $]x[=min\{k|k \in N, k \geq x\}$ ¶3. From Theorem 1 we obtain: Theorem 3. If $\hat{t} \geq \frac{n}{6}$,then (38) $\hat{t} \geq \frac{1}{2e} \sum_{v \in V} d^2(v)-\frac{n}{3}$ From Corollary 2 and Theorem 3 we obtain: Corollary 6. If $\sum_{v \in V} d^2(v) \ geq ne$ and $t > 0$, then (38) holds. vEV From Corollary 4 and Corollar 6 we obtain: Corallary7. If $e \geq \Bigg[ \frac{n^2}{4}\Bigg]$ and $t > 0$, then (38) holds. Corollary 7 confirms an Edwards' conjecture, given in added note of [3]. Since Corollary 7 is easily deduced from Theorem 3, we can say that the Edwards' conjecture is a consequence of Erdos' one. The contrary is also true since if the assumptions of Corollary 7 are satisfied, then by Lemma 4 we have $\sum_{v \in V} d^2(v) \geq ne$ (38) implies $\hat{t} \geq \frac{n}{6}$ Finally, the Erdos' and Edwards' conjectures are equivalent. In $\\ \S 3$ a detailed analysis of Edwards' paper [3] is done also. It is shown that the essential assertions in this paper are trivial consequences of the inclusion-exclusion principle for two or three sets and have nothing to do with the solution of Erdos' conjecture.