A complete graph connects every pair of distinct vertices with exactly one edge. Because loops are excluded, a graph with n vertices has n(n−1)/2 edges, the maximum for a simple graph. The notation Kₙ records its number of vertices. section 15.1.2
Use these properties when modeling or checking a graph:
- Treat K₅ as a standard example of a non-planar complete graph and as one of the forbidden graphs in Kuratowski’s characterization. section 15.1.1
- Expect quadratic growth: adding vertices rapidly increases the number of edges and makes drawings increasingly difficult to route without crossings. section 15.1.2 section 15.3.1
- Distinguish complete graphs from complete bipartite graphs, which connect every vertex across two partitions but never within one partition. section 15.1.2
K₆ and graph drawing
K₆ contains 6·5/2 = 15 edges. A naïve embedding produces 15 crossing pairs, whereas a minimum-crossing embedding has 3 intersections, showing why layout quality matters separately from graph completeness. section 15.1.2
