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

### Related post:

- Reisch receives SUNY Chancellor’s Award | News, Sports, Jobs – Evening Observer
- An overall 2nd place for Malta in an International Mental Mathematics Challenge – Malta Independent Online
- DU Admissions 2019: Mathematics Must In Best Of Four Subjects For Admission Into Eco(H); JMC, Stephen’s Stick To Old Rule – Swarajya
- Agami Education Foundation holds teachers’ training on Teaching Mathematics by Olympiad Technique – Dhaka Tribune
- 2nd place for Malta in international Mental Mathematics Challenge – Newsbook
- Darlington pupils among most-skilled mathematics in the UK – Darlington and Stockton Times
- Women and minority faculty in science, technology, engineering and mathematics (STEM) – Open Access Government
- The messy mathematics of British Columbia’s CleanBC plan – Business in Vancouver
- All Limerick student’s hard work adds up to him winning top mathematics award in Ireland – Limerick Leader
- CMU-Q researchers explore the mathematics of personalised medicine – The Peninsula Qatar