Rhombus-free edge bound
ID: rhombus-free-edge-bound
A graph-theoretic rhombus consists of two triangles in a graph sharing an edge. Every rhombus-free simple graph on vertices has at mostedges, 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 this gives at most edges. For , the remaining three vertices either have at most two edges, giving at most , 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 , remove a triangle and apply induction to the remaining vertices. The edge count is at most . Checking the small bases avoids applying the asserted bound to a three-vertex triangle, where it is false.
New to topics? Read the docs here!