| Requirement | Prove the following theorem: \newline |
| Proposition | Every regular bipartite graph has a perfect matching |
| Supporting content header | Useful Information |
| Supporting content | {\textbf {Definition 1.1}} A graph is said to be \textit{regular} if every node has the same degree \newline{\textbf {Definition 1.2}} A {\textit {bipartite}} graph is a graph together with a partition of its vertices into two sets, $L$ and $R$, such that every edge is incident to a vertex in $L$ and to a vertex in $R$. \newline{\textbf {Definition 1.3}} A bipartite graph $G$ with vertex partition $L$, $R$ where $\left| L \right| \leq \left| R \right|$ is \textit{degree-constrained} if $deg(l) \geq deg(r)$ for every $l \in L$ and $r \in R$ \newline{\textbf {Definition 1.4}} A matching is \textit{perfect} if every vertix in the graph is incident to an edge in the matching \newline{\textbf {Definition 1.5}} A matching \textit{covers} a set $L$ if and only if each vertex in $L$ has an edge of the matching incident to it.\newline{\textbf {Theorem.}} Let $G$ be a bipartite graph with vertex partition $L$, $R$ where $\left|L\right| \leq \left|R\right|$. If $G$ is degree-constrained, then there is a matching that covers $L$. |
| Proof | Let $G$ be a regular bipartite graph with vertex partition $L$, $R$ where $\left|L\right| \leq \left|R\right|$. \begin{enumerate}\item Since regular graphs are degree-constrained, we know by the supporting theorem that there must be a matching in $G$ that covers $L$. \item Since $G$ is regular, we also know that $\left|L\right| = \left|R\right|$ and thus the matching must also cover $R$. \item This means that every node in $G$ is incident to an edge in the matching and thus $G$ has a perfect matching.\end{enumerate} |
| Subject | DISCRETE MATH |
| Tags | bipartite_graphs chapter_5 graph_theory matchings proof |