A graph-theoretic rhombus consists of two triangles in a graph sharing an edge. Every rhombus-free simple graph on vertices has at most
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 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.
The triangular prism has six vertices and nine edges. Each edge lies in at most one triangle, so it has no rhombus; its two triangles show that it is not .
This is the prism graph built from two triangles.

Articles by others on the same topic (0)

There are currently no matching articles.