Bipartite Graphs

Quick Revisit

• USE WHEN: 2-coloring, parity constraints, matching on bipartite graphs, odd-cycle detection
• INVARIANT: a graph is bipartite iff it contains no odd-length cycle
• TIME: O(V + E) via BFS/DFS coloring | SPACE: O(V)
• CLASSIC BUG: not checking all connected components (graph may be disconnected)
• PRACTICE: ../12-practice-ladders/05-ladder-graphs.md

Two-colorable graphs -- split vertices into two sides so every edge crosses. The foundation of matching, covering, and independence in contest problems.

Difficulty: [Intermediate]Prerequisites: BFS, DFS and Tree DFSCF Rating Range: 1300-1700

---

Contents

• 2. Intuition & Concept
• 3. Visual Intuition
• 4. C++ STL Reference
• 5. Implementation (Contest-Ready)
• 6. Operations Reference
• 7. Problem Patterns & Tricks
• When to Reach for This
• 8. Contest Cheat Sheet
• 9. Common Mistakes
• 10. Self-Test
• 11. Practice Problems
• Recap
• 12. Further Reading
• Appendix: The Proof -- Bipartite iff No Odd Cycle
• Appendix: Konig's Theorem -- Why It Works

---

Intuition & Concept

A teacher wants to split students into two teams for a quiz bowl. The constraint: no two friends can be on the same team (they'd share answers). Model students as nodes, friendships as edges. Can you color every node red or blue so that every edge connects a red node to a blue node?

That's the 2-coloring problem, and a graph that admits such a coloring is bipartite.

Bipartite graphs appear everywhere on Codeforces: grid problems where you color cells like a checkerboard, "assign items to two groups" constraints, parity arguments on paths, and as the underlying structure for matching and flow. Recognizing bipartiteness early often unlocks the entire solution.

A graph is bipartite if and only if it contains no odd-length cycle. This is the single most important characterization. Every tree is bipartite (trees have no cycles at all). Every grid graph with standard 4-directional adjacency is bipartite (the checkerboard coloring works). A cycle of even length is bipartite; a cycle of odd length is not.

Why odd cycles break things: start coloring around a cycle, alternating red-blue-red-blue. After an even number of steps, you return to the start and the color matches. After an odd number of steps, you return and need a different color than what's already there -- contradiction.

When to suspect bipartite on CF:

• "Divide into two groups" or "two teams" language
• Grid problems with alternating constraints (checkerboard)
• Parity arguments: distances mod 2, even/odd path lengths
• Any problem reducible to 2-SAT where each variable is binary
• Problems mentioning "independent set" or "vertex cover" on special graphs

Common traps at the ~1100-1300 level:

• Forgetting to handle disconnected graphs (see Common Mistakes)
• Using adjacency matrix on $n>5000$ -- always use adjacency lists
• Not realizing that "bipartite check" is just a BFS/DFS with coloring, not a separate algorithm
• Confusing bipartite with "has even number of nodes" (completely unrelated)

What the Code Won't Teach You

The 2-coloring check works because of BFS layers -- not by accident.

BFS explores nodes layer by layer. Layer 0 gets color 0, layer 1 gets color 1, layer 2 gets color 0, and so on. The color of a node is exactly its layer parity. Every edge in the BFS tree connects adjacent layers (different parity, different colors) -- automatically consistent. The only way a conflict arises is from a non-tree edge whose two endpoints have the same parity — that is, layers differing by an even number. The simplest case is a literal same-layer edge; the general case is any edge between two nodes whose BFS-distances from the root have the same parity. Either way, the resulting cycle has odd length. This is why the algorithm is correct, not just a heuristic.

    BFS layers on a 4-node bipartite path:

    Graph:  1 --- 2 --- 3 --- 4

    BFS from node 1:
    Layer 0:  [0]1                    Queue: < 1 >
                |
    Layer 1:  [1]2                    Queue: < 2 >
                |
    Layer 2:  [0]3                    Queue: < 3 >
                |
    Layer 3:  [1]4                    Queue: < 4 >

    Every edge connects adjacent layers (parity differs by 1):
      1--2 : layer 0 -- layer 1  (different color) OK
      2--3 : layer 1 -- layer 2  (different color) OK
      3--4 : layer 2 -- layer 3  (different color) OK

    No same-parity edges --> no conflicts --> bipartite.

    Now add edge 1--3 (same parity, layers 0 and 2):

    Layer 0:  [0]1 ------+
                |         |  <-- same parity (both even layers)
    Layer 1:  [1]2        |      so same color: color[1]=color[3]=0
                |         |
    Layer 2:  [0]3 ------+      CONFLICT!

    +---> edge 1--3 connects two nodes at even layers
    |     same color on both ends -> odd cycle 1--2--3--1
    v     cycle length = 2 + 1 = 3 (odd)

    The fatal pattern is "same-parity edge", not necessarily
    "same-layer edge". A literal same-layer edge is the most
    obvious case; an edge between layers k and k+2 is the same
    sin in disguise.

Bipartiteness enables powerful reductions -- not just a "check".

Recognizing a graph as bipartite unlocks Konig's theorem (max matching = min vertex cover), Hall's theorem (conditions for perfect matching), and efficient matching algorithms. Many contest problems disguise themselves as assignment, scheduling, or coloring tasks -- but the core reduction is: build a conflict graph, check bipartiteness, then exploit the bipartite structure. The 2-coloring isn't the answer; it's the key that opens the door to the real algorithm.

---

Visual Intuition

The Coloring Process

Start with an uncolored graph of 6 nodes. BFS from node 1, assigning colors alternately.

  Initial graph (no colors):

      1 --- 2
      |     |
      3 --- 4 --- 5
                  |
                  6

  Adjacency: 1:[2,3]  2:[1,4]  3:[1,4]  4:[2,3,5]  5:[4,6]  6:[5]

BFS from node 1, color it RED (0):

  Step 0: color[1] = R         Queue: [1]

  Step 1: pop 1, push neighbors 2,3
          color[2] = B          (opposite of 1)
          color[3] = B          (opposite of 1)
          Queue: [2, 3]

      [R]1 --- [B]2
       |         |
      [B]3      4 --- 5
                      |
                      6

  Step 2: pop 2, push neighbor 4
          color[4] = R          (opposite of 2)
          Queue: [3, 4]

  Step 3: pop 3, check neighbor 4
          4 is already colored R, 3 is colored B
          R != B  -->  OK, no conflict
          Queue: [4]

      [R]1 --- [B]2
       |         |
      [B]3 --- [R]4 --- 5
                        |
                        6

  Step 4: pop 4, push neighbor 5
          color[5] = B          (opposite of 4)
          Queue: [5]

  Step 5: pop 5, push neighbor 6
          color[6] = R          (opposite of 5)
          Queue: [6]

  Step 6: pop 6, no unvisited neighbors.
          Queue: []  -->  done.

  Final coloring:

      [R]1 --- [B]2
       |         |
      [B]3 --- [R]4 --- [B]5
                          |
                        [R]6

  Left side (R): {1, 4, 6}
  Right side (B): {2, 3, 5}
  Every edge goes R <--> B.   BIPARTITE.

Detecting an Odd Cycle

Now add edge (2, 3) to the same graph:

      1 --- 2
      |   / |
      3 --- 4 --- 5
                  |
                  6

  BFS from 1:
    color[1] = R
    color[2] = B     (from 1)
    color[3] = B     (from 1)
    Now process node 2: neighbor 3 has color B.
    Node 2 also has color B.
    B == B  -->  CONFLICT!

  The odd cycle: 1 -- 2 -- 3 -- 1  (length 3)

      [R]1 --- [B]2
        \      /
         [B]3          <-- same color as 2, but edge exists!

  NOT BIPARTITE.

Konig's Theorem Visualized

In a bipartite graph, maximum matching = minimum vertex cover.

  Example bipartite graph:

    L1 ---- R1
    L1 ---- R2
    L2 ---- R2
    L2 ---- R3
    L3 ---- R3

    Left:  L1  L2  L3          Right:  R1  R2  R3
            |\ | \ |
           R1 R2  R3

  Maximum matching (bold edges):

    L1 ==== R1          (matched)
    L2 ==== R2          (matched)
    L3 ==== R3          (matched)

    Max matching size = 3

  Minimum vertex cover:
    Pick {R1, R2, R3} -- these 3 vertices touch all 5 edges.
    Or pick {L1, L2, L3} -- also works.
    Min vertex cover size = 3

  By Konig's theorem, these are always equal in bipartite graphs.
  (This fails in general graphs -- K3 has matching 1 but vertex cover 2.)

  Bonus: Maximum independent set = n - min vertex cover
         = 6 - 3 = 3  (the other side)

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
vector<vector<int>>	<vector>	Adjacency list representation	$O(1)$ per push
queue<int>	<queue>	BFS frontier	$O(1)$ push/pop
vector<int> color(n, -1)	<vector>	Color/side assignment (-1 = unvisited)	$O(n)$ init
fill(v.begin(), v.end(), -1)	<algorithm>	Reset color array	$O(n)$

No specialized STL for bipartite checking -- it's a standard BFS/DFS with a color array.

---

Implementation (Contest-Ready)

Minimal Template -- BFS 2-Coloring

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> color(n, -1);
    bool bipartite = true;

    for (int s = 0; s < n && bipartite; s++) {
        if (color[s] != -1) continue;
        color[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty() && bipartite) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) {
                    color[v] = color[u] ^ 1;
                    q.push(v);
                } else if (color[v] == color[u]) {
                    bipartite = false;
                }
            }
        }
    }

    if (bipartite) {
        cout << "YES\n";
        for (int i = 0; i < n; i++)
            cout << (color[i] == -1 ? 0 : color[i]) + 1 << " \n"[i == n - 1];
    } else {
        cout << "NO\n";
    }
}

