Course contentsShow
← Mathematics
Lesson 2653 of 3,12153. Graph TheoryFree lesson

Bipartite Graphs

Define bipartite graphs where vertices split into two sets with edges only between sets; introduce complete bipartite graphs.

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.