Graph Matchings – The Math


Definition: For a graph $G = (V(G), E(G))$, a Matching is a subset $M subset E(G)$ where no two edges in $M$ share a vertex.

For example, suppose that we have a graph $G$ where $E(G) = { {a, b}, {a, c}, {a, d }, {b, c }, {c, d }, {c, e }, {e , f }$ we know that if $M = { { a, b }, {c, d }, {e, f} }$, we know that $M$ is a matching of $G$ since no edges in $M$ have a vertex in common. Now if we added the edge ${a, c }$ to $M$, then $M$ is no longer a matching since two edges in the set $M$ share the vertex $a$, and two edges also share the vertex $c$.

Visually, a matching of a Graph $G$ is similar. For example, the following graph $G$ and some possible matchings of $G$:

Screen%20Shot%202014-04-11%20at%203.44.34%20AM.png

In fact, this graph has another matching containing two vertices (can you find it?). Additionally, there are also $5$ matchings containing only one edge (since we could have $M$ contain only $1$ edge and there are $5$ edges total).



The math online

Leave a Comment

Your email address will not be published. Required fields are marked *