Mathematics.

graph structures

Bipartite Graphs

Graph Theory25 minDifficulty3 out of 10

You should know: graph basics

Overview

A bipartite graph is a graph whose vertices can be split into two disjoint sets, X and Y, such that every edge connects a vertex in X to a vertex in Y — no edge ever joins two vertices within the same set. Bipartite graphs naturally model matching problems between two distinct kinds of objects: job applicants and job openings, students and schools, or buyers and sellers. A fundamental theorem states that a graph is bipartite if and only if it contains no odd-length cycle, giving an easy algorithmic test via a two-coloring attempt during BFS or DFS.

Intuition

Picture a school dance where boys must be paired only with girls, never boy-with-boy or girl-with-girl — every dance pairing (edge) crosses between the two groups. That's the essence of bipartiteness: two 'teams' of vertices where all the action happens between teams, never within one. This structure shows up whenever you're matching two different kinds of things: workers to tasks, courses to time slots, or organs to transplant recipients.

Formal Definition

Definition

A graph G = (V, E) is bipartite if V can be partitioned into two sets X and Y with:

V=X∪Y,X∩Y=∅V = X \cup Y, \quad X \cap Y = \emptyset
Vertex bipartition
∀{u,v}∈E: u∈X, v∈Y (or vice versa)\forall \{u,v\} \in E:\ u \in X,\ v \in Y \text{ (or vice versa)}
Every edge crosses the partition
G is bipartite  ⟺  G has no odd-length cycleG \text{ is bipartite} \iff G \text{ has no odd-length cycle}
Odd-cycle characterization

Worked Examples

  1. Try to 2-color: put A and B in set X, and see if all their neighbors can go in set Y.

    X={A,B}X = \{A, B\}

  2. A's neighbors are C, D; B's neighbor is C. All of C, D can be placed in Y without conflict.

    Y={C,D}Y = \{C, D\}

  3. Check every edge crosses X-Y: A-C (X-Y ✓), A-D (X-Y ✓), B-C (X-Y ✓). No edge is within X or within Y.

    All edges cross X,Y\text{All edges cross } X, Y

Answer: Yes, bipartite with X = {A, B}, Y = {C, D}.

Practice Problems

Difficulty 3/10

A graph is a single cycle of length 6 (a hexagon). Is it bipartite?

Difficulty 4/10

5 applicants and 4 job openings are connected by an edge whenever an applicant is qualified for that job. What kind of graph models this, and why is it always bipartite regardless of which edges exist?

Difficulty 4/10

A graph has a triangle (3-cycle) A-B-C-A as a subgraph. Can the overall graph be bipartite?

Quiz

A graph is bipartite if and only if it contains:
In a bipartite graph with parts X and Y, an edge can connect:
Matching job applicants to job openings is naturally modeled as:

Summary

  • A bipartite graph splits its vertices into two sets X, Y where every edge connects X to Y, never within a set.
  • A graph is bipartite if and only if it contains no odd-length cycle — testable via a 2-coloring attempt with BFS/DFS.
  • Bipartite structure is the natural model for matching problems: applicants-to-jobs, students-to-schools, tasks-to-workers.

References

  1. WebsiteWikipedia — Bipartite graph