If a room's floor plan has a five-sided room, you can always snap a chalk line across it to split it into two triangular rooms without adding any new doors on the outside — you only add one interior wall (an edge) and gain one extra room (a face). Doing this to every non-triangular face never changes the running total , because the one new edge and one new face cancel each other out.
If some face of the planar graph has four or more sides, draw a diagonal splitting it into two smaller faces. This adds exactly one new edge and one new face while leaving every vertex untouched, so it changes by and by and leaves exactly as it was. Repeating this for every non-triangular face — always possible for a polygon with at least four sides — turns the whole graph into a triangulation without ever changing .
- Triangulation
- A way of splitting every face of a planar graph into triangles by drawing diagonals, without adding new vertices.