Minimum degree of a graph and existence of perfect matching

I was reading a result where the following proposition appears as a preliminary step (and left as exercise):

Claim: Suppose $G$ is a graph on $n$ vertices ($n$ even and $n \geqslant 3$) with minimum degree at least $n/2$. Show that $G$ contains a perfect matching.

Proof: By Dirac's theorem, $G$ has a Hamiltonian cycle $C$. Since $|C|=n$ is an even integer, the set of “odd” edges of $C$ gives a perfect matching for $G$. $\quad\Box$

I feel that using Dirac's theorem for this claim is an overkill. But after trying for a few days, couldn't come up with any other proofs. Can you give a more “direct” proof of the claim that avoids the machinery of Hamiltonian cycles?

Naturally, you might object to the vague requirement of “directness”. To clarify what I mean by it, I’ll give an example.

Claim 2. Suppose $G$ has a minimum degree at least $n/2$. Show that $G$ is connected.

Proof via Dirac's theorem. $G$ has a hamiltonian cycle as before, and hence is connected. $\Box$

A different proof. We'll show that any pair of vertices $u,v$ are connected by a path of length at most $2$. If $uv$ is an edge, we are done. Suppose not. Then $N(u) \cup N(v) \subseteq V \smallsetminus \{u,v\}$. Therefore $$ |N(u) \cap N(v)| = |N(u)| + |N(v)| - |N(u) \cup N(v)| \geqslant \frac{n}{2}+\frac{n}{2}-(n-2) = 2 \gt 0. $$ In particular there exists vertex $w$ such that $uw$ and $wv$ are both edges, and we are done. $\quad \Box$

I find the proof via Dirac's theorem much less illuminating in this example. In fact, as Qioachu points out below, the Claim 2 might even appear as an intermediate steps of Dirac’s theorem, making the above proof cyclic. My intention here is only to point out that Dirac’s theorem can be used as a powerful black box in killing much easier results.

Here's an alternative proof using Hall's theorem -- I don't know whether that counts as a more "direct" proof, but at least it uses a theorem that directly deals with perfect matchings instead of a detour (pun intended) through Hamiltonian cycles.

Arbitrarily divide the vertices into two sets $A$ and $B$ of equal size. In each set, find a vertex with a minimal number of edges connecting it to the other set, and swap the two minimal vertices. Repeat this until the swap would no longer increase the total number of edges connecting the two sets. (Since there is a finite number of edges, this must happen at some point.) Denoting the two vertices whose swap would no longer increase the number of connections by $v_A$ and $v_B$ and the numbers of their edges within and between the sets by $v_{AA}$, $v_{AB}$, $v_{BA}$ and $v_{BB}$, and counting the number of connections between the sets before and after the swap, we have $v_{AB}+v_{BA}\ge v_{AA}+v_{BB}$. (There might be an edge between $v_A$ and $v_B$, but that works in favour of the inequality.) It follows that

$$v_{AB}+v_{BA}\ge \frac12(v_{AB}+v_{BA}+v_{AA}+v_{BB})=\frac12(\deg v_A+\deg v_B)\ge \frac12(n/2+n/2)=n/2\;.$$

Now consider a subset $X$ of $A$. If $|X|\le v_{AB}$, then since each element of $A$ has edges to at least $v_{AB}$ elements of $B$, $X$ has at least as many neighbours in $B$ as elements. If $|X|>v_{AB}$, then since each element of $B$ has edges to at least $v_{BA}$ elements of $A$ and $v_{AB}+v_{BA}\ge n/2=|A|$, at least one of these edges must lead to $X$, so $X$ has $n/2$ neighbours in $B$, and thus at least as many as it has elements. Thus the premise of Hall's theorem is fulfilled, and the bipartite graph induced on $A$ and $B$ must contain a perfect matching, which is also a perfect matching in $G$.

I believe it might be possible to provide a simpler proof by induction. Conisder the minimal situation where each vertex has degree $n/2$.

For the first case, $n=4$, this is equivalent to $C_4$ and there is an obvious perfect matching, and adding more edges between the vertices does not affect the existence of a matching.

