Graph Matchings

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