Here is an only slightly more direct proof from convex duality and total unimodularity of the constraint matrix.

Let $G = (L \cup R, E)$ be a bipartite graph satisfying Hall's condition, where $|L| = |R| = n$. The matching polytope $P_G$ for this graph is the convex hull of the indicator vectors $x \in \mathbb{R}^E$ of all matchings, and can be written as:

$$ \forall v \in L \cup R: \sum_{e \ni v}{x_{e}} \leq 1\\ \forall e \in E: x_e \geq 0 $$

I.e., if $B$ is the incidence matrix of $G$, then $P_G = \{x: Bx \leq 1, x\geq 0\}$. Let us verify this is the matching polytope. It is clear that all matchings satisfy these constraints, and that all integral points in $P_G$ are matchings. Since the incidence matrix of a bipartite graph is easily seen to be totally unimodular, all vertices of $P_G$ are integral, and we are done.

A maximum cardinality matching in $G$ is naturally formulated as the linear optimization problem $\max\{1^Tx: x\in P_G\}$, whose dual is

$$ \min 1^Ty\\ \text{ subject to}\\ \\ \forall e=(u,v) \in E: y_u + y_v \geq 1\\ \forall u \in L \cup R: y_u\geq 0 $$

(Notice the solution to the above linear optimization problem is just the size of the minimum vertex cover of $G$.) By (strong) duality, which is a consequence of the Hahn-Banach theorem, $G$ has a matching of size $n$ if and only if the optimum of the above program is at least $n$. To prove Hall's theorem we must show that if the above optimization problem has optimal value strictly less than $n$, then Hall's condition is violated. Again by total unimodularity, an optimal solution is integral; let $y$ be optimal and take $S = \{u: y_u = 1\}$ and $S_L = S \cap L$, $S_R = S \cap R$. Since $y$ is feasible, $N_G(L \setminus S_L) = S_R$, and we have $$ |L \setminus S_L| = n - |S_L| = n - |S| + |S_R| > |S_R| = N_G(L \setminus S_L), $$ contradicting Hall's condition.

This approach gives König's theorem immediately, and you get Egerváry's theorem in the weighted case.

Here is an only slightly more direct proof from convex duality and total unimodularity of the constraint matrix.

Let $G = (L \cup R, E)$ be a bipartite graph satisfying Hall's condition, where $|L| = |R| = n$. The matching polytope $P_G$ for this graph is the convex hull of the indicator vectors $x \in \mathbb{R}^E$ of all matchings, and can be written as:

$$ \forall v \in L \cup R: \sum_{e \ni v}{x_{e}} \leq 1\\ \forall e \in E: x_e \geq 0 $$

I.e., if $B$ is the incidence matrix of $G$, then $P_G = \{x: Bx \leq 1, x\geq 0\}$. Let us verify this is the matching polytope. It is clear that all matchings satisfy these constraints, and that all integral points in $P_G$ are matchings. Since the incidence matrix of a bipartite graph is easily seen to be totally unimodular, all vertices of $P_G$ are integral, and we are done.

A maximum cardinality matching in $G$ is naturally formulated as the linear optimization problem $\max\{1^Tx: x\in P_G\}$, whose dual is

$$ \min 1^Ty\\ \text{ subject to}\\ \\ \forall e=(u,v) \in E: y_u + y_v \geq 1\\ \forall u \in L \cup R: y_u\geq 0 $$

(Notice the solution to the above linear optimization problem is just the size of the minimum vertex cover of $G$.) By (strong) duality, which is a consequence of the Hahn-Banach theorem, $G$ has a matching of size $n$ if and only if the optimum of the above program is at least $n$. To prove Hall's theorem we must show that if the above optimization problem has optimal value strictly less than $n$, then Hall's condition is violated. Again by total unimodularity, there exists an integral optimal solution; let $y$ be such a solution and take $S = \{u: y_u = 1\}$ and $S_L = S \cap L$, $S_R = S \cap R$. Since $y$ is feasible, $N_G(L \setminus S_L) = S_R$, and we have $$ |L \setminus S_L| = n - |S_L| = n - |S| + |S_R| > |S_R| = N_G(L \setminus S_L), $$ contradicting Hall's condition.

