Bipartite Graphs

Graph Theory · Axiom Academy

Understanding graphs with two-part vertex sets and their fundamental characterization A graph G = (V, E) is bipartite if its vertex set V can be partitioned into two disjoint sets U and W such that every edge connects a vertex in U to a vertex in W. For every edge (u, v) ∈ E: u ∈ U and v ∈ W (or vice versa) Watch the animation to see how vertices are partitioned into two sets with edges only between them: 2. Characterization: No Odd Cycles This elegant characterization provides both a structural and algorithmic way to understand bipartite graphs. In a bipartite graph, any cycle must alternate between the two vertex sets, making all cycle lengths even. The animation demonstrates why an odd cycle (like a triangle) prevents bipartiteness: 3. Testing Bipartiteness: 2-Coloring A graph is bipartite if and only if it is 2-colorable, meaning we can color all vertices using exactly two colors such that no two adjacent vertices share the same color. Start at any vertex, color it with color 1 Color all neighbors with color 2 Color all their neighbors with color 1 Continue until all vertices are colored or a conflict is found If a conflict occurs (adjacent vertices same color), graph is not bipartite Watch the 2-coloring algorithm in action: 4. Complete Bipartite Graphs K m,n A complete bipartite graph K m,n has vertex sets U and W with |U| = m and |W| = n, where every vertex in U is connected to every vertex in W. Every vertex in U has degree n Every vertex in W has degree m

This is the written version of the interactive lesson above. See the full Graph Theory course.