Explained Version -- BFS 2-Coloring

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;  // 0-indexed
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // color[v] = -1 means unvisited, 0 or 1 means side assignment
    vector<int> color(n, -1);
    bool bipartite = true;

    // Graph may be disconnected -- must try every component
    for (int s = 0; s < n && bipartite; s++) {
        if (color[s] != -1) continue;  // already colored in a previous BFS

        // Start BFS from this component's first unvisited node
        color[s] = 0;
        queue<int> q;
        q.push(s);

        while (!q.empty() && bipartite) {
            int u = q.front();
            q.pop();

            for (int v : adj[u]) {
                if (color[v] == -1) {
                    // Unvisited: assign opposite color
                    color[v] = color[u] ^ 1;  // 0^1=1, 1^1=0
                    q.push(v);
                } else if (color[v] == color[u]) {
                    // Same color on both endpoints -- odd cycle found
                    bipartite = false;
                }
                // If color[v] != color[u] and v is already colored,
                // that's fine -- the edge crosses sides correctly.
            }
        }
    }

    if (bipartite) {
        cout << "YES\n";
        // Output 1-indexed side assignments
        for (int i = 0; i < n; i++) {
            // Isolated nodes (color still -1 if n=0 edges) go to side 1
            cout << (color[i] == -1 ? 0 : color[i]) + 1;
            cout << " \n"[i == n - 1];
        }
    } else {
        cout << "NO\n";
    }
}

