Definition of Bipartite Graphs - Bipartite Graphs | OneNoughtOne

0/361

Data Structures & AlgorithmsBipartite Graphs

Bipartite Graphs

LevelIntermediate

Duration60 mins

TopicBipartite Graphs

1 / 4

Definition of Bipartite Graphs

The World of Two-Partitioned Graphs

Imagine you're designing a job marketplace platform. On one side, you have employers posting job openings. On the other, job seekers looking for their next opportunity. The connections between them — applications, interviews, offers — always link an employer to a job seeker, never employer-to-employer or seeker-to-seeker.

Or consider a movie database: you have actors and movies. Each edge represents 'Actor X appeared in Movie Y.' An actor never 'appears in' another actor; a movie never 'appears in' another movie. The edges always cross between two distinct categories.

These scenarios share a profound structural property: they can be modeled as bipartite graphs. This isn't just an abstract classification — bipartite graphs unlock entire families of algorithms that are impossible or inefficient on general graphs. From matching job seekers to openings, to scheduling tasks on machines, to validating data models — bipartite graphs are everywhere in computer science.

What You Will Learn

By the end of this page, you will understand the precise mathematical definition of bipartite graphs, develop deep visual intuition for their structure, explore their fundamental properties and special cases, and appreciate why recognizing bipartiteness is often the key to solving complex problems efficiently.

Formal Definition: What Makes a Graph Bipartite?

Let's establish the rigorous mathematical foundation. While the intuition is simple — 'two groups where connections only cross between groups' — the formal definition reveals the precise structure that makes bipartite graphs algorithmically tractable.

Definition: Bipartite Graph

A graph G = (V, E) is bipartite if its vertex set V can be partitioned into two disjoint, non-empty sets U and W (where V = U ∪ W and U ∩ W = ∅) such that every edge (u, v) ∈ E connects a vertex in U to a vertex in W. That is: for every edge, one endpoint is in U and the other is in W.

Let's unpack each component of this definition:

1. Vertex Partition (U and W)

The vertex set V must split into exactly two non-overlapping subsets. These are often called:

Left vertices (U) and Right vertices (W)
Color 0 and Color 1 (reflecting the two-coloring perspective)
Part A and Part B

The terminology varies, but the structure is always the same: every vertex belongs to exactly one of the two partitions.

2. Edge Constraint: Cross-Partition Only

This is the defining property. For every edge in the graph, its two endpoints must be in different partitions. If even a single edge has both endpoints in the same partition, the graph is not bipartite.

3. Disjoint and Non-Empty

