Minimum degree of a graph and existence of perfect matching

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.