DFS 2-Coloring (Alternative)

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<int> color;
bool bipartite;

void dfs(int u, int c) {
    color[u] = c;
    for (int v : adj[u]) {
        if (color[v] == -1) {
            dfs(v, c ^ 1);
        } else if (color[v] == c) {
            bipartite = false;
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    adj.resize(n);
    color.assign(n, -1);
    bipartite = true;

    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 0; i < n; i++)
        if (color[i] == -1) dfs(i, 0);

    cout << (bipartite ? "YES" : "NO") << "\n";
}

Extracting an Odd Cycle (When Not Bipartite)

Some problems ask you to output a proof -- an odd cycle. Track parents during BFS:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> color(n, -1), par(n, -1);
    bool bipartite = true;
    int cu = -1, cv = -1;  // conflict edge endpoints

    for (int s = 0; s < n && bipartite; s++) {
        if (color[s] != -1) continue;
        color[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty() && bipartite) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) {
                    color[v] = color[u] ^ 1;
                    par[v] = u;
                    q.push(v);
                } else if (color[v] == color[u]) {
                    bipartite = false;
                    cu = u; cv = v;
                }
            }
        }
    }

    if (!bipartite) {
        // Reconstruct odd cycle via LCA of cu and cv in the BFS tree
        vector<int> path_u, path_v;
        int a = cu, b = cv;

        // Trace both paths back to root, find meeting point
        vector<bool> on_path(n, false);
        for (int x = a; x != -1; x = par[x]) on_path[x] = true;
        int lca = -1;
        for (int x = b; x != -1; x = par[x]) {
            if (on_path[x]) { lca = x; break; }
        }

        vector<int> cycle;
        for (int x = a; x != lca; x = par[x]) cycle.push_back(x);
        cycle.push_back(lca);
        vector<int> tail;
        for (int x = b; x != lca; x = par[x]) tail.push_back(x);
        reverse(tail.begin(), tail.end());
        for (int x : tail) cycle.push_back(x);

        cout << cycle.size() + 1 << "\n";
        for (int x : cycle) cout << x + 1 << " ";
        cout << cycle[0] + 1 << "\n";  // close the cycle
    }
}

---

Operations Reference

Bipartite checking is just BFS/DFS with a color array -- the operations below show the cost of the check itself and the related constructions you might layer on top.

Operation	Time	Space
Build adjacency list	$O(n+m)$	$O(n+m)$
BFS 2-coloring	$O(n+m)$	$O(n)$
DFS 2-coloring	$O(n+m)$	$O(n)$ stack
Extract odd cycle	$O(n+m)$	$O(n)$
Check single edge for conflict	$O(1)$	--
Konig's theorem (given matching)	$O(n+m)$	$O(n)$

---

Problem Patterns & Tricks

Pattern 1: Direct Bipartite Check

The most common pattern. Given a graph, determine if it's 2-colorable.

Standard BFS/DFS coloring. Output "YES"/"NO" or the partition itself.

