, 2023

Graph theoretic statement: in a balanced bipartite graph $G(V_1, V_2, E)$ with $n$ vertices on both parties, if there is no perfect matching but adding any other edges would lead to one, determine the number of vertices with degree $n$. We will show that this number is $n-1$.

(1) Since $G(V_1, V_2, E)$ has no perfect matching, by Hall's theorem, we know that there is some subset $U \subseteq V_1$ such that $|N(U)| < |U|$. Let $U' = V_2 - N(U)$, then since $n - |U'| = |N(U)| < |U|$, we have $|U| + |U'| \ge n + 1$.

(2) In addition, if there is some $(a, b) \in (V_1 \times V_2)$ such that $a$ is not a neighbor of $b$ but $(a, b) \notin (U \times U')$, then we may connect $ab$ and $G$ would still have no perfect matching by Hall's, which is a contradiction. Therefore we may assume that, for all $(a, b) \notin (U \times U')$, $a$ and $b$ are connected.

(3) Now, if $|U| + |U'| \ge n + 2$, we may connect an arbitrary $u \in U$ and an arbitrary $u' \in U'$, then $|N_{\{new\}}(U)| = |N_{\{old\}}(U)| + 1 = n + 1 - |U'| < U$, which means that the new graph still has no perfect matching (due to Hall's). This means that $|U| + |U'| = n + 1$.

(4) Combining (2) and (3), we know that $\text{deg}(v) = n$ if and only if $v \notin U \cup U'$, so the number of vertices with degree $n$ is $2n - (|U| + |U'|) = n - 1$.