The Central Idea
A bipartite graph divides the vertex set into two disjoint parts,
\[ U \]and
\[ V, \]so that every edge joins one vertex from \(U\) to one vertex from \(V\).
A matching then chooses edges without allowing two chosen edges to share a vertex.
Definition of a Bipartite Graph
A graph \(G\) is bipartite if its vertex set can be written as
\[ V(G)=U\cup W, \]where
\[ U\cap W=\varnothing, \]and every edge has one endpoint in \(U\) and one endpoint in \(W\).
The Two Parts
The sets
\[ U \]and
\[ W \]are often called the parts, partite sets, or bipartition of the graph.
No edge may join two vertices within the same part.
A First Bipartite Graph
Let
\[ U=\{u_1,u_2,u_3\} \]and
\[ W=\{w_1,w_2,w_3\}. \]Suppose the edge set is
\[ E= \bigl\{ \{u_1,w_1\}, \{u_1,w_2\}, \{u_2,w_2\}, \{u_2,w_3\}, \{u_3,w_1\} \bigr\}. \]Every edge crosses from one part to the other, so the graph is bipartite.
A Bipartite Graph as a Picture
Bipartite Graphs and Two-Coloring
A graph is bipartite if and only if its vertices can be properly colored with at most two colors.
\[ \boxed{\text{bipartite}\iff\text{2-colorable}}. \]One color is assigned to all vertices in one part and the second color to all vertices in the other part.
Bipartite Graphs and Odd Cycles
A graph is bipartite if and only if it contains no odd cycle.
\[ \boxed{\text{bipartite}\iff\text{no odd cycle}}. \]Even cycles are compatible with a two-part structure because the vertices can alternate between the two parts.
Why Odd Cycles Fail
Suppose we alternate the two parts around an odd cycle.
After an odd number of edges, the final vertex is forced into the same part as the starting vertex even though those two vertices are adjacent.
That contradiction prevents a bipartition.
Complete Bipartite Graphs
The complete bipartite graph
\[ K_{m,n} \]has one part with \(m\) vertices and another part with \(n\) vertices, with every possible edge between the two parts.
It contains
\[ \boxed{mn} \]edges.
Example: \(K_{3,4}\)
The graph
\[ K_{3,4} \]has
\[ 3+4=7 \]vertices and
\[ 3\cdot4=12 \]edges.
What Is a Matching?
A matching is a set of edges in which no two selected edges share a vertex.
If \(M\subseteq E\), then \(M\) is a matching when every vertex is incident with at most one edge of \(M\).
Matched and Unmatched Vertices
A vertex is matched if it belongs to one of the selected matching edges.
A vertex not incident with any selected edge is unmatched.
A First Matching
In the running bipartite graph, consider
\[ M= \bigl\{ \{u_1,w_2\}, \{u_3,w_1\} \bigr\}. \]The two edges share no endpoint, so \(M\) is a matching.
Size of a Matching
The size of a matching is the number of selected edges.
For
\[ M= \bigl\{ \{u_1,w_2\}, \{u_3,w_1\} \bigr\}, \]we have
\[ \boxed{|M|=2}. \]Maximal Matching
A matching is maximal if no additional edge can be added without violating the matching condition.
Maximal means
\[ \boxed{\text{cannot be extended by one more edge}}. \]Maximum Matching
A matching is maximum if it has the largest possible size among all matchings of the graph.
\[ \boxed{ |M_{\max}|= \max\{|M|:M\text{ is a matching}\} }. \]Maximal and Maximum Are Different
Every maximum matching is maximal.
But a maximal matching need not be maximum.
A poor early choice may block additional pairings even though another matching of larger size exists.
Example: Maximal but Not Maximum
Suppose a path has vertices
\[ a-b-c-d. \]The matching
\[ \{\{b,c\}\} \]is maximal because neither \(\{a,b\}\) nor \(\{c,d\}\) can be added.
But
\[ \{\{a,b\},\{c,d\}\} \]has size \(2\), so the first matching is not maximum.
Perfect Matching
A perfect matching matches every vertex of the graph.
Each vertex belongs to exactly one selected edge.
In a bipartite graph with parts \(U\) and \(W\), a perfect matching pairs every vertex in both parts.
Perfect Matching Requires Equal Part Sizes
If a bipartite graph has a perfect matching, then the two parts must have the same number of vertices.
\[ \boxed{|U|=|W|}. \]This condition is necessary but not sufficient.
Matching One Side Completely
Sometimes the goal is not to match every vertex in both parts.
We may instead ask for a matching that saturates every vertex of one chosen part, such as assigning every worker to one available job.
Saturated Vertices
A vertex is saturated by a matching if it is incident with one selected matching edge.
To say that a matching saturates \(U\) means every vertex in \(U\) is matched.
Neighborhood of a Set
For a set of vertices
\[ S\subseteq U, \]let
\[ N(S) \]denote the set of vertices in the opposite part adjacent to at least one vertex of \(S\).
Why Neighborhood Size Matters
If \(k\) vertices in \(U\) are to be matched to distinct vertices in \(W\), then together they need at least \(k\) available neighbors.
Therefore,
\[ |N(S)|\ge|S| \]is a natural requirement for every subset \(S\subseteq U\).
Hall's Marriage Theorem
Hall's theorem gives a complete condition for matching every vertex of one part.
A bipartite graph with parts \(U\) and \(W\) has a matching that saturates every vertex of \(U\) if and only if
\[ \boxed{|N(S)|\ge|S|\text{ for every }S\subseteq U}. \]Hall's Condition
The inequality
\[ |N(S)|\ge|S| \]is called Hall's condition.
It prevents any group of vertices on one side from competing for too few possible partners on the other side.
Example: Hall Condition Fails
Suppose three vertices
\[ u_1,u_2,u_3 \]are collectively adjacent only to
\[ w_1,w_2. \]Then
\[ |S|=3 \]but
\[ |N(S)|=2. \]No matching can assign all three vertices to distinct partners.
Alternating Paths
Relative to a matching \(M\), an alternating path switches between edges not in \(M\) and edges in \(M\).
These paths are central to improving matchings.
Augmenting Paths
An augmenting path is an alternating path whose endpoints are unmatched.
It begins and ends with unmatched edges relative to the current matching.
Why Augmenting Paths Increase Matching Size
Along an augmenting path, replace:
- every matched edge by unmatched status;
- every unmatched edge by matched status.
Because the path begins and ends with unmatched edges, the new matching has one additional edge.
Example: Augmentation
Suppose an alternating path has edges in the pattern
\[ \text{unmatched}, \text{matched}, \text{unmatched}. \]Flipping their status changes one matched edge into two matched edges.
The matching size increases by
\[ \boxed{1}. \]Berge's Theorem
A matching \(M\) is maximum if and only if there is no augmenting path relative to \(M\).
\[ \boxed{ M\text{ is maximum} \iff \text{no augmenting path exists} }. \]This theorem provides a fundamental optimization criterion for matching.
Matching and Network Flow
Bipartite matching can be converted into a maximum-flow problem.
Add:
- a source \(s\) connected to every vertex in \(U\);
- directed versions of the bipartite edges from \(U\) to \(W\);
- edges from every vertex in \(W\) to a sink \(t\).
Give every edge capacity \(1\).
Why Unit Capacities Create Matchings
Capacity \(1\) from the source into a vertex of \(U\) prevents that vertex from being used more than once.
Capacity \(1\) from a vertex of \(W\) into the sink does the same on the other side.
Each unit of integral flow corresponds to one matched pair.
Maximum Matching from Maximum Flow
In the standard unit-capacity construction,
\[ \boxed{ \text{maximum matching size} = \text{maximum flow value} }. \]This connection lets flow algorithms solve bipartite matching problems.
Assignment Problems
Bipartite matching naturally models assignments between two different kinds of objects.
Examples include:
- workers and jobs;
- students and projects;
- drivers and routes;
- machines and tasks;
- applicants and positions;
- courses and available rooms.
Compatibility Graphs
In an assignment model, an edge may mean that a particular pairing is feasible.
A matching then selects a collection of mutually nonconflicting feasible assignments.
Weighted Matching
Some matching problems assign weights or costs to possible pairings.
The goal may be to find a maximum-weight matching or a minimum-cost perfect matching.
These weighted assignment problems extend the basic matching framework.
Perfect Matching versus Maximum Matching
A maximum matching has the largest possible number of edges.
A perfect matching covers every vertex.
A maximum matching may fail to be perfect when the graph structure prevents all vertices from being matched.
Unique and Nonunique Matchings
A graph may have several different maximum matchings of the same size.
A perfect matching, when it exists, may likewise be unique or may have several alternatives.
Bipartite Structure in Data
Many real systems naturally divide into two object types.
Representing the two types as separate parts makes structural restrictions explicit and often simplifies algorithms.
Common Error: Placing an Edge within One Part
In a bipartite graph, every edge must cross between the two parts.
An edge joining two vertices both in \(U\) or both in \(W\) violates the proposed bipartition.
Common Error: Confusing Bipartite with Complete Bipartite
A bipartite graph need not contain every possible cross-part edge.
Only \(K_{m,n}\) is complete bipartite.
Common Error: Allowing Matching Edges to Share a Vertex
If two selected edges share an endpoint, the selected set is not a matching.
Each vertex may participate in at most one selected matching edge.
Common Error: Confusing Maximal with Maximum
Maximal means no additional edge can be added directly.
Maximum means no larger matching exists anywhere in the graph.
Maximum is a global optimum; maximal is only a local stopping condition.
Common Error: Assuming Equal Part Sizes Guarantee a Perfect Matching
Equal sizes are necessary for a perfect matching in a bipartite graph, but the adjacency structure may still prevent one.
Hall's condition addresses the missing structural requirement.
Common Error: Checking Hall's Condition Only for Single Vertices
Hall's theorem requires
\[ |N(S)|\ge|S| \]for every subset
\[ S\subseteq U, \]not merely individual vertices.
A Reliable Procedure for Testing Bipartiteness
- Choose an uncolored vertex and assign it to one part.
- Assign all of its neighbors to the opposite part.
- Continue alternating across edges.
- If an edge ever joins two vertices forced into the same part, the graph is not bipartite.
- Repeat for additional connected components if necessary.
A Reliable Procedure for Building a Matching
- Choose an available edge.
- Match its two endpoints.
- Exclude other edges incident with those vertices from the current selection.
- Continue until no direct extension is possible.
- Then search for augmenting paths to determine whether the matching can be improved.
A Reliable Procedure for Checking a Perfect Matching
- Confirm the selected edges form a matching.
- Check that every vertex is incident with exactly one selected edge.
- In a bipartite graph, verify that both parts are fully saturated.
- If constructing rather than checking, use Hall's condition or augmenting-path methods when needed.
Example: Full Matching Workflow
Suppose
\[ U=\{u_1,u_2,u_3\} \]and
\[ W=\{w_1,w_2,w_3\}, \]with edges
\[ \{u_1,w_1\}, \{u_1,w_2\}, \{u_2,w_2\}, \{u_2,w_3\}, \{u_3,w_1\}. \]Choose
\[ \{u_3,w_1\}. \]Then choose
\[ \{u_1,w_2\}. \]Finally choose
\[ \{u_2,w_3\}. \]The three selected edges share no vertices and match all six vertices.
\[ \boxed{\text{This is a perfect matching of size }3}. \]Practice 1: Bipartite Meaning
What structural condition defines a bipartite graph?
Practice 2: Odd Cycle
A graph contains a cycle of length \(5\).
Can the graph be bipartite?
Practice 3: Complete Bipartite Edge Count
How many edges does
\[ K_{4,6} \]contain?
Practice 4: Matching Check
Are the edges
\[ \{a,x\},\qquad\{b,y\},\qquad\{c,z\} \]a matching if all six vertices are distinct?
Practice 5: Not a Matching
Are
\[ \{a,x\} \]and
\[ \{a,y\} \]allowed to appear together in a matching?
Practice 6: Perfect Matching
A bipartite graph has parts of sizes \(4\) and \(5\).
Can it have a perfect matching?
Practice 7: Hall Condition
A subset \(S\subseteq U\) has
\[ |S|=4 \]but
\[ |N(S)|=3. \]Can a matching saturate every vertex of \(U\)?
Practice 8: Augmenting Path
What happens to the size of a matching when we flip the edge status along an augmenting path?
Practice 9: Maximum Matching
A matching has no augmenting path relative to it.
What does Berge's theorem imply?
Practice 10: Identify the Error
A student says, “My matching is maximal, so it must be maximum.”
Explain the error.
Practice Answers
Practice 1
The vertices must be divisible into two disjoint parts so that every edge joins one part to the other.
\[ \boxed{\text{No edge may lie entirely within one part.}} \]Practice 2
A cycle of length \(5\) is odd.
Since bipartite graphs contain no odd cycles,
\[ \boxed{\text{No}}. \]Practice 3
A complete bipartite graph \(K_{m,n}\) has \(mn\) edges:
\[ 4\cdot6=24. \] \[ \boxed{24}. \]Practice 4
Yes. No two selected edges share an endpoint.
\[ \boxed{\text{Yes, they form a matching.}} \]Practice 5
No. Both edges use vertex \(a\).
\[ \boxed{\text{They cannot both belong to the same matching.}} \]Practice 6
No. A perfect matching would require every vertex in both parts to be paired, which is impossible when the part sizes differ.
\[ \boxed{\text{No perfect matching exists.}} \]Practice 7
Hall's condition fails because
\[ 3<4. \]Therefore,
\[ \boxed{\text{No matching can saturate all of }U}. \]Practice 8
Flipping the matched and unmatched status along an augmenting path increases the matching size by
\[ \boxed{1}. \]Practice 9
Berge's theorem states that a matching with no augmenting path is maximum.
\[ \boxed{\text{The matching is maximum.}} \]Practice 10
Maximal only means no single edge can be added directly.
Another matching with more edges may still exist.
\[ \boxed{\text{Maximal does not imply maximum.}} \]What to Remember
- A bipartite graph divides its vertices into two parts with edges only between the parts.
- A graph is bipartite exactly when it is 2-colorable.
- A graph is bipartite exactly when it has no odd cycle.
- \(K_{m,n}\) has \(mn\) edges.
- A matching is a set of edges with no shared endpoints.
- A maximal matching cannot be extended directly; a maximum matching has greatest possible size.
- A perfect matching matches every vertex.
- Hall's theorem characterizes when one side of a bipartite graph can be completely saturated.
- An augmenting path increases matching size by one.
- A matching is maximum exactly when no augmenting path exists.
- Bipartite matching can be solved through a unit-capacity maximum-flow construction.
Where We Go Next
Bipartite graphs and matchings model pairwise compatibility and assignment. The final lesson in this graph-and-network sequence broadens the viewpoint to large real-world systems whose vertices and edges represent interacting people, infrastructure, communications, and dependencies.
The next lesson, Social, Transportation, Communication, and Dependency Networks, applies graph structures and network methods across several important modeling domains.