CF examples: CF 687A -- NP-Hard Problem, CF 1144F -- Graph Without Long Directed Paths

Pattern 2: Grid Checkerboard Coloring

Grid cells with 4-directional adjacency form a bipartite graph: color cell $(r,c)$ by $(r+c)mod2$. Black cells on one side, white cells on the other.

This unlocks max independent set on grids: it equals $n\cdot m-\text{max matching}$ by Konig's theorem.

// Checkerboard color of cell (r, c):
int side = (r + c) % 2;

    Checkerboard pattern -- why grids are always bipartite:

    4x4 grid colored by (row + col) % 2:

    col:  0     1     2     3
        +-----+-----+-----+-----+
    r=0 |  0  |  1  |  0  |  1  |
        +-----+-----+-----+-----+
    r=1 |  1  |  0  |  1  |  0  |
        +-----+-----+-----+-----+
    r=2 |  0  |  1  |  0  |  1  |
        +-----+-----+-----+-----+
    r=3 |  1  |  0  |  1  |  0  |
        +-----+-----+-----+-----+

    Every adjacent pair (up/down/left/right) differs:
      (r,c)=0 neighbors (r+1,c)=1, (r,c+1)=1  OK
      (r,c)=1 neighbors (r+1,c)=0, (r,c+1)=0  OK

    Graph view of a 2x3 sub-grid:

      [0](0,0) --- [1](0,1) --- [0](0,2)
        |              |              |
        |              |              |
      [1](1,0) --- [0](1,1) --- [1](1,2)

    Set A (color 0): *  -  *     Set B (color 1): -  *  -
                     -  *  -                      *  -  *

    All edges cross from Set A to Set B.
    No odd cycle possible -- grid is always bipartite.

CF examples: CF 1033C -- Permutation Game, CF 1354E -- Graph Coloring

Pattern 3: Edge Orientation for Bipartite

Given an undirected bipartite graph, orient all edges from left to right (or based on some constraint). Since no two nodes on the same side are adjacent, you can assign directions without conflicts.

CF examples: CF 1144F -- Graph Without Long Directed Paths

Pattern 4: Parity / Distance Mod 2

If a BFS tree has depth $d$ for every node, then nodes at even depth and nodes at odd depth form the bipartition. Two nodes are on the same side iff their BFS-distance from the root has the same parity.

This is critical for problems asking "can X reach Y in an even/odd number of steps?"

CF examples: CF 1092F -- Tree with Maximum Cost

Pattern 5: Bipartite + Konig for Min Vertex Cover

When a problem asks for the minimum set of nodes covering all edges in a bipartite graph, apply Konig's theorem: run max bipartite matching, then the answer equals the matching size.

Reconstruct the actual vertex cover by running alternating-path reachability from unmatched left nodes.

Max Matching = Min Vertex Cover (bipartite only)
Max Independent Set = n - Min Vertex Cover
Min Edge Cover = n - Max Matching  (if no isolated nodes)

CF examples: CF 1525D -- Armchairs

Pattern 6: Bipartite Coloring on Trees

Every tree is bipartite. Color by depth parity. This is useful when a tree problem has alternating constraints (e.g., "adjacent nodes must have different properties").

void dfs(int u, int p, int depth) {
    color[u] = depth & 1;
    for (int v : adj[u]) if (v != p) dfs(v, u, depth + 1);
}

Pattern 7: Detecting Bipartiteness Under Edge Additions (DSU)

Maintain bipartiteness dynamically using a weighted DSU. Each node stores its "distance parity" to the root. When merging, check if adding an edge creates an odd cycle.

// Weighted DSU: rank[x] = parity of distance from x to its root
int find(int x) {
    if (par[x] == x) return x;
    int root = find(par[x]);
    rank_[x] ^= rank_[par[x]];
    par[x] = root;
    return root;
}

bool unite(int u, int v) {
    int ru = find(u), rv = find(v);
    if (ru == rv) return (rank_[u] ^ rank_[v]) == 1;  // must be different parity
    par[ru] = rv;
    rank_[ru] = rank_[u] ^ rank_[v] ^ 1;
    return true;
}

CF examples: CF 1559D2 -- Mocha and Diana (Hard)

---

When to Reach for This

Bipartite checking shows up in more forms than the obvious "is this graph 2-colorable?" question:

• 2-coloring / two-team division: the direct application -- split nodes into two groups with no intra-group edges
• Scheduling with parity constraints: tasks alternate between two resource types; model as a graph, check bipartiteness
• Matching problems: bipartite matching (Kuhn, Hopcroft-Karp) requires a bipartite graph; verify first
• Conflict graphs: if conflicts only occur between two groups (not within), the conflict graph is bipartite
• Odd-cycle detection: determining whether a constraint system has a parity violation
• Grid problems: any grid with 4-directional adjacency is bipartite via checkerboard coloring -- exploit this for matching/cover

