A complete bipartite graph separates its vertices into two disjoint groups, A and B. Vertices connect only across the groups, and every vertex in A connects to every vertex in B. Loops and within-group edges are excluded. section 15.1.2
Write Kₙ,ₘ for partitions containing n and m vertices. The graph has exactly n·m edges, making the partition sizes a direct way to estimate its storage and drawing cost. section 15.1.2
Use these structural properties when modeling or testing graphs:
- Check that no edge joins two vertices in the same partition. section 15.1.2
- Generate every cross-partition pair to construct the graph; this produces n·m edges. section 15.1.2
- Recognize K₃,₃ as a key non-planar graph and use larger complete bipartite graphs with both partitions of at least three vertices as non-planarity cases. section 15.1.1 section 15.2.4
K₃,₃
Divide six vertices into two groups of three. Connect each vertex in the first group to all three vertices in the second, giving 3·3 = 9 edges. K₃,₃ appears with K₅ in Kuratowski’s characterization of non-planar graphs. section 15.1.1 section 15.1.2
Figure 15.6 An embedding of K3,3. Again, do you think there could be a more convenient embedding for this graph?
Inspect an embedding of K₃,₃ and compare possible layouts; crossings are allowed in a generic embedding, while avoiding them is the planarity question. section 15.1.2
