= Rhombus-free edge bound
A graph-theoretic rhombus consists of two <triangles in a graph> sharing an <edge>. Every rhombus-free <simple graph> on $n\geq4$ vertices has at most
$$
\left\lfloor\frac{n^2}{4}\right\rfloor
$$
edges, attained by the balanced <complete bipartite graph>. A <triangle-free graph> satisfies this by <Mantel theorem>. If a triangle is present, each vertex outside it has at most one neighbour in it: two neighbours would form another triangle sharing an edge.
For $n=4,5$ this gives at most $4,6$ edges. For $n=6$, the remaining three vertices either have at most two edges, giving at most $3+3+2=8$, or form a second triangle. In the latter case the edges between the triangles form a <matching>, so there are at most nine edges. For $n\geq7$, remove a triangle and apply induction to the remaining $n-3\geq4$ vertices. The edge count is at most $\lfloor(n-3)^2/4\rfloor+n\leq\lfloor n^2/4\rfloor$. Checking the small bases avoids applying the asserted bound to a three-vertex triangle, where it is false.
Back to article page