See also: BFS (BFS-based coloring), DFS and Tree DFS (DFS-based coloring), Graph Representation, Graph Modeling Guide.

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|  BIPARTITE GRAPHS  --  Quick Reference                           |
+------------------------------------------------------------------+
|  WHEN TO USE:                                                    |
|    - "Split into two groups, no conflicts within a group"        |
|    - Grid coloring problems (checkerboard = bipartite)           |
|    - Odd-cycle detection                                         |
|    - Matching / vertex cover / independent set on bipartite      |
|                                                                  |
|  CORE CHECK (BFS):                                               |
|    color[s] = 0; queue q; q.push(s);                             |
|    while (!q.empty()) { u = q.front(); q.pop();                  |
|      for (v : adj[u])                                            |
|        if (color[v]==-1) color[v]=color[u]^1, q.push(v);        |
|        else if (color[v]==color[u]) NOT_BIPARTITE; }             |
|                                                                  |
|  KEY THEOREM:                                                    |
|    Bipartite  <=>  No odd-length cycle                           |
|                                                                  |
|  KONIG'S THEOREM (bipartite only):                               |
|    Max Matching = Min Vertex Cover                               |
|    Max Independent Set = n - Max Matching                        |
|                                                                  |
|  COMPLEXITY:   O(n + m) time, O(n + m) space                    |
|  GRID TRICK:   side = (row + col) % 2                            |
+------------------------------------------------------------------+

---

Common Mistakes

Disconnected components. The number one bug. If you only BFS/DFS from node 0, you miss other components. Always loop over all nodes:

for (int i = 0; i < n; i++)
    if (color[i] == -1) { /* start BFS/DFS from i */ }

Self-loops. A self-loop $(u,u)$ means $u$ is adjacent to itself -- same-color conflict, so the graph is immediately not bipartite. Your coloring code handles this automatically only if you check color[v] == color[u] for all neighbors, including when $v=u$.

Multi-edges. Duplicate edges don't affect bipartiteness (if $u$-$v$ is fine once, it's fine twice). But they inflate $m$, so watch for TLE if you're not careful with adjacency list size.

1-indexed vs 0-indexed. The classic off-by-one. If the problem uses 1-indexed nodes, either subtract 1 when reading or allocate arrays of size $n+1$.

DFS stack overflow. For $n>{10}^5$, recursive DFS may hit the default stack limit. Use iterative BFS or increase the stack size. BFS is generally safer in contests for large graphs.

Isolated nodes. Nodes with no edges are trivially on either side. If your code leaves color[i] = -1 for isolated nodes, handle that when outputting the partition.

Printing the partition. Some problems want you to output which nodes are on which side. Remember: the choice of which side is "1" and which is "2" is arbitrary per component -- just be consistent.

Wrong graph type. Konig's theorem only holds for bipartite graphs. If you apply it to a general graph, you'll get wrong answers. Always verify bipartiteness first.

Edge between same-side nodes in bipartite matching. If you're building a bipartite matching model, make sure edges only go from left to right. An edge between two left-side nodes is a modeling error.

Mental Traps

Trap: "A graph with no cycles is the only kind of bipartite graph."

Trees have no cycles and are bipartite -- but graphs WITH even-length cycles are also bipartite. The correct statement: bipartite <=> no odd-length cycle. A cycle of length 4 or 6 is fine; a cycle of length 3 or 5 is fatal.

    BFS 2-coloring on a triangle (odd cycle -> conflict):

        1 ----------- 2
         \           /
          \         /
           \       /
            \     /
             \   /
               3

    Step 0: color[1]=0            Queue: < 1 >
    +------+-----+-----+-----+
    | Node |  1  |  2  |  3  |
    +------+-----+-----+-----+
    | Color|  0  |  -  |  -  |
    +------+-----+-----+-----+

    Step 1: pop 1, push neighbors 2, 3
            color[2] = 0 ^ 1 = 1
            color[3] = 0 ^ 1 = 1
            Queue: < 2, 3 >

        [0]1 ---------- [1]2
            \          /
             \        /
              \      /
               [1]3

    +------+-----+-----+-----+
    | Node |  1  |  2  |  3  |
    +------+-----+-----+-----+
    | Color|  0  |  1  |  1  |
    +------+-----+-----+-----+

    Step 2: pop 2, check neighbor 3
            color[3]=1  color[2]=1
            1 == 1
            +---> CONFLICT! same color on adjacent nodes
            |
            v  odd cycle: 1--2--3--1  (length 3)

        [0]1 ---------- [1]2
            \          /
             \  *##*  /   <-- conflict edge (2--3)
              \      /
               [1]3

    No starting node or recoloring fixes this.
    The triangle is structurally non-bipartite.

