Matching

A matching M in a graph G=(V,E) is a subset of E such that there is no $u\in V$, $v_1\in V$, $v_2\in V$ such that $v_1\neq v_2$ and either $(u,v_1) \in M$ and $(u,v_2) \in M$, or $(v_1,u) \in M$ and $(v_2,u) \in M$.

In other words, no node is linked to two other nodes. It's a monogamy thing.

I'll use ``blue'' edges to refer to those in the matching M and ``white'' for the others.

Example...