A bipartite graph is a connected graph whose vertices can be divided into two groups, A and B, with every edge joining one group to the other. No edge joins two vertices within the same group. section 15.1.2
A complete bipartite graph contains every possible edge between its partitions. It is written Kₙ,ₘ, where the two groups contain n and m vertices; it has exactly n·m edges. K₃,₃ therefore has six vertices and nine edges. section 15.1.2 section 15.2.3
To test a connected graph, start with one vertex, assign it one color, and traverse the graph with BFS. Assign every uncolored neighbor the opposite color. If an edge connects vertices with the same color, the graph is not bipartite; otherwise, the two color classes are the partitions. section 15.2.3
A practical implementation maintains:
- Two resulting color classes, returned as the graph’s partitions when no conflict appears. section 15.2.3
Recognizing K₃,₃
A graph is a candidate for K₃,₃ when it has six vertices and nine simple edges. It qualifies only if it is bipartite and its two partitions each contain three vertices. section 15.2.3