Trap: "I checked one component, so the whole graph is bipartite."

A graph is bipartite iff EVERY component is bipartite. One BFS from one source only checks one component. Nodes in other components might form odd cycles -- making the whole graph non-bipartite -- and you'd never know.

    Multi-component graph: component 1 is bipartite,
                           component 2 is NOT.

    Component 1                 Component 2
    (bipartite)                 (has triangle)

    [0]A -------- [1]B          [0]E --------- [1]F
     |                              \          /
     |                               \        /
    [1]C -------- [0]D                \      /
                                      [1]G

    BFS from A:                 BFS from E:
      A=0, B=1, C=1, D=0         E=0, F=1, G=1
      all edges cross sides       check edge F--G:
      +---> OK, bipartite           color[F]=1 == color[G]=1
                                    +---> CONFLICT!
                                    |
                                    v  triangle E-F-G (odd)

    If you only BFS from A and stop:
      verdict = "bipartite"  <-- WRONG!
    You must loop: for each unvisited node, start new BFS.

    +-----------------------------------------------+
    | for (int i = 0; i < n; i++)                   |
    |     if (color[i] == -1) bfs(i);  // *every*   |
    |                                   // component |
    +-----------------------------------------------+

Trap: "A same-color conflict means I colored wrong -- try a different starting node."

A conflict means an odd cycle exists. It is a structural property of the graph, not an artifact of your BFS order. No starting node or recoloring strategy will fix it. The conflict arises because a same-layer BFS edge forces two nodes at equal depth to be adjacent -- creating an odd cycle.

    Same-layer conflict detection:

    BFS layers from source S:

    Layer 0:       [0]S
                   / \
                  /   \
    Layer 1:  [1]A --- [1]B   <-- edge within same layer!
                               same color on both ends

    Why same-layer edge = odd cycle:

      S -> A  :  1 edge  (layer 0 -> layer 1)
      S -> B  :  1 edge  (layer 0 -> layer 1)
      A -> B  :  1 edge  (within layer 1)
      +----------------------------------+
      | cycle: S--A--B--S  length = 3    |
      | dist(S,A) + dist(S,B) + 1       |
      | = 1 + 1 + 1 = 3  (odd)          |
      +----------------------------------+

    General rule:
      edge between layers k and k = same-layer
      -> cycle length = k + k + 1 = 2k+1 (always odd)

    An edge between layer k and layer k+1 is fine:
      -> cycle length = k + (k+1) + 1 = 2k+2 (always even)

---

Self-Test

Before moving on, verify you can do each of these without looking at the material above:

1. Implement bipartite checking via BFS 2-coloring -- including the multi-component loop (for each unvisited node: start BFS) and the conflict detection (color[v] == color[u]). Write it from scratch in under 3 minutes.
2. State the odd cycle theorem: a graph is bipartite if and only if it has no odd-length cycles. Explain both directions of the proof in one sentence each.
3. Explain why a grid graph is always bipartite -- use the checkerboard argument: color(r,c) = (r+c) % 2, adjacent cells always differ by 1 in r+c.
4. Name one problem that reduces to bipartite checking (not matching) and describe the reduction in two sentences.
5. State Konig's theorem and explain why it only works for bipartite graphs. Give a counterexample on a general graph (hint: the triangle has matching 1 but vertex cover 2).
6. Trace BFS 2-coloring on a triangle (nodes 1-2-3-1). Write out queue state and colors at each step, and identify exactly where the conflict arises and which edge triggers it.
7. Given a graph with 3 components, explain why checking only one component is insufficient for declaring the whole graph bipartite. What could hide in the unchecked components?

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Building Teams	CSES	Easy	Direct bipartite check, output partition
2	NP-Hard Problem	CF 687A	Easy	Find bipartition or report impossible
3	Graph Without Long Directed Paths	CF 1144F	Easy-Med	Orient edges in bipartite graph
4	Graph Coloring	CF 1354E	Medium	Bipartite check per component + knapsack on partition sizes
5	Bertown Subway	CF 884C	Medium	Cycle structure, bipartite reasoning
6	DZY Loves Colors	CF 444C	Medium	Segment tree + coloring (bipartite-adjacent)
7	Balanced Lineup	CF 1450C1	Medium	Greedy on bipartite structure
8	Mocha and Diana	CF 1559D2	Med-Hard	DSU with parity for bipartite maintenance
9	Armchairs	CF 1525D	Med-Hard	DP on bipartite-like matching
10	Array and Operations	CF 498C	Hard	Bipartite matching with number theory

---

The Aha Moment

A graph is bipartite if and only if it has no odd-length cycles. This means 2-coloring isn't just a "trick" -- it's a structural certificate. If your BFS/DFS 2-coloring succeeds, you've proven the graph has a clean two-sided partition. If it fails, you've found an odd cycle -- a proof that no partition exists. Every bipartite problem reduces to: can I split things into two groups with constraints only between groups?

