Laman graph

Remarks

Example: the complete graph $K_4$ minus one edge has $4$ vertices and $5 = 2 \cdot 4 - 3$ edges. Each $3$-vertex subset spans at most $3$ edges, and each pair spans at most $1$ edge, so condition 2 holds.

Non-example: two triangles that share one vertex have $5$ vertices and $6$ edges, but $2 \cdot 5 - 3 = 7$, so condition 1 fails. Such a framework in the plane can rotate one triangle about the shared vertex.

Laman's theorem concerns a generic placement of the vertices in $\R^2$. It states that $G$ is a Laman graph if and only if this framework is rigid and becomes flexible when any edge is removed. Hilda Pollaczek-Geiringer found this result earlier, so it is also called the Geiringer–Laman theorem.