Bipartite Graphs: Two Teams, One Graph

Introduction

Imagine organizing a dance where the rule is simple: every dance must be between a person from Group A and a person from Group B — no dancing within the same group. That rule, translated into graph theory, is exactly what defines a bipartite graph.

Bipartite graphs are one of the most widely used structures in mathematics and computer science. They model everything from job assignments and web search rankings to biological protein interactions and exam scheduling. Understanding them deeply opens the door to a whole family of powerful algorithms.

In this post we will build intuition from scratch, prove key properties, and see why some graphs simply cannot be bipartite — no matter how hard you try.

Definition

Definition: A graph $G = (V, E)$ is bipartite if its vertex set $V$ can be partitioned into two disjoint, non-empty sets $A$ and $B$ — called the bipartition — such that every edge connects a vertex in $A$ to a vertex in $B$.

Formally:

$$V = A \cup B, \quad A \cap B = \emptyset, \quad \forall (u,v) \in E: u \in A \text{ and } v \in B$$

Let’s unpack what this means:

• The word Bi means two — and partite means parts. So bipartite literally means two parts.
• Every edge must cross the partition — edges within $A$ or within $B$ are forbidden.
• $A$ and $B$ are sometimes called the left set and right set, or colour classes.

The pair $(A, B)$ is called a bipartition of $G$.

The Golden Rule

You can draw edges between the two sets, but you can never draw an edge between two vertices in the same set.

A First Example

Here is a small bipartite graph with $|A| = 3$ (orange) and $|B| = 3$ (teal):

Notice:
- Every edge goes from an orange vertex to a teal vertex.
- No orange vertex connects to another orange vertex.
- No teal vertex connects to another teal vertex.
- Not every possible cross-edge needs to exist — this is not a complete bipartite graph. A bipartite graph only requires that existing edges all cross the partition.

The 2-Coloring Test

How to Detect a Bipartite Graph

The most practical way to check whether a graph is bipartite is the 2-coloring algorithm — also called BFS 2-coloring. The idea:

1. Pick any unvisited vertex. Color it orange.
2. Color all of its neighbours teal.
3. Color all of their unvisited neighbours orange.
4. Keep alternating. If you ever try to assign a color to a vertex that already has the opposite color you need, the graph is not bipartite.
5. If you finish coloring every vertex without conflict, the graph is bipartite.

Walkthrough on the Example Above

Step through the coloring:
- Start at vertex 1 → color orange
- Neighbours of 1: 2, 3 → color teal
- Neighbours of 2 and 3: 4 → color orange
- Neighbours of 4: 5, 6 → color teal
- All vertices colored, no conflict. ✓ Bipartite!

The two color classes are $A = \{1, 4\}$ (orange) and $B = \{2, 3, 5, 6\}$ (teal).

The Key Insight

The 2-coloring algorithm works because bipartiteness is equivalent to being 2-colorable: you can assign one of two colors to every vertex so that no two adjacent vertices share the same color. This is also the definition of having chromatic number $\chi(G) \leq 2$.

When It Fails: Odd Cycles

Why Triangles Are Not Bipartite

Consider three friends: You, Alex, and Sam — all friends with each other. That’s a triangle ($K_3$, also called $C_3$).

Try to 2-color it:
- Vertex 1 → orange
- Vertex 2 is adjacent to 1 → teal
- Vertex 3 is adjacent to 2 → must be orange
- But vertex 3 is also adjacent to vertex 1, which is orange — conflict! ✗

The red edge and red vertex mark the contradiction. The coloring algorithm fails, so this graph is not bipartite.

The Cycle Theorem

The failure above is not a coincidence. There is a precise theorem:

Theorem: A graph is bipartite if and only if it contains no odd-length cycles.

This means:
- Any graph with a triangle ($C_3$), pentagon ($C_5$), heptagon ($C_7$), or any other odd cycle is never bipartite.
- Graphs with only even cycles ($C_4$, $C_6$, $C_8$, …) are bipartite.

Odd cycle — $C_5$ (not bipartite)

The 5-cycle $C_5$: following the alternating colors around the pentagon, vertex 5 needs to be orange (because it follows teal vertex 4), but vertex 5 is adjacent to vertex 1 which is also orange. Conflict — marked in red.

Even cycle — $C_6$ (bipartite)

The 6-cycle $C_6$ colors perfectly: odd-positioned vertices $\{1, 3, 5\}$ are orange, even-positioned $\{2, 4, 6\}$ are teal. Every edge crosses the partition. No conflict. $C_6$ is bipartite with $A = \{1,3,5\}$ and $B = \{2,4,6\}$.

General rule: $C_n$ is bipartite $\iff$ $n$ is even.

Real-World Examples

Bipartite graphs are everywhere once you know what to look for.

Example 1: Dogs and Owners