Pattern Fingerprint

Constraint / Signal	-> Use
"Divide into two groups with no intra-group conflict" ->	Bipartite check (2-coloring)
"Is the graph 2-colorable?" ->	BFS/DFS bipartite check
"Maximum matching in a two-sided assignment" ->	Bipartite matching (Kuhn / Hopcroft-Karp)
"Minimum vertex cover" in bipartite graph ->	Konig's theorem = max matching
Graph has only even-length cycles ->	It's bipartite
"Assign +1/-1 to nodes such that adjacent nodes differ" ->	2-coloring

Rating Progression

CF Rating	What You Should Be Comfortable With
1200	BFS/DFS 2-coloring, detecting if a graph is bipartite
1500	Bipartite check with DSU, finding the odd cycle witness, connected component bipartiteness
1800	Maximum bipartite matching (Kuhn's algorithm), Konig's theorem applications
2100	Hopcroft-Karp, minimum vertex cover / max independent set via Konig, weighted bipartite matching (Hungarian)

Before You Code Checklist

• [ ] Is the graph connected? If not, check each component independently -- one non-bipartite component makes the whole graph non-bipartite.
• [ ] Color array initialized to -1 (uncolored)? Using 0 as "uncolored" collides with color 0.
• [ ] Both directions added for undirected graphs? Missing a reverse edge can make a non-bipartite graph appear bipartite.
• [ ] Edge between same-color nodes = odd cycle. Are you checking color[v] == color[u] correctly?
• [ ] Matching array initialized to -1 (unmatched)? Using 0 collides with node 0.

What Would You Do If...?

1. ...the graph is given implicitly (e.g., "two people conflict if they share a trait")? Build the conflict graph explicitly, then run bipartite check. The graph structure matters, not how it's described.

2. ...you need to handle dynamic edge additions and maintain bipartiteness? Use DSU with parity (weighted DSU). Each edge adds a constraint "these two nodes must have different colors." A same-set, same-parity union means an odd cycle was found.

3. ...the problem says "assign values from {0, 1} to nodes minimizing adjacent same-value pairs"? If the graph is bipartite, the answer is 0 (perfect 2-coloring). If not, it becomes an NP-hard min-cut variant for general graphs -- look for special structure.

Debug This

Bug 1: Bipartite check always returns "Yes":

vector<int> color(n + 1, -1);
bool is_bipartite = true;
for (int i = 1; i <= n; i++) {
    if (color[i] != -1) continue;
    queue<int> q;
    color[i] = 0;
    q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (color[v] == -1) {
                color[v] = color[u] ^ 1;
                q.push(v);
            }
            if (color[v] == color[u]) {
                is_bipartite = false;
                // but doesn't break out of BFS!
            }
        }
    }
}

Answer

The code correctly detects the conflict (color[v] == color[u]) and sets is_bipartite = false, but it continues the BFS loop and may overwrite colors in subsequent iterations. Actually, the logic is correct -- it just doesn't break early, which is inefficient but not wrong. The real issue: change if (color[v] == color[u]) to else if (color[v] == color[u]) to avoid checking nodes that were just colored. As written, a freshly colored node with color[v] = color[u] ^ 1 won't trigger the conflict, so the code is actually correct but wastes time. If your answer is "this code is correct," you're right! Not every suspicious-looking code has a bug -- recognizing correct code is a skill too.

Bug 2: DSU-based bipartite check gives wrong answer:

int parent[MAXN], rank_[MAXN], dist[MAXN];  // dist = parity to root

int find(int x) {
    if (parent[x] == x) return x;
    parent[x] = find(parent[x]);
    // forgot to update dist[x] during path compression
    return parent[x];
}

Answer

