Course contentsShow
← Mathematics
Lesson 2699 of 3,12153. Graph TheoryFree lesson

Matchings in Graphs: Definitions and Basic Properties

Define matchings, maximum matchings, perfect matchings, and maximal matchings with examples in bipartite and general graphs.

Matchings in Graphs: Definitions and Basic Properties

What you'll learn: You'll understand what matchings are in graphs and how to distinguish between different types of matchings.

What is a Matching?

A matching in a graph is a set of edges with no shared vertices—in other words, no two edges in the matching are adjacent to the same vertex. Think of it like pairing up people for a dance: each person can dance with at most one partner, and no person can be in two pairs simultaneously.

Types of Matchings

Maximal Matching

A maximal matching is a matching where you cannot add any more edges without violating the matching property. It's "locally complete"—every possible addition would create a conflict. Note that maximal doesn't mean it's the largest possible; it just means you can't extend it further.

Example: In a path graph with 4 vertices (v₁—v₂—v₃—v₄), the matching {(v₁,v₂)} is maximal (you can't add (v₃,v₄) without... wait, you actually can!). Better example: {(v₁,v₂), (v₃,v₄)} is maximal because adding any remaining edge would share a vertex.

Maximum Matching

A maximum matching contains the largest possible number of edges among all matchings in the graph. This is "globally optimal."

Example: In the complete bipartite graph K₃,₃, a maximum matching has 3 edges, pairing each vertex from one partition to exactly one vertex in the other.

Perfect Matching

A perfect matching covers every single vertex in the graph—everyone gets paired. This can only exist in graphs with an even number of vertices, and it's automatically a maximum matching.

Example: In K₄ (complete graph on 4 vertices), the edges {(v₁,v₂), (v₃,v₄)} form a perfect matching.

Key Takeaway: A matching pairs vertices without overlap; maximal means locally complete, maximum means globally largest, and perfect means everyone is matched.