Now consider the operation of adding 2 vertices ($u$ and $v$) and enough edges to a graph (which already contains a perfect matching) to fulfill the $n/2$ condition. If there is an edge between $u$ and $v$ add that edge to the matching and the matching is perefct.

If there is not an edge between the two new vertices then they must share at least 2 neigbors ($y$ and $z$) because there are $n$ original vertices and $u$ and $v$ must each dominate $\frac {n+2}{2}$ of these vertices. There are three further cases to consider.

Case 1 If the edge $yz$ is in the original matching then WLOG replace $yz$ with $uy$ and $vz$ and the matching is again perfect.

Case 2 If the edge $yz$ is not in the original matching and $u$ and $v$ share only 2 neighbors then create an augmenting path as follows: Select an alternating path from $y$ to $z$ taking the matched edge from $y$ as the first edge in the path. The vertex that is matched to $z$ ($p$) must be adjacent to either $u$ or $v$ because by only sharing 2 common neighbors $u$ and $v$ cover all of the vertices. WLOG assume the $v$ is adjacent $p$ and add $zp$ and $pv$ to the path. Add the edge $uy$ and the path becomes an augmenting path that when the edges are flipped creates a perfect matching.

Case 3 If $u$ and $v$ share more than 2 neighbors they must be adjacent to both ends of a matched edge. As in case 1 above you may remove that edge from the matching and replace with two edges of your choice attaching one of each $u$ and $v$ to an vertex from the previous matching.

With Bogumil Kaminski, I am writing a book for high school students and we asked this question there. For simplicity, we assumed that the number of vertices is even but, of course, the same argument works for odd case.

Suppose that $G=(V,E)$ is a graph on $|V|=2n$ vertices and the minimum degree, $\delta=\delta(G) \ge n$. Our goal is to show that $G$ has a perfect matching.

We will construct a perfect matching in $n$ rounds, distinguishing two phases. During the first phase, we apply a trivial, greedy algorithm to construct a maximal matching, that is, a matching that cannot be extended by adding an edge. We start with an empty matching $M_0 = (\emptyset, \emptyset)$. In each round $i$, we consider the graph $G[V \setminus V(M_{i-1})]$ induced by unsaturated vertices. If it contains edges, then we arbitrarily pick one of them (say, edge $a_i b_i$) and add it to the current matching; that is, $V(M_i) = V(M_{i-1}) \cup \{a_i, b_i\}$ and $E(M_i) = E(M_{i-1}) \cup \{a_i b_i\}$. This phase ends if there are no more edges to pick from. If all the vertices are saturated, then we are done; otherwise, we move on to the second phase.

During the second phase, at the beginning of each round $i \le n$, set $V \setminus V(M_{i-1})$ contains at least two vertices and it induces an independent set. We pick \emph{any} two vertices, say, $p$ and $q$ from that set. We will show that there is an edge in $E(M_{i-1})$, say, $r s$ such that $p r \in E$ and $q s \in E$. In other words, we will show that there exists a path $(p, r, s, q)$ of length 3 (such paths are often called \textbf{augmenting paths}). The existence of such paths allows us to improve the size of our matching. Indeed, we can simply remove $r s$ from the matching and add edges $pr$ and $qs$ instead. Formally, $V(M_i) = V(M_{i-1}) \cup \{p, q\}$ and $E(M_i) = (E(M_{i-1}) \setminus \{rs\}) \cup \{pr, qs\}$.

To finish the proof, let us note that $p$ has at least $n$ neighbours in $V(M_{i-1})$ (since $\delta \ge n$ and $V \setminus V(M_{i-1})$ induces an independent set). Let $R := N(p) \subseteq V(M_{i-1})$, and let $S$ be the set of vertices matched with vertices from $R$, that is, $S = \{ s \in V(M_{i-1}) : sr \in E(M_{i-1}) \text{ for some } r \in R \}$. Clearly, $|S|=|R| \ge \delta \ge n$. Moreover, $S$ and $R$ can overlap (and, in fact, they do) but it causes no problem. More importantly, since $q$ has at least $n$ neighbours in $V(M_{i-1})$, $|S| \ge n$, and $|V(M_{i-1})| \le 2n-2$, it follows that $q$ has at least one neighbour in $S$ which finishes the argument.