A graph-theoretic rhombus is two triangles sharing an edge. Every rhombus-free graph on vertices has at mostedges. If the graph is triangle-free this is Turán's theorem. Otherwise remove a triangle: every remaining vertex has at most one neighbor in it, and induction bounds the edge count by
.
.
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 .
Articles by others on the same topic
There are currently no matching articles.