This approach gives König's theorem immediately, and you get Egerváry's theorem in the weighted case.

Here is an only slightly more direct proof from convex duality and total unimodularity of the constraint matrix.

Let $G = (L \cup R, E)$ be a bipartite graph satisfying Hall's condition, where $|L| = |R| = n$. The matching polytope $P_G$ for this graph is the convex hull of the indicator vectors $x \in \mathbb{R}^E$ of all matchings, and can be written as:

$$ \forall v \in L \cup R: \sum_{e \ni v}{x_{e}} \leq 1\\ \forall e \in E: x_e \geq 0 $$

I.e., if $B$ is the incidence matrix of $G$, then $P_G = \{x: Bx \leq 1, x\geq 0\}$. Let us verify this is the matching polytope. It is clear that all matchings satisfy these constraints, and that all integral points in $P_G$ are matchings. Since the incidence matrix of a bipartite graph is easily seen to be totally unimodular, all vertices of $P_G$ are integral, and we are done.

A maximum cardinality matching in $G$ is naturally formulated as the linear optimization problem $\max\{1^Tx: x\in P_G\}$, whose dual is

$$ \min 1^Ty\\ \text{ subject to}\\ \\ \forall e=(u,v) \in E: y_u + y_v \geq 1\\ \forall u \in L \cup R: y_u\geq 0 $$

(Notice the solution to the above linear optimization problem is just the size of the minimum vertex cover of $G$.) By (strong) duality, which is a consequence of the Hahn-Banach theorem, $G$ has a matching of size $n$ if and only if the optimum of the above program is at least $n$. To prove Hall's theorem we must show that if the above optimization problem has optimal value strictly less than $n$, then Hall's condition is violated. Again by total unimodularity, an optimal solution is integral; let $y$ be optimal and take $S = \{u: y_u = 1\}$ and $S_L = S \cap L$, $S_R = S \cap R$. Since $y$ is feasible, $N_G(L \setminus S_L) = S_R$, and we have $$ |L \setminus S_L| = n - |S_L| = n - |S| + |S_R| > |S_R| = N_G(L \setminus S_L), $$ contradicting Hall's condition.

Here is an only slightly more direct proof from convex duality and total unimodularity of the constraint matrix.

Let $G = (L \cup R, E)$ be a bipartite graph satisfying Hall's condition, where $|L| = |R| = n$. The matching polytope $P_G$ for this graph is the convex hull of the indicator vectors $x \in \mathbb{R}^E$ of all matchings, and can be written as:

$$ \forall v \in L \cup R: \sum_{e \ni v}{x_{e}} \leq 1\\ \forall e \in E: x_e \geq 0 $$

I.e., if $B$ is the incidence matrix of $G$, then $P_G = \{x: Bx \leq 1, x\geq 0\}$. Let us verify this is the matching polytope. It is clear that all matchings satisfy these constraints, and that all integral points in $P_G$ are matchings. Since the incidence matrix of a bipartite graph is easily seen to be totally unimodular, all vertices of $P_G$ are integral, and we are done.

A maximum cardinality matching in $G$ is naturally formulated as the linear optimization problem $\max\{1^Tx: x\in P_G\}$, whose dual is

$$ \min 1^Ty\\ \text{ subject to}\\ \\ \forall e=(u,v) \in E: y_u + y_v \geq 1\\ \forall u \in L \cup R: y_u\geq 0 $$

(Notice the solution to the above linear optimization problem is just the size of the minimum vertex cover of $G$.) By (strong) duality, which is a consequence of the Hahn-Banach theorem, $G$ has a matching of size $n$ if and only if the optimum of the above program is at least $n$. To prove Hall's theorem we must show that if the above optimization problem has optimal value strictly less than $n$, then Hall's condition is violated. Again by total unimodularity, an optimal solution is integral; let $y$ be optimal and take $S = \{u: y_u = 1\}$ and $S_L = S \cap L$, $S_R = S \cap R$. Since $y$ is feasible, $N_G(L \setminus S_L) = S_R$, and we have $$ |L \setminus S_L| = n - |S_L| = n - |S| + |S_R| > |S_R| = N_G(L \setminus S_L), $$ contradicting Hall's condition.

This approach gives König's theorem immediately, and you get Egerváry's theorem in the weighted case.