Matching

Description:

• $M$, a subset $\in E$ such that no vertex in 𝑉 is on more than one edge in 𝑀
  • i.e. one $V$ has maximum one edge

Perfect matching:

• Every vertex in $V$ is on an edge in $M$

Maximum matching:

• Largest possible of $|M|$
• Hall’s Marriage Theorem can be used to find

Complete matching:

• $M$ such that every nodes in $V_1$ is matched (assumed $|V_1|\le |V_2|$)
• A complete match is a maximum match

Stable Matching Problem

---