Induction

Question

Prove that the number of edges in a graph with exactly one triangle is at most \begin{align*}
\frac{\left( n - 1 \right )^2}{4} + 2
\end{align*}

Answer 1

A simple graph with no triangles can contain maximum edges if it contains cycles of 4 edges between vertices.

Making graph a complete bipartite graph. Maximum number of edges in a bipartite graph with n vertices = $\large \left \lfloor \frac{n^2}{4} \right \rfloor$

Now mentioned in the question that every graph must contain exactly one triangle.

Assuming a graph with n vertices.

$n-1$ vertices can be connected with maximum $\large \left \lfloor \frac{(n-1)^{2}}{4} \right \rfloor$
edges.

and for forming a triangle the remaining vertex can connect to any 2 adjacent vertices making maximum edges = $\large \left \lfloor \frac{(n-1)^{2}}{4} \right \rfloor + 2 $

Note: We can prove this by contradiction, assuming there exist a graph with exactly one triangle with edges > $\large \left \lfloor \frac{(n-1)^{2}}{4} \right \rfloor + 2 $ and then proving it wrong by above explanation. Most graph theory proofs can be proved with contradiction easily.

Comments

Nicelly explained.