• Set A (orange): Dogs — Rex, Spot, Bella
• Set B (teal): Owners — John, Mary, Sam
• Edges: a line between a dog and a person means the person owns that dog

Rex is owned by both John and Mary. Spot belongs to Mary. Bella belongs to Sam. No dog owns a dog, and no human owns a human in this model — all edges are cross-set. ✓ Bipartite.

Example 2: The School Dance

Imagine a dance where only cross-gender pairs dance together:

• Set A: Boys (Alice, Bob, Carlos)
• Set B: Girls (Dana, Eve, Fiona)
• Edges: a line between two people means they danced together

Because no same-side pair dances, the “who danced with whom” graph is always bipartite.

Example 3: Job Applicants and Positions

A classic application — the matching problem:

• Set A: Applicants (people applying for jobs)
• Set B: Job positions available
• Edges: an applicant is connected to a job if they qualify for it

Finding a maximum matching in this bipartite graph (pairing as many applicants to unique jobs as possible) is solved by the Hungarian algorithm or Hopcroft-Karp algorithm — both run efficiently precisely because the graph is bipartite.

Example 4: A Group of Friends (Usually NOT Bipartite)

Take three friends: You, Alex, and Sam. You are friends with Alex, Alex is friends with Sam, and Sam is friends with you. That triangle $C_3$ we saw above — not bipartite, because it is an odd cycle.

But if you have four friends in a square: You → Alex → Sam → Jordan → You (a $C_4$), the coloring works perfectly: $\{$You, Sam$\}$ and $\{$Alex, Jordan$\}$. Bipartite.

Isolated Vertices

What about a vertex with no edges at all? Such a vertex is called an isolated vertex.

Since it has no edges, it cannot violate the golden rule. When testing for bipartiteness, you can place it in either partition. Isolated vertices never prevent a graph from being bipartite.

The Degree Sum Theorem

There is a beautiful mathematical theorem unique to bipartite graphs.

The Theorem

$$\sum_{v \in A} \deg(v) = \sum_{v \in B} \deg(v) = |E|$$

In words: In any bipartite graph, the sum of degrees of vertices in Set A equals the sum of degrees of vertices in Set B, and both equal the total number of edges.

Why Is This True?

Every edge has exactly one endpoint in $A$ and one endpoint in $B$. So:
- Each edge contributes exactly 1 to the degree sum in $A$.
- Each edge contributes exactly 1 to the degree sum in $B$.

Therefore both sums equal $|E|$. $\blacksquare$

Note: this is different from the Handshaking Lemma (which says the total degree sum equals $2|E|$). In a bipartite graph the total degree sum is split equally between the two sides.

Worked Example

• Set A = $\{X, Y\}$ (orange):
• $\deg(X) = 2$ (connected to $L$ and $M$)
• $\deg(Y) = 3$ (connected to $L$, $M$, and $N$)

• $\sum_{A} \deg = 2 + 3 = \mathbf{5}$

• Set B = $\{L, M, N\}$ (teal):

• $\deg(L) = 2$ (connected to $X$ and $Y$)
• $\deg(M) = 2$ (connected to $X$ and $Y$)
• $\deg(N) = 1$ (connected to $Y$ only)

• $\sum_{B} \deg = 2 + 2 + 1 = \mathbf{5}$

• Total edges $|E| = 5$

$$5 = 5 = 5 \checkmark$$

Complete Bipartite Graphs

Definition

A complete bipartite graph $K_{p,q}$ is a bipartite graph in which every vertex in $A$ is connected to every vertex in $B$. No cross-edge is missing.

If the regular bipartite graph is “some edges cross the partition”, then $K_{p,q}$ is the extreme case: “all possible edges cross the partition.”

Notation

$K_{p,q}$ where:
- $p = |A|$ — the number of vertices in Set A
- $q = |B|$ — the number of vertices in Set B

Properties of $K_{p,q}$

$K_{2,3}$: A First Complete Bipartite Graph

• $|A| = 2$ (orange), $|B| = 3$ (teal)
• Every orange vertex connects to every teal vertex
• Order: $2 + 3 = 5$ vertices
• Size: $2 \times 3 = 6$ edges
• Degrees: each orange vertex has degree $3$; each teal vertex has degree $2$
• Degree sequence: $[3, 3, 2, 2, 2]$

$K_{3,3}$: The Famous Utility Graph

$K_{3,3}$ (three orange, three teal) is perhaps the most famous bipartite graph in all of mathematics. It represents the classic “utilities problem”: can three houses each be connected to three utilities (water, gas, electricity) without any pipes crossing?

Properties of $K_{3,3}$:
- Order: $3 + 3 = 6$ vertices
- Size: $3 \times 3 = 9$ edges
- Degree of every vertex: $3$ (it is a 3-regular graph)
- Degree sequence: $[3, 3, 3, 3, 3, 3]$

