Question I found in one of the previous year's exam:
Let $G$ a connected graph on $n \geq 3$ vertices, such that every edge participates in at least one triangle. Prove that $|E(G)| \geq \dfrac{3(n-1)}{2}$.
I tried proving using Turan's theorem on $\overline{G}$, but I get a less tight bound – $|E(G)| > \dfrac{3(n-2)}{4}$.
Using induction I'm getting nowhere as well; here it seems like I need to break the problem to $n$ odd and even, as it gives different number of edges. And even then, I don't know which edge/vertex to contract/delete.
Is it more straightforward than that?
Thanks in advance.
Best Answer
The assumption that $G$ is connected is crucial.
Otherwise, consider a graph of $6$ vertices which is composed of $2$ disjoint triangles.
Also, it is not true that $\overline{G}$ needs to be triangle free (all you need is an independent set of size $3$ in $G$).
A proof by induction actually works.
Base cases
$n=3,4$ are easily verified.
Induction step
Suppose we are given a graph $G$ with $n \ge 5$ vertices. Let $e = |E(G)|$.
Now if every vertex of $G$ had degree $\ge 3$, then we are done, as $2e \ge 3n$.
So assume there is a vertex $a$ of degree exactly $2$. (Why not $0$ or $1$?).
Let $b,c$ be the neighbours of $a$. Note that $\{b,c\}$ is an edge in $G$ (Why?)
Consider two cases:
Case 1) The edge $\{b,c\}$ is a part of a triangle other than $abc$.
In which case, we delete $a$ from $G$ to give a new graph $G'$ of $n-1$ vertices, satisfying the induction hypothesis.
Thus we get $e-2 \ge 3(n-2)/2$ and so $e \ge (3n - 2)/2 \gt 3(n-1)/2$ and so we are done.
Case 2) The edge $\{b,c\}$ is not part of any other triangle.
In this case, we delete the vertex $a$ and the edge $\{b,c\}$ to get a new graph $G'$.
Now it is possible that $G'$ is disconnected due to deletion of edge $\{b,c\}$. Since $G$ was connected, $G'$ has no more than two connected components, and we can try and apply the induction step to each connected component if each component has at least two vertices.
Thus if $n_1$ and $n_2$ (with $n_1 \ge 2$ and $n_2 \ge 2$) are the number of vertices in each connected component, we have that,
$e - 3 \ge 3(n_1 - 1)/2 + 3(n_2 -1)/2 = 3(n-3)/2$
Thus
$e \ge 3(n-1)/2$
and we are done.
If one of $n_1$, $n_2$ is $0$ or $1$, we can ignore that component and the above inequality still holds.