Combinatorics • Topic 37

Matchings

Matchings deal with pairing elements in a graph without overlaps. They are central to assignment problems and network flows.

Definitions

Definition (Matching)

A matching

M

in a graph

G

is a set of edges without common vertices.

Maximal Matching: A matching that cannot be extended by adding another edge.
Maximum Matching: A matching with the largest possible number of edges.
Perfect Matching: A matching that covers every vertex in the graph. (Requires $∣ V ∣$ to be even).

In a bipartite graph

G = (U \cup V, E)

, we often want to match every vertex in

U

to a distinct vertex in

V

An augmenting path is a path that starts and ends at unmatched vertices and alternates between edges not in

M

and edges in

M

Berge's Lemma: A matching $M$ is maximum if and only if there is no augmenting path.

Exercise (Problem 1)

Does the complete graph

K_{5}

have a perfect matching? What about

K_{6}

Exercise (Problem 2)

Find a maximum matching in the cycle graph

C_{6}

. Is it perfect?

Exercise (Problem 3)

In a group of

n

people, some shake hands. Prove that the number of people involved in an odd number of handshakes is even. (Handshaking Lemma relation).