# Graph Matching

**Definitions**

Definition

A

matchingof a graph is a set of edges in which no two edges share a common vertex.

Definition 2

In a matching $M$, a vertex $v$ is

saturatedby $M$ if $v$ is incident with an edge in $M$.

Definition 3

A matching is a

perfect matchingif it saturates every vertex.

If the graph does not have a perfect matching, how do we know we’ve got a maximum matching?

- We’ll look at a dual property with Graph Covers

Familiarize yourself with Graph Covers first.

Neighbour Set

Let $D⊆V(G)$. The

neighbour set$N(D)$ of $D$ is the set of all vertices adjacent to at least one vertex of $D$: $N(D)={v:uv∈E(G)∧u∈D}$

**Theorems and Lemmas**

Lemma 8.2.1

If $M$ is a matching of $G$ and $C$ is a cover of $G$, then $∣M∣≤∣C∣$.

Lemma 8.2.2

If $M$ is a matching and $C$ is a cover and $∣M∣=∣C∣$, then $M$ is a maximum matching and $C$ is a minimum cover.

Lemma 8.1.1

If a matching $M$ has an Augmenting Path, then $M$ is not maximum.

- An
*alternating path*$P$ with respect to a matching $M$ is a match where consecutively alternate between being in $M$ and not in $M$ - An
*augmenting path*is an alternating path that starts and ends with distinct unsaturated vertices

Given a matching $M$ and an augmenting path $P$, the new matching is $M_{′}=(M∪(E(P)\M))\(E(P)∩M)$

Konig's Theorem (Lemma 8.1.1)

In a bipartite graph, the size of a maximum matching is equal to the size of a minimum cover.

- Proven using the Bipartite Matching Algorithm

Corollary 1

Let $G$ be a Bipartite Graph on $m$ edges with bipartition $(A,B)$ such that $∣A∣=∣B∣=n$. Then $G$ has a matching of size at least $m/n$.

Hall's Theorem, Theorem 8.4.1

A bipartite graph $G$ with bipartition $(A,B)$ has a matching saturating every vertex in $A$ if and only if every subset $D⊆A$ satisfies $∣N(D)∣≥∣D∣$. (This is called “Hall’s condition”.)

Corollary 8.6.1

A Bipartite Graph $G$ with bipartition $(A,B)$ has a perfect matching if and only if $∣A∣=∣B∣$ and every subset $D⊆A$ satisfies $∣N(D)∣≥∣D∣$.

Theorem 8.6.2

If $G$ is a $k$-regular bipartite graph with $k≥1$, then $G$ has a perfect matching.