Bipartite Graph — Definition, Formula & Examples

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. No edge ever links two vertices within the same set.

A graph $G = (V, E)$ is bipartite if there exists a partition of $V$ into two non-empty subsets $U$ and $W$ (where $U \cup W = V$ and $U \cap W = \emptyset$ ) such that every edge $\{u, w\} \in E$ satisfies $u \in U$ and $w \in W$ . Equivalently, $G$ is bipartite if and only if it contains no odd-length cycle.

How It Works

To check whether a graph is bipartite, attempt a 2-coloring. Pick any vertex, assign it color A, then assign color B to all its neighbors. Continue alternating colors via BFS or DFS. If you ever need to assign both colors to the same vertex, the graph is not bipartite. If the entire graph is successfully 2-colored, it is bipartite, and the two color classes form the partition.

Worked Example

Problem: Determine whether the graph with vertices {1, 2, 3, 4} and edges {1-2, 2-3, 3-4, 4-1} is bipartite.

Step 1: Start at vertex 1 and assign it to set U.

U = \{1\}

Step 2: Vertex 1 is adjacent to 2 and 4, so assign them to set W.

W = \{2, 4\}

Step 3: Vertex 2 is adjacent to 3, and vertex 4 is also adjacent to 3. Assign vertex 3 to set U.

U = \{1, 3\}, \quad W = \{2, 4\}

Step 4: Verify: every edge (1-2, 2-3, 3-4, 4-1) connects a vertex in U to a vertex in W. No edge connects two vertices within the same set.

Answer: The graph is bipartite with partition U = {1, 3} and W = {2, 4}. This is a 4-cycle, which is an even cycle and therefore bipartite.

Why It Matters

Bipartite graphs model matching problems such as assigning jobs to workers, scheduling tasks to machines, or pairing students with projects. Algorithms like the Hungarian method and Hopcroft–Karp rely on bipartite structure. They also appear in database theory, network flow, and compiler design.

Common Mistakes

Mistake: Assuming a graph with an even number of vertices must be bipartite.

Correction: The number of vertices does not determine bipartiteness. A triangle (

K_3

) has an odd cycle and is not bipartite, while a path on 3 vertices is bipartite. Check for odd cycles or attempt a 2-coloring instead.