Bipartite Graphs
What You'll Learn
You'll discover a special class of graphs where vertices naturally split into two distinct groups with all edges crossing between them.
The Core Idea
A bipartite graph is a graph whose vertices can be divided into two completely separate sets (often called U and V), where every edge connects a vertex from one set to a vertex in the other set—never within the same set.
Think of it like a dance where partners must come from different groups: boys on one side, girls on the other, and every dance pair consists of one person from each side. No one dances with someone from their own group.
Key Properties
- Two disjoint sets: The vertices are partitioned into two groups with no overlap
- Cross-set edges only: All edges go between the two sets; no edges exist within a set
- No odd cycles: This is the mathematical test—a graph is bipartite if and only if it contains no cycles of odd length
Common Examples
- Job matching: Workers on one side, jobs on the other, edges represent who can do which job
- Course scheduling: Students in one set, courses in the other, edges show enrollment
- Network routing: Computers in one set, routers in the other
- Dating apps: Two groups of users, edges represent mutual interest
Recognizing Bipartite Graphs
You can test if a graph is bipartite by trying to color it with just two colors, where no adjacent vertices share the same color. If you succeed, it's bipartite—the two colors represent the two sets.
Key Takeaway: A bipartite graph partitions vertices into two independent sets where all edges cross between sets, making it perfect for modeling relationships between two distinct types of entities.