During path compression, dist[x] (the parity/distance to root) must be updated. After find(parent[x]), the parity of x becomes dist[x] ^ dist[old_parent] (XOR with parent's parity to the new root). Fix: save the old parent, recurse, then dist[x] ^= dist[old_parent].

Bug 3: Bipartite matching returns 0 matches:

vector<int> match(n + 1, -1);
int result = 0;
for (int u = 1; u <= n; u++) {
    vector<bool> visited(n + 1, false);
    if (dfs_augment(u, visited)) result++;
}

bool dfs_augment(int u, vector<bool>& vis) {
    for (int v : adj[u]) {
        if (vis[v]) continue;
        vis[v] = true;
        if (match[v] == -1 || dfs_augment(match[v], vis)) {
            match[v] = u;
            // forgot match[u] = v;
            return true;
        }
    }
    return false;
}

Answer

Only match[v] = u is set (right side -> left side), but match[u] = v is never set. For Kuhn's algorithm to work, you need both directions so augmenting paths can check if the left node is already matched. However, note that Kuhn's algorithm typically only iterates over one side (left nodes), so match[u] may not be needed if the loop only tries left nodes. The actual bug depends on the exact implementation -- but best practice is to set both sides of the matching.

Historical Origin

The study of bipartite graphs dates to Denes Konig (1931), who proved the foundational theorem: in bipartite graphs, the maximum matching equals the minimum vertex cover. This Konig-Egervary theorem was one of the first results in combinatorial optimization and directly influenced the development of network flow theory.

Recap

"Two colors, no conflict -- that's bipartite."

• A graph is bipartite iff it has no odd-length cycle. Check via BFS/DFS 2-coloring in O(V + E).
• The classic bug: forgetting to loop over all components. One BFS from node 0 only checks one component.
• Self-loops immediately break bipartiteness. Even cycles are fine; odd cycles are fatal.
• Recognizing bipartiteness unlocks Konig's theorem (max matching = min vertex cover) and efficient matching algorithms.
• Grid problems with 4-directional adjacency are always bipartite -- use (r + c) % 2 coloring.
• When in doubt, build the conflict graph and check if it's 2-colorable.

---

Further Reading

• cp-algorithms: Bipartite Check -- BFS/DFS coloring with proof
• cp-algorithms: Kuhn's Algorithm -- maximum bipartite matching
• Konig's Theorem (Wikipedia) -- proof and applications
• CF Blog: Bipartite Matching and Flows -- contest-oriented treatment
• For maximum matching: see Bipartite Matching
• For flow-based approach: see Max Flow / Min Cut

Related topics in this book:

• Graph Representation -- adjacency list basics needed here
• BFS -- the traversal underneath BFS 2-coloring
• DFS and Tree DFS -- DFS-based coloring alternative
• Graph Modeling Guide -- reducing problems to bipartite structure
• Practice Ladder: Graphs

---

Appendix: The Proof -- Bipartite iff No Odd Cycle

This is worth understanding, not just memorizing. Two directions:

($\Rightarrow$) Bipartite implies no odd cycle.

Suppose the graph is bipartite with sides $L$ and $R$. Every edge goes $L\to R$ or $R\to L$. Walk along any cycle: each edge flips your side. After $k$ edges, you've flipped $k$ times. To return to your starting side, $k$ must be even. So every cycle has even length.

($\Leftarrow$) No odd cycle implies bipartite.

Run BFS from any node $s$, assigning $\text{color}[v]=\text{dist}(s,v)mod2$. Suppose for contradiction that some edge $(u,v)$ has $\text{color}[u]=\text{color}[v]$, meaning $\text{dist}(s,u)\equiv \text{dist}(s,v)(\mathrm{mod}2)$.

The BFS-tree path from $s$ to $u$ has length $\text{dist}(s,u)$. The BFS-tree path from $s$ to $v$ has length $\text{dist}(s,v)$. These paths share a common prefix up to some node $w$ (their LCA in the BFS tree). The cycle formed by:

$$s\to \cdots \to w\to \cdots \to u\to v\to \cdots \to w\to \cdots \to s$$

has length $(\text{dist}(s,u)-\text{dist}(s,w))+1+(\text{dist}(s,v)-\text{dist}(s,w))$. Since $\text{dist}(s,u)\equiv \text{dist}(s,v)(\mathrm{mod}2)$, this total is odd. But we assumed no odd cycle -- contradiction. So the BFS coloring must be valid, and the graph is bipartite. $◻$

---

Appendix: Konig's Theorem -- Why It Works

The full proof uses max-flow min-cut duality on a flow network built from the bipartite graph. Here's the intuition:

Build a flow network: source $S$ connects to all left nodes, all right nodes connect to sink $T$, and the bipartite edges go left-to-right. All capacities are 1.

         L1 ---- R1
        / |        \
  S ---  L2 ---- R2  --- T
        \ |        /
         L3 ---- R3

• Max flow = max bipartite matching (each augmenting path matches one pair)
• Min cut = min vertex cover (cutting a left node's edge from $S$ means "covering it"; cutting a right node's edge to $T$ means the same)

By the max-flow min-cut theorem, max matching = min vertex cover. This is Konig's theorem.

The maximum independent set follows immediately: removing a minimum vertex cover from $V$ leaves a set of nodes with no edges between them (since all edges were covered). So:

$$\text{Max Independent Set}=n-\text{Min Vertex Cover}=n-\text{Max Matching}$$

And the minimum edge cover (assuming no isolated nodes):

$$\text{Min Edge Cover}=n-\text{Max Matching}$$

These four quantities -- matching, vertex cover, independent set, edge cover -- are linked by Konig's theorem and its complement, forming the Konig-Egervary framework. In contests, if you can model your problem as bipartite, you unlock all four.