Graph Matchings

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$:

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).