Intuition The one core ideaA bipartite graph is just a set of dots split into two teams where every connecting line jumps from one team to the other — never inside a team. Once you truly see that "two-team" picture, everything else (2-coloring, matching, Hopcroft–Karp) is a story about painting dots and drawing lines between the teams.
This page assumes you know nothing . Before you touch the parent note (topic) , we build every symbol it fires at you, one at a time, each anchored to a picture.
Everything in this topic is drawn from two ingredients: dots and lines connecting dots .
Definition Vertex (a "dot")A vertex is a single point that represents one thing — a person, a job, a city, a pixel. In pictures it is a filled circle. We usually give each a name like 1 , 2 , 3 a , b , x , y
The picture: a labelled blue circle sitting alone. That circle is the vertex.
Definition Edge (a "line")An edge is a line drawn between two vertices, meaning "these two things are connected / related / compatible." We write an edge between u v ( u , v )
The picture: a straight segment joining two circles. The line is the edge.
WHY we need both. The topic is entirely about relationships between things . A vertex holds a thing; an edge records a relationship. No other objects exist here — literally everything else is built from dots and lines.
The parent note opens with G = ( V , E )
V E G = ( V , E )
V set of all vertices (all the dots). "Set" just means "collection with no repeats."E set of all edges (all the lines).G = ( V , E ) G these dots and these lines ."
The picture: draw a loose blob around a handful of connected dots — that entire blob, dots plus lines, is G
Intuition Why bundle them into one letterG whole graph as input. Writing G = ( V , E ) G V E G
Two size symbols you'll see constantly:
Definition Neighbor / adjacencyTwo vertices are neighbors (or adjacent ) if an edge directly connects them. The set of u neighbors ( u ) a d j [ u ] u
The picture: stand on a dot; the neighbors are every dot you can reach by sliding along exactly one line.
Definition Path, cycle, and cycle length
A path is a trail of vertices connected edge-to-edge, no repeats: like 1 → 2 → 3
A cycle is a path that returns to where it started: 1 → 2 → 3 → 1
The length of a cycle = the number of edges in it (equal to the number of dots it visits).
The picture: a path is an open chain; a cycle is a closed loop. Count the segments (lines), not the dots, to get length.
Intuition Why "odd vs even length" will matter so muchThe whole bipartite test hinges on whether a loop has an even number of segments (you can two-team it) or an odd number (you can't). Look at the triangle in the figure: 3 segments = odd. The square: 4 segments = even. Hold that distinction — the parent note's deepest theorem is built on it.
Definition Connected vs disconnectedA graph is connected if you can walk from any dot to any other dot. If it splits into separate islands with no lines between them, it is disconnected ; each island is a component .
The picture: one blob = connected; two blobs with a gap = two components.
WHY it matters: the 2-coloring algorithm must restart on every island (one of the parent note's "common mistakes"). If you forget an island, you never color it.
Now we can state the star concept precisely.
Definition Partition intoL R partition V L R
L ∪ R = V ∪ together they cover every dot .L ∩ R = ∅ ∩ ∅ no dot is in both teams .
The picture: every dot is painted either "team-Left" or "team-Right," never both, never neither.
Intuition Why exactly two teams and not three?Because the natural real-world problems come in two kinds: workers/jobs, students/projects, buyers/sellers. Two teams is also the simplest structure where "matching one side to the other" becomes a clean, solvable question — which is the whole point of the topic.
A 2-coloring assigns each vertex one of two colors — call them 0 1
The picture: paint team L R
Intuition "Bipartite" and "2-colorable" are the SAME thing"Team Left / team Right" is exactly "color 0 / color 1." Choosing sides is choosing colors. So the parent note freely swaps between the words "bipartite" and "2-colorable" — they describe one identical picture. The related idea in general is Graph Coloring , which allows many colors; bipartite is the special 2-color case.
The parent's propagation rule color [ v ] = 1 − color [ u ] "give a neighbor the opposite color." With only two colors { 0 , 1 } 0 1 1 0 1 − 0 = 1 1 − 1 = 0 is the flip.
M matching M chosen subset of the edges such that no two chosen edges touch the same vertex . The symbol M ⊆ E M
The picture: highlight some lines in bold; if you never see two bold lines meeting at one dot, it's a valid matching. Think "each thing is paired with at most one partner."
Definition Matched, free, maximum
A vertex is matched if a bold (matching) edge touches it, else it is free (unmatched).
A maximum matching is a matching using the most possible edges.
The picture: bold lines pair up dots; leftover lonely dots are free. Maximum = as few lonely dots as possible.
Intuition Why "augmenting paths" (the parent's engine) existTo grow a matching you find a special zig-zag path that starts and ends on free dots and alternates non-bold, bold, non-bold... Flipping bold↔non-bold along it nets +1 pair. The deep guarantee that "no such path left = you're done" is Berge's Theorem . Getting these paths fast is what Hopcroft–Karp does, and the counting bound O ( E V )
O ( ⋅ ) O ( V + E ) BFS — BFS — explores a graph in expanding rings (nearest dots first). The 2-coloring test and Hopcroft–Karp's layering both use it.DFS — DFS — dives deep along one trail before backtracking. Used to extract augmenting paths.Flow view — Maximum Flow — bipartite matching is a special max-flow problem; useful for proofs.Beyond two teams — Blossom Algorithm handles matching in general (non-bipartite) graphs, where odd cycles ("blossoms") appear. König's Theorem — Königs Theorem — ties max matching to min vertex cover in bipartite graphs.
Bipartite two teams L and R
Hopcroft-Karp fast matching
Reveal each line only after you can answer it in your own words.
What is a vertex and what does it represent? A single dot standing for one thing (person, job, pixel).
What is an edge, and how is it written? A line connecting two vertices, written as the pair ( u , v )
What do V E G = ( V , E ) V E G
What do ∣ V ∣ ∣ E ∣ The number of vertices and the number of edges respectively.
What are the neighbors of a vertex u Every dot reachable from u
What is the length of a cycle? The number of edges (segments) in the closed loop.
Why does odd vs even cycle length matter? Even loops can be split into two teams; odd loops cannot, so an odd cycle means not bipartite.
What does it mean for a graph to be disconnected? It breaks into separate islands (components) with no edges between them.
What do L ∪ R = V L ∩ R = ∅ Every dot is in exactly one of the two teams — none missed, none in both.
State the bipartite condition in one sentence. Every edge has one endpoint in L R
Why is "bipartite" the same as "2-colorable"? Choosing team Left/Right is the same as painting color 0/1 so no edge joins same-colored dots.
What is a matching M A set of chosen edges where no two share a vertex — each thing paired with at most one partner.
What is a free (unmatched) vertex? A vertex that no matching edge touches.
What does O ( V + E ) Work grows in proportion to dots plus lines — each touched about once, no rescanning.