Both U and W must be non-empty (otherwise we'd have a trivial graph with no edges). They must be disjoint — no vertex can belong to both partitions simultaneously.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Type definitions for bipartite graphs
interface BipartiteGraph<T> {
  // The two partitions
  leftVertices: Set<T>;   // U: the 'left' partition
  rightVertices: Set<T>;  // W: the 'right' partition
  
  // Edges connecting left to right
  // Each edge goes from a left vertex to a right vertex
  edges: Map<T, Set<T>>;  // adjacency: left vertex -> set of right neighbors
  
  // Invariant: for every edge (u, v) in the graph:
  // - u ∈ leftVertices AND v ∈ rightVertices, OR
  // - u ∈ rightVertices AND v ∈ leftVertices
}
 
// Validate that a given partition represents a valid bipartite structure
function isValidBipartitePartition<T>(
  leftSet: Set<T>,
  rightSet: Set<T>,
  edges: Array<[T, T]>
): boolean {
  // Check 1: Partitions are disjoint
  for (const v of leftSet) {
    if (rightSet.has(v)) return false;
  }
  
  // Check 2: Every edge crosses partitions
  for (const [u, v] of edges) {
    const uLeft = leftSet.has(u);
    const vLeft = leftSet.has(v);
    const uRight = rightSet.has(u);
    const vRight = rightSet.has(v);
    
    // Valid if one in left and other in right
    const crossesPartition = (uLeft && vRight) || (uRight && vLeft);
    if (!crossesPartition) return false;
  }
  
  return true;
}

Alternative Definition via Colorability

An equivalent and often more useful definition: A graph is bipartite if and only if it can be 2-colored — meaning we can assign one of two colors to each vertex such that no edge connects two vertices of the same color. This coloring perspective directly leads to the detection algorithms we'll explore.

Visual Representation and Intuition

Bipartite graphs have a distinctive visual representation that immediately reveals their structure. When drawn in the standard form, they appear as two parallel columns of vertices with edges crossing between them — never connecting vertices within the same column.

      Left (U)              Right (W)
    ┌─────────┐            ┌─────────┐
    │         │            │         │
    │   A ●━━━━━━━━━━━━━━━━● 1       │
    │         │╲           │         │
    │   B ●━━━━━━━━━━━━━━━━● 2       │
    │         │  ╲         │╱        │
    │   C ●━━━━━━━━━━━━━━━━● 3       │
    │         │    ╲      ╱│         │
    │   D ●━━━━━━━━━━━━━━━━● 4       │
    │         │            │         │
    └─────────┘            └─────────┘
 
    Edges shown: A-1, A-2, B-2, B-3, C-3, C-4, D-4
    
    Notice: Every edge crosses between columns.
    No edge connects two vertices in the same column.

Why this visual form is powerful:

When you draw a bipartite graph with left vertices in one column and right vertices in another:

Bipartiteness becomes immediately visible — Any intra-column edge would instantly reveal the graph is not bipartite.
Matching problems become geometric — Finding a maximum matching is like drawing the maximum number of non-crossing connections.
Relationships are clear — In applications like job matching, you literally see 'employers on left, candidates on right, lines show who applied where.'

Contrast: The same graph drawn differently

The same bipartite graph can be drawn in ways that hide its bipartite nature:

              A
             ╱ ╲
            ╱   ╲
           1─────2
          ╱       ╲
         ╱         ╲
        D───────────B
         ╲         ╱
          ╲       ╱
           4─────3
            ╲   ╱
             ╲ ╱
              C
 
    In this circular layout, bipartiteness is not obvious!
    But if we color: {A, B, C, D} = BLUE, {1, 2, 3, 4} = RED
    We see: Every edge connects BLUE to RED.
    
    The graph IS bipartite — the layout just obscured it.

Don't Judge by Visual Appearance Alone

A graph's visual layout can hide or reveal its bipartite structure. The definition is what matters — whether a valid 2-partition exists. Algorithms like BFS/DFS 2-coloring definitively answer this question, regardless of how the graph happens to be drawn.

Fundamental Properties of Bipartite Graphs

Bipartite graphs possess several remarkable properties that distinguish them from general graphs. Understanding these properties is crucial for recognizing bipartite problems and applying specialized algorithms.

Core Properties of Bipartite Graphs

•Property 1: No Odd Cycles — A graph is bipartite if and only if it contains no cycles of odd length. This is the characterization theorem that underlies all detection algorithms.
•Property 2: Unique 2-Partition (for Connected Graphs) — If a connected graph is bipartite, its 2-partition is unique (up to swapping the two sets). You can't 'choose' which side a vertex goes on — once you fix one vertex, all others are determined.
•Property 3: All Cycles Are Even — Every cycle in a bipartite graph has even length (2, 4, 6, 8, ...). Cycles must alternate between partitions, requiring an even number of steps to return to the start.
•Property 4: König's Theorem — In bipartite graphs, the maximum matching size equals the minimum vertex cover size. This duality doesn't hold for general graphs!
•Property 5: Hall's Marriage Theorem — A bipartite graph has a perfect matching if and only if every subset S of one partition has at least |S| neighbors in the other partition.

Let's examine the most important property — the odd cycle characterization — in depth, as it's the theoretical foundation for all bipartiteness detection algorithms:

Theorem (Odd Cycle Characterization):

A graph G is bipartite if and only if G contains no cycle of odd length.

Proof Sketch (⟹ direction): Suppose G is bipartite with partition (U, W). Consider any cycle: v₁ → v₂ → v₃ → ... → vₖ → v₁.

Start at v₁. Say v₁ ∈ U.
v₂ must be in W (since edge v₁-v₂ crosses partitions)
v₃ must be in U (since edge v₂-v₃ crosses partitions)
The pattern alternates: U, W, U, W, U, W, ...
After k edges, we return to v₁ ∈ U
For this to work, k must be even (so we're 'back' to the starting partition)

Thus, every cycle has even length.

Proof Sketch (⟸ direction): If G has no odd cycles, we can 2-color it using BFS:

Pick any vertex, color it 0, put it in partition U
BFS outward, alternating colors
If we ever try to color a vertex already colored the same color, we've found an odd cycle (contradiction)
Since no odd cycles exist, the 2-coloring succeeds

Thus, G is bipartite.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// When BFS detection fails, it finds an odd cycle
function findOddCycleIfExists(
  graph: Map<number, number[]>,
  n: number
): number[] | null {
  const color = new Array(n).fill(-1);  // -1 = unvisited
  const parent = new Array(n).fill(-1);
  
  for (let start = 0; start < n; start++) {
    if (color[start] !== -1) continue;
    
    const queue: number[] = [start];
    color[start] = 0;
    
    while (queue.length > 0) {
      const u = queue.shift()!;
      
      for (const v of graph.get(u) || []) {
        if (color[v] === -1) {
          color[v] = 1 - color[u];
          parent[v] = u;
          queue.push(v);
        } else if (color[v] === color[u]) {
          // Same color neighbor! Found odd cycle.
          // Reconstruct the cycle:
          return reconstructOddCycle(u, v, parent);
        }
      }
    }
  }
  
  return null;  // No odd cycle — graph is bipartite
}
 
function reconstructOddCycle(
  u: number,
  v: number,
  parent: number[]
): number[] {
  // u and v are same-colored neighbors
  // Trace back to find their common ancestor
  const pathU: number[] = [];
  const pathV: number[] = [];
  
  let curr = u;
  while (curr !== -1) {
    pathU.push(curr);
    curr = parent[curr];
  }
  
  curr = v;
  while (curr !== -1) {
    pathV.push(curr);
    curr = parent[curr];
  }
  
  // Find common ancestor and construct cycle
  const setU = new Set(pathU);
  let ancestor = -1;
  for (const node of pathV) {
    if (setU.has(node)) {
      ancestor = node;
      break;
    }
  }
  
  // Cycle: u -> ancestor -> v -> u
  const cycle: number[] = [];
  for (const node of pathU) {
    cycle.push(node);
    if (node === ancestor) break;
  }
  
  const vToAncestor: number[] = [];
  for (const node of pathV) {
    if (node === ancestor) break;
    vToAncestor.push(node);
  }
  
  cycle.push(...vToAncestor.reverse());
  return cycle;
}

Practical Implication

The odd cycle characterization isn't just theoretical — it's constructive. When a graph fails the bipartiteness test, we don't just get 'false'; we can extract the actual odd cycle that proves non-bipartiteness. This is invaluable for debugging and understanding complex graphs.

Special Cases and Edge Cases

Understanding the edge cases of bipartite graphs helps solidify the definition and prevents subtle bugs in algorithms. Let's examine several important special cases:

Case 1: Empty Graph (No Edges)

A graph with vertices but no edges is always bipartite. We can assign vertices to partitions arbitrarily since there are no edge constraints to satisfy.

Vertices: {A, B, C, D, E}
Edges: ∅ (none)

Valid 2-coloring: Any assignment works!
Example: U = {A, B, C}, W = {D, E}
Example: U = {A}, W = {B, C, D, E}
Example: U = {A, B, C, D, E}, W = {} ← Actually invalid! W must be non-empty.

Technical note: Some definitions require both partitions to be non-empty. Under strict definitions, an edgeless graph with all vertices in one partition wouldn't qualify. In practice, most algorithms treat such graphs as bipartite.

Case 2: Single Edge Graph

The simplest non-trivial bipartite graph:

A ━━━━━ B

Partition: U = {A}, W = {B}
2-coloring: color(A) = 0, color(B) = 1

This trivially satisfies all bipartite properties. More generally, any tree is bipartite because trees contain no cycles (hence, no odd cycles).

Case 3: Disconnected Graphs

A disconnected graph is bipartite if and only if every connected component is bipartite. We partition each component independently.

Component 1:        Component 2:
  A ━━ B              X ━━ Y
  │    │              │    │
  D ━━ C              Z ━━ W

Both components form 4-cycles (even cycles).
Both are bipartite independently.
The whole graph is bipartite.

Partition: U = {A, C, X, Z}, W = {B, D, Y, W}

If any component contains an odd cycle, the entire graph is non-bipartite.

Case 4: Self-Loops

A self-loop (an edge from a vertex to itself) immediately makes a graph non-bipartite:

A ⟳ (self-loop on A)

This is an odd cycle of length 1!
For A's edge to cross partitions, A would need to be in BOTH U and W.
This is impossible, so the graph is not bipartite.

Key insight: Self-loops are the shortest possible odd 'cycle.' Any graph with self-loops is automatically non-bipartite.

Case 5: Complete Bipartite Graphs (K_{m,n})

The complete bipartite graph K_{m,n} has:

m vertices in partition U
n vertices in partition W
Every possible edge between U and W

K_{3,2}:  Every left vertex connects to every right vertex.

    A ●━━━━━━━━━━━━━━● 1
      ╲             ╱
    B ●━━━╳━━━━━╳━━━● 2
      ╱             ╲
    C ●━━━━━━━━━━━━━━●

Edges: A-1, A-2, B-1, B-2, C-1, C-2
Total: 3 × 2 = 6 edges

Complete bipartite graphs are extremely dense but still bipartite. They have m × n edges — the maximum possible while maintaining bipartiteness.

Special case: K_{n,n} When both partitions have equal size, we get a balanced complete bipartite graph. These are important in matching theory — they always admit a perfect matching.

The Simplest Non-Bipartite Examples

Triangle (K₃): Three vertices, all connected. This 3-cycle is the smallest non-bipartite graph (excluding self-loops).

Pentagon (C₅): A cycle of 5 vertices. Any odd cycle makes a graph non-bipartite.

Remember: Even cycles (square, hexagon, octagon) are bipartite. Odd cycles are not.

Bipartiteness of Common Graph Structures
Graph Type	Bipartite?	Reason
Path (P_n)	✅ Yes	No cycles at all — trees are always bipartite
Tree	✅ Yes	Trees contain no cycles
Even Cycle (C_4, C_6, ...)	✅ Yes	All cycles have even length
Odd Cycle (C_3, C_5, ...)	❌ No	Contains an odd cycle (itself)
Complete Graph (K_n, n > 2)	❌ No	Contains triangles (K₃)
Complete Bipartite (K_{m,n})	✅ Yes	By construction — all edges cross partitions
Grid Graph	✅ Yes	Can be 2-colored like a checkerboard
Hypercube (Q_n)	✅ Yes	Bipartite — vertices partition by parity of 1-bits
Wheel Graph (W_n)	❌ No (n ≥ 3)	Central vertex creates odd cycles
Petersen Graph	❌ No	Contains 5-cycles

Why Bipartite Graphs Matter Algorithmically

Recognizing that a graph is bipartite isn't just a classification exercise — it unlocks powerful algorithms that don't work on general graphs. This is perhaps the most important practical takeaway: many NP-hard problems on general graphs become polynomial-time solvable on bipartite graphs.

Problem Complexity: General vs. Bipartite Graphs
Problem	General Graphs	Bipartite Graphs
Maximum Matching	O(V × E) — Blossom algorithm	O(E × √V) — Hopcroft-Karp
Minimum Vertex Cover	NP-hard	O(E × √V) — König's theorem
Maximum Independent Set	NP-hard	O(E × √V) — Complement of vertex cover
Graph Coloring (min colors)	NP-hard	O(1) — Always 2 colors!
Edge Coloring (min colors)	NP-complete (decision)	O(E) — Always Δ or Δ+1 colors
Perfect Matching Decision	O(V × E)	O(E × √V) + Hall's theorem check

Key insight: The Matching-Vertex Cover Duality

In general graphs, maximum matching and minimum vertex cover are related but finding minimum vertex cover is NP-hard.

In bipartite graphs, König's theorem states:

Maximum matching size = Minimum vertex cover size

This means once you find a maximum matching (polynomial time), you've implicitly solved the vertex cover problem too! This duality is extraordinarily powerful for optimization problems.

Why does bipartiteness help?

The structural constraint (no odd cycles) eliminates the algorithmic complexity that makes many graph problems hard. For matching, the 'blossom' structure that complicates general matching doesn't exist in bipartite graphs. For coloring, the answer is trivially 2. For covers, the König duality provides a polynomial-time path.

Problem-Solving Strategy

When facing a graph problem, always check if the graph is bipartite first. Many problems simplify dramatically. Even if the problem doesn't explicitly mention bipartiteness, the input constraints might guarantee it (e.g., 'graph has no odd cycles,' 'graph represents relationships between two types of entities').

Real-World Examples of Bipartite Graphs

Bipartite graphs appear naturally whenever relationships exist exclusively between two distinct categories. Recognizing these patterns in real problems is a critical skill for algorithm designers.

Bipartite Graphs in the Real World

•Job Matching — Employers ↔ Job Seekers. Applications connect seekers to employers, never seeker-to-seeker. Maximum matching finds optimal job assignments.
•Dating/Matching Apps — In traditional models: one group ↔ another group. Edges represent mutual interest. Finding stable matchings is a bipartite problem.
•Movie-Actor Database — Movies ↔ Actors. Edges represent 'appeared in.' Queries like 'actors in common' exploit bipartite structure.
•Course Scheduling — Courses ↔ Time Slots. Edges represent 'course can be scheduled at this time.' Valid schedules are bipartite matchings.
•Medical Trials — Patients ↔ Treatments. Edges represent 'patient eligible for treatment.' Assignment optimization is bipartite matching.
•E-commerce Recommendations — Users ↔ Products. Purchase/view history creates edges. Recommendation algorithms leverage bipartite structure.
•Bioinformatics — Genes ↔ Diseases, Proteins ↔ Drugs. Association networks are naturally bipartite.
•Academic Publishing — Authors ↔ Papers. The author-paper graph is bipartite; analyzing it reveals collaboration patterns.
•Load Balancing — Servers ↔ Requests. Assigning requests to servers to balance load is often modeled as bipartite matching.
•Chess Tournaments — In round-robin with two teams: Team A players ↔ Team B players. Scheduling matches is bipartite.

Pattern Recognition

Whenever you see 'two types of entities with relationships only between types,' think bipartite graph. This mental pattern matching opens up the entire toolkit of bipartite algorithms.

Summary: Definition of Bipartite Graphs

We've established a comprehensive foundation for understanding bipartite graphs. Let's consolidate the key concepts:

Key Takeaways

•Formal Definition — A bipartite graph has vertices partitioned into two disjoint sets U and W, where every edge connects a vertex in U to a vertex in W.
•Equivalent Characterization — A graph is bipartite if and only if it can be 2-colored, which is equivalent to containing no odd cycles.
•Visual Intuition — Bipartite graphs are naturally drawn with two columns of vertices, edges crossing between columns.
•Special Cases — Trees, even cycles, grids, and hypercubes are bipartite. Triangles, odd cycles, and complete graphs (n > 2) are not.
•Algorithmic Significance — Many NP-hard problems (vertex cover, independent set) become polynomial on bipartite graphs.
•Real-World Applications — Any 'two types of entities' relationship network is likely bipartite: job matching, course scheduling, medical trials, etc.

What's Next:

Now that we understand what bipartite graphs are, we need a way to detect them. The next page explores the 2-coloring approach — the elegant technique that not only verifies bipartiteness but also produces the partition when it exists, or identifies the odd cycle when it doesn't.

Foundation Complete

You now have a rigorous understanding of bipartite graph structure. The definition, properties, and intuition from this page will underpin everything that follows — detection algorithms, matching algorithms, and real-world applications.