The surprising fact: $K_{3,3}$ is not planar — it cannot be drawn in the plane without edge crossings. Together with $K_5$, it is one of the two Kuratowski forbidden minors that characterize planar graphs:

Kuratowski’s Theorem: A graph is planar if and only if it contains no subdivision of $K_5$ or $K_{3,3}$.

$K_{p,q}$ vs $K_n$ — Do Not Confuse Them!

$K_{p,q}$ obeys the bipartite rule. $K_n$ (for $n \geq 3$) violates it — every vertex connects to every other, including same-“side” vertices.

Summary of Key Facts

Practice Problems

Problem 1: Is It Bipartite?

Question: Can the friendship graph “You — Alex — Sam — You” (a triangle) be bipartite?

Problem 2: Degree Theorem

Question: A bipartite graph has $|A| = 4$ vertices and $|B| = 3$ vertices. Set A degrees are $\{2, 3, 1, 2\}$. What is the sum of degrees in Set B? How many edges are there?

Problem 3: Complete Bipartite Properties

Question: For $K_{4,5}$, find: (a) order, (b) size, (c) degree of each vertex in Set A, (d) degree of each vertex in Set B, (e) degree sequence.

Problem 4: Is $C_8$ Bipartite?

Question: Is the 8-cycle $C_8$ bipartite? If yes, give the bipartition.

Problem 5: Find n Given Edge Count

Question: A complete bipartite graph $K_{n,n}$ has 25 edges. Find $n$.

Problem 6: Trees Are Bipartite

Question: Every tree is bipartite. Can you explain why?

Problem 7: Regular Complete Bipartite

Question: For which values of $p$ and $q$ is $K_{p,q}$ a regular graph?

Applications

1. Matching and Assignment Problems

The most powerful use of bipartite graphs is maximum matching — pairing vertices from $A$ to vertices in $B$ such that as many pairs as possible are matched, with no vertex used twice.

Examples:
- Matching job applicants to positions
- Scheduling tasks to machines
- Assigning students to project groups
- Hospital resident matching

König’s Theorem (1931) states that in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover — a deep result with no analogue in general graphs.

2. Web Search and Recommendation Systems

Google’s original PageRank algorithm modeled web links as a bipartite graph: one set = pages that link out, the other = pages being linked to. Modern recommendation engines (Netflix, Spotify) model users and items as two bipartite sets with edges representing ratings or views.

3. Exam and Resource Scheduling

A bipartite graph can model which exams share students: $A$ = exams, $B$ = students, edges = “student takes this exam.” A proper 2-coloring of a derived conflict graph then schedules exams into two non-overlapping time slots — a direct application of bipartite structure.

4. Network Flow

Many network-flow problems reduce to bipartite matching. Hall’s Marriage Theorem gives a necessary and sufficient condition for a perfect matching (every vertex in $A$ matched) to exist in a bipartite graph:

Hall’s Theorem: A bipartite graph $G = (A \cup B, E)$ has a perfect matching (matching all of $A$) if and only if for every subset $S \subseteq A$, the neighbourhood $|N(S)| \geq |S|$.

5. Bioinformatics

Protein-protein interaction networks are often modeled as bipartite graphs: one set = proteins acting as “activators,” the other = proteins acting as “targets.” Drug discovery algorithms search for specific bipartite substructures.

Key Takeaways

1. Definition: A bipartite graph partitions its vertices into two sets $A$ and $B$; every edge crosses between them.
2. 2-Coloring: A graph is bipartite iff it can be 2-colored — equivalent to $\chi(G) \leq 2$.
3. Cycle Theorem: Bipartite iff no odd-length cycles ($C_3, C_5, C_7, \ldots$).
4. Even cycles are bipartite; odd cycles are not. Trees are always bipartite.
5. Degree Sum Theorem: $\sum_A \deg(v) = \sum_B \deg(v) = |E|$.
6. Complete bipartite $K_{p,q}$: every $A$-vertex connects to every $B$-vertex. Order $= p+q$, size $= pq$.
7. $K_{3,3}$ is the famous non-planar bipartite graph (Kuratowski’s theorem).
8. Applications: job matching, recommendation systems, scheduling, network flow, bioinformatics.

Explore Further

Use the GraphArena Playground to experiment:
- Build a bipartite graph and verify the degree sum theorem by hand
- Try to 2-color a $C_5$ and see exactly where it fails
- Construct $K_{3,3}$ and confirm it has 9 edges and is 3-regular
- Try adding a single edge within one partition and observe the graph is no longer bipartite
- Compare $K_{3,3}$ (9 edges, bipartite) with $K_6$ (15 edges, complete) — both have 6 vertices, very different structures

Bipartite graphs are the backbone of matching theory, network flow, and two-sided market models. Mastering them is an essential step in every graph theorist’s toolkit.