K5 is the complete graph with five vertices: every pair of distinct vertices is joined by an edge, producing 10 simple edges. In planarity problems, it is a fundamental obstruction: no drawing places all edges without crossings, while deleting an edge makes the resulting graph planar. section 15.2.1 section 15.2.3
Use K5 as a concrete test case when implementing or explaining planarity testing:
- Recognize a possible K5 by checking for exactly five vertices and exactly ten simple edges; this count is sufficient for the simple graph considered by the predicate. section 15.2.3
- Treat K5 alongside K3,3 as a Kuratowski obstruction: encountering either graph provides a non-planarity result in the recursive test. section 15.2.1 section 15.2.3
- Use edge deletion to understand minimality: removing an edge from K5 eliminates the crossing in an appropriate embedding, and symmetry makes the choice of edge irrelevant. section 15.2.1
Comparing K5 with K4
A naive drawing of K4 may appear to contain crossing edges, but moving one vertex produces a planar embedding. K5 remains non-planar; deleting one edge reduces it to a planar graph. section 15.2.1
