Exercise 963Combinatorics › Graph theoryL1Added 3 Nov 2026

Matchings

#matching#bipartite#Hall

Statement

Define a matching and a perfect matching. Give an example of a bipartite graph with a perfect matching.

Hint

A matching is a set of pairwise non-adjacent edges.

Show solutionHide solution

Matching. Set of edges with no shared endpoint.

Perfect matching. Matching covering all vertices.

Example. $K_{2,2}$ with parts $\{a,b\}$ and $\{c,d\}$ : edges $ac,bd$ form a perfect matching (also $ad,bc$ ).

Conclusion. $K_{n,n}$ has a perfect matching for every $n\ge1$ .