Bipartite Graphs
What You'll Learn
You'll learn what bipartite graphs are and explore their special structure where vertices split into two independent groups.
The Core Idea
A bipartite graph is a graph whose vertices can be divided into two disjoint sets—let's call them U and V—such that every edge connects a vertex in U to a vertex in V. Crucially, no edges exist within the same set: vertices in U don't connect to other vertices in U, and vertices in V don't connect to other vertices in V.
Think of it like a dating app matching system: one set represents users looking for partners, the other set represents potential matches, and edges represent compatible pairings. People only connect across groups, never within their own group.
Visual Example
Imagine vertices {1, 2, 3} in set U and {A, B} in set V. Valid edges might be 1-A, 1-B, 2-A, 3-B. Invalid would be 1-2 (both in U) or A-B (both in V).
We write this as G = (U ∪ V, E) where U ∩ V = ∅.
Complete Bipartite Graphs
A complete bipartite graph K_{m,n} is a special bipartite graph where every vertex in one set connects to every vertex in the other set. If |U| = m and |V| = n, then K_{m,n} has exactly m × n edges—the maximum possible for a bipartite graph with those set sizes.
For example, K_{3,2} has 3 vertices in one set, 2 in the other, and 6 edges connecting them completely.
Testing for Bipartiteness
A graph is bipartite if and only if it contains no odd-length cycles. This gives us a practical way to verify the structure.
Key Takeaway: Bipartite graphs partition vertices into two independent sets with edges only between sets; complete bipartite graphs K_{m,n} connect every vertex across both sets.