7a:T4d8,// Type definitions for bipartite graphs interface BipartiteGraph { // The two partitions leftVertices: Set; // U: the 'left' partition rightVertices: Set; // W: the 'right' partition // Edges connecting left to right // Each edge goes from a left vertex to a right vertex edges: Map>; // 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( leftSet: Set, rightSet: Set, 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; }7b:T48d,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.7c:T756,// When BFS detection fails, it finds an odd cycle function findOddCycleIfExists( graph: Map, 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; }72:{"json":{"id":"seed_8419dd20c9e32afee15ea154b1f97df7","slug":"bipartite-graphs","category":"Data Structures & Algorithms","topic":"Bipartite Graphs","title":"Bipartite Graphs","description":"Master the theory and algorithms behind bipartite graphs — a fundamental graph structure with two disjoint vertex sets where edges only connect vertices from different sets. Learn to detect bipartiteness using two-coloring, understand BFS/DFS-based algorithms, and explore powerful applications in matching problems, scheduling, and beyond.","difficulty":"INTERMEDIATE","estimatedMinutes":60,"pages":[{"id":"seed_eef4f9d9290accab2cf660490b9b1b9f","title":"Definition of Bipartite Graphs","order":0,"content":[{"id":"opening-hook","title":"The World of Two-Partitioned Graphs","content":[{"data":{"content":"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.\n\nOr 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.\n\nThese 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."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"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.","variant":"info"},"type":"callout"}]},{"id":"formal-definition","title":"Formal Definition: What Makes a Graph Bipartite?","content":[{"data":{"content":"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."},"type":"text"},{"data":{"icon":"FileText","title":"Definition: Bipartite Graph","content":"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**.","variant":"note"},"type":"callout"},{"data":{"content":"Let's unpack each component of this definition:\n\n**1. Vertex Partition (U and W)**\n\nThe vertex set V must split into exactly two non-overlapping subsets. These are often called:\n- **Left vertices (U)** and **Right vertices (W)**\n- **Color 0** and **Color 1** (reflecting the two-coloring perspective)\n- **Part A** and **Part B**\n\nThe terminology varies, but the structure is always the same: every vertex belongs to exactly one of the two partitions.\n\n**2. Edge Constraint: Cross-Partition Only**\n\nThis 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.\n\n**3. Disjoint and Non-Empty**\n\nBoth 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."},"type":"text"},{"data":{"code":"$7a","title":"Bipartite Graph Type Definition","language":"typescript","showLineNumbers":true},"type":"code"},{"data":{"icon":"Lightbulb","title":"Alternative Definition via Colorability","content":"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.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"visual-representation","title":"Visual Representation and Intuition","content":[{"data":{"content":"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."},"type":"text"},{"data":{"code":" Left (U) Right (W)\n ┌─────────┐ ┌─────────┐\n │ │ │ │\n │ A ●━━━━━━━━━━━━━━━━● 1 │\n │ │╲ │ │\n │ B ●━━━━━━━━━━━━━━━━● 2 │\n │ │ ╲ │╱ │\n │ C ●━━━━━━━━━━━━━━━━● 3 │\n │ │ ╲ ╱│ │\n │ D ●━━━━━━━━━━━━━━━━● 4 │\n │ │ │ │\n └─────────┘ └─────────┘\n\n Edges shown: A-1, A-2, B-2, B-3, C-3, C-4, D-4\n \n Notice: Every edge crosses between columns.\n No edge connects two vertices in the same column.","title":"Standard Bipartite Graph Representation","language":"plaintext"},"type":"code"},{"data":{"content":"**Why this visual form is powerful:**\n\nWhen you draw a bipartite graph with left vertices in one column and right vertices in another:\n\n1. **Bipartiteness becomes immediately visible** — Any intra-column edge would instantly reveal the graph is not bipartite.\n\n2. **Matching problems become geometric** — Finding a maximum matching is like drawing the maximum number of non-crossing connections.\n\n3. **Relationships are clear** — In applications like job matching, you literally see 'employers on left, candidates on right, lines show who applied where.'\n\n**Contrast: The same graph drawn differently**\n\nThe same bipartite graph can be drawn in ways that hide its bipartite nature:"},"type":"text"},{"data":{"code":" A\n ╱ ╲\n ╱ ╲\n 1─────2\n ╱ ╲\n ╱ ╲\n D───────────B\n ╲ ╱\n ╲ ╱\n 4─────3\n ╲ ╱\n ╲ ╱\n C\n\n In this circular layout, bipartiteness is not obvious!\n But if we color: {A, B, C, D} = BLUE, {1, 2, 3, 4} = RED\n We see: Every edge connects BLUE to RED.\n \n The graph IS bipartite — the layout just obscured it.","title":"Same Bipartite Graph - Circular Layout (Structure Hidden)","language":"plaintext"},"type":"code"},{"data":{"icon":"Eye","title":"Don't Judge by Visual Appearance Alone","content":"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.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"fundamental-properties","title":"Fundamental Properties of Bipartite Graphs","content":[{"data":{"content":"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."},"type":"text"},{"data":{"items":["**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."],"title":{"icon":"Key","text":"Core Properties of Bipartite Graphs","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"content":"$7b"},"type":"text"},{"data":{"code":"$7c","title":"Odd Cycle Detection Reveals Non-Bipartiteness","language":"typescript","showLineNumbers":true},"type":"code"},{"data":{"icon":"Info","title":"Practical Implication","content":"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.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"special-cases","title":"Special Cases and Edge Cases","content":[{"data":{"content":"Understanding the edge cases of bipartite graphs helps solidify the definition and prevents subtle bugs in algorithms. Let's examine several important special cases:"},"type":"text"},{"data":{"content":"**Case 1: Empty Graph (No Edges)**\n\nA graph with vertices but no edges is **always bipartite**. We can assign vertices to partitions arbitrarily since there are no edge constraints to satisfy.\n\n```\nVertices: {A, B, C, D, E}\nEdges: ∅ (none)\n\nValid 2-coloring: Any assignment works!\nExample: U = {A, B, C}, W = {D, E}\nExample: U = {A}, W = {B, C, D, E}\nExample: U = {A, B, C, D, E}, W = {} ← Actually invalid! W must be non-empty.\n```\n\n*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."},"type":"text"},{"data":{"content":"**Case 2: Single Edge Graph**\n\nThe simplest non-trivial bipartite graph:\n```\nA ━━━━━ B\n\nPartition: U = {A}, W = {B}\n2-coloring: color(A) = 0, color(B) = 1\n```\n\nThis trivially satisfies all bipartite properties. More generally, any tree is bipartite because trees contain no cycles (hence, no odd cycles)."},"type":"text"},{"data":{"content":"**Case 3: Disconnected Graphs**\n\nA disconnected graph is bipartite if and only if **every connected component** is bipartite. We partition each component independently.\n\n```\nComponent 1: Component 2:\n A ━━ B X ━━ Y\n │ │ │ │\n D ━━ C Z ━━ W\n\nBoth components form 4-cycles (even cycles).\nBoth are bipartite independently.\nThe whole graph is bipartite.\n\nPartition: U = {A, C, X, Z}, W = {B, D, Y, W}\n```\n\nIf *any* component contains an odd cycle, the entire graph is non-bipartite."},"type":"text"},{"data":{"content":"**Case 4: Self-Loops**\n\nA **self-loop** (an edge from a vertex to itself) immediately makes a graph non-bipartite:\n\n```\nA ⟳ (self-loop on A)\n\nThis is an odd cycle of length 1!\nFor A's edge to cross partitions, A would need to be in BOTH U and W.\nThis is impossible, so the graph is not bipartite.\n```\n\n*Key insight:* Self-loops are the shortest possible odd 'cycle.' Any graph with self-loops is automatically non-bipartite."},"type":"text"},{"data":{"content":"**Case 5: Complete Bipartite Graphs (K_{m,n})**\n\nThe **complete bipartite graph K_{m,n}** has:\n- m vertices in partition U\n- n vertices in partition W \n- **Every possible edge** between U and W\n\n```\nK_{3,2}: Every left vertex connects to every right vertex.\n\n A ●━━━━━━━━━━━━━━● 1\n ╲ ╱\n B ●━━━╳━━━━━╳━━━● 2\n ╱ ╲\n C ●━━━━━━━━━━━━━━●\n\nEdges: A-1, A-2, B-1, B-2, C-1, C-2\nTotal: 3 × 2 = 6 edges\n```\n\nComplete bipartite graphs are extremely dense but still bipartite. They have **m × n** edges — the maximum possible while maintaining bipartiteness.\n\n**Special case: K_{n,n}**\nWhen both partitions have equal size, we get a **balanced complete bipartite graph**. These are important in matching theory — they always admit a perfect matching."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Simplest Non-Bipartite Examples","content":"**Triangle (K₃):** Three vertices, all connected. This 3-cycle is the smallest non-bipartite graph (excluding self-loops).\n\n**Pentagon (C₅):** A cycle of 5 vertices. Any odd cycle makes a graph non-bipartite.\n\nRemember: **Even** cycles (square, hexagon, octagon) are bipartite. **Odd** cycles are not.","variant":"tip"},"type":"callout"},{"data":{"rows":[["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"]],"caption":"Bipartiteness of Common Graph Structures","headers":["Graph Type","Bipartite?","Reason"]},"type":"table"}],"titleType":"number","titleNumber":4},{"id":"bipartite-in-algorithms","title":"Why Bipartite Graphs Matter Algorithmically","content":[{"data":{"content":"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."},"type":"text"},{"data":{"rows":[["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"]],"caption":"Problem Complexity: General vs. Bipartite Graphs","headers":["Problem","General Graphs","Bipartite Graphs"]},"type":"table"},{"data":{"content":"**Key insight: The Matching-Vertex Cover Duality**\n\nIn general graphs, maximum matching and minimum vertex cover are related but finding minimum vertex cover is NP-hard.\n\nIn bipartite graphs, **König's theorem** states:\n> Maximum matching size = Minimum vertex cover size\n\nThis 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.\n\n**Why does bipartiteness help?**\n\nThe 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."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Problem-Solving Strategy","content":"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').","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"real-world-examples","title":"Real-World Examples of Bipartite Graphs","content":[{"data":{"content":"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."},"type":"text"},{"data":{"items":["**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."],"title":{"icon":"Globe","text":"Bipartite Graphs in the Real World","type":"icon","color":"secondary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"Info","title":"Pattern Recognition","content":"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.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"summary","title":"Summary: Definition of Bipartite Graphs","content":[{"data":{"content":"We've established a comprehensive foundation for understanding bipartite graphs. Let's consolidate the key concepts:"},"type":"text"},{"data":{"type":"ordered","items":["**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."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nNow 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."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Foundation Complete","content":"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.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7}],"isLocked":false},{"id":"seed_7642940b33721b5a5d95ebec429c1228","title":"Two-Coloring Test","order":1,"content":null,"isLocked":true},{"id":"seed_1142e9a0044f18eadddb84f5d0ba2d87","title":"BFS/DFS-Based Detection","order":2,"content":null,"isLocked":true},{"id":"seed_c5ac5f4f0bc23e58ae69454b67afa4a2","title":"Applications — Matching Problems","order":3,"content":null,"isLocked":true}]}}