K3,3 is the complete bipartite graph with two vertex partitions of three vertices each. It has six vertices and nine simple edges, with every edge joining the two partitions. Kuratowski’s theorem identifies it as one of the two simplest non-planar graphs. section 15.2.1 section 15.2.3
Recognize K3,3 during planarity testing by checking:
- The graph has exactly six vertices and nine simple edges. section 15.2.3
- The graph is bipartite, with partitions sized (3,3). section 15.2.3
- A matching graph is immediately classified as non-planar within the recursive planarity algorithm. section 15.2.1 section 15.2.3
Recognition in a planarity test
An isK3_3 check first counts vertices and simple edges, then verifies bipartiteness and the partition sizes. It returns true only for six vertices, nine edges, and partitions of three and three. section 15.2.3
Listing 15.5 Planarity testing utility methods: K3,3 testing
function isK3_3(graph) #1
(n,m) ← (|graph.vertices|, |graph.simpleEdges|) #2
if n == 6 and m == 9 then #3
if isBipartite(graph) and partitionsSize(graph) == (3,3) then #4
return true
return false
Use the compact utility listing to inspect the exact recognition procedure and its bipartite-partition test. section 15.2.3
