[proofplan] We orient every edge from the left part $U$ to the right part $W$ and compare the resulting directed incidence matrix with the unsigned vertex-edge incidence matrix that defines the degree constraints. The directed incidence matrix is totally unimodular by a determinant expansion argument, and multiplying rows by $-1$ preserves total unimodularity, so the degree constraint matrix is totally unimodular. We then include the non-negativity constraints and prove directly, using Cramer's formula, that every vertex of the resulting polyhedron is integral. Finally, the integral feasible points are exactly incidence vectors of matchings, which identifies the linear program with the maximum weight matching problem. [/proofplan] [step:Encode the degree constraints by an unsigned incidence matrix] Let $V := U \sqcup W$ be the vertex set of $G$. Define the unsigned incidence matrix $N \in \mathbb{R}^{V \times E}$ as follows: for $v \in V$ and $e \in E$, set $N_{v,e}:=1$ if $e \in \delta(v)$, and set $N_{v,e}:=0$ if $e \notin \delta(v)$. Let $\mathbb{1}_V \in \mathbb{R}^{V}$ denote the vector whose every coordinate is $1$. With this notation, \begin{align*} Q_M(G)=\{x \in \mathbb{R}^{E}: Nx \leq \mathbb{1}_V,\; x \geq 0\}. \end{align*} Orient each edge $e \in E$ from its endpoint in $U$ to its endpoint in $W$. Define the directed incidence matrix $B \in \mathbb{R}^{V \times E}$ as follows: for $v \in V$ and $e \in E$, set $B_{v,e}:=1$ if $v \in U$ and $e \in \delta(v)$, set $B_{v,e}:=-1$ if $v \in W$ and $e \in \delta(v)$, and set $B_{v,e}:=0$ if $e \notin \delta(v)$. Define the diagonal matrix $D \in \mathbb{R}^{V \times V}$ as follows: for $v \in V$, set $D_{v,v}:=1$ if $v \in U$ and set $D_{v,v}:=-1$ if $v \in W$; for distinct vertices $v,v' \in V$, set $D_{v,v'}:=0$. For every $v \in V$ and $e \in E$, the equality $N_{v,e}=D_{v,v}B_{v,e}$ holds. Hence \begin{align*} N = DB. \end{align*} [/step] [step:Prove total unimodularity of the bipartite degree matrix] A real matrix is called totally unimodular if every square submatrix has determinant in $\{-1,0,1\}$. [claim:The directed incidence matrix $B$ is totally unimodular] Every square submatrix of $B$ has determinant in $\{-1,0,1\}$. [/claim] [proof] Let $A$ be a $k \times k$ square submatrix of $B$. We prove the assertion by induction on $k$. For $k=1$, each entry of $A$ belongs to $\{-1,0,1\}$, so $\det A \in \{-1,0,1\}$. Assume $k \geq 2$ and the assertion has been proved for all smaller square submatrices of $B$. If some column of $A$ has no non-zero entries, then $\det A=0$. If some column of $A$ has exactly one non-zero entry, expanding $\det A$ along that column expresses $\det A$ as $\pm \det A'$, where $A'$ is a $(k-1)\times(k-1)$ square submatrix of $B$. By the induction hypothesis, $\det A' \in \{-1,0,1\}$, and therefore $\det A \in \{-1,0,1\}$. It remains to consider the case where every column of $A$ has at least two non-zero entries. Since each column of the full directed incidence matrix $B$ has exactly two non-zero entries, one equal to $1$ and one equal to $-1$, every column of $A$ has exactly these two entries. Thus the sum of all rows of $A$ is the zero row vector in $\mathbb{R}^{k}$. The rows of $A$ are linearly dependent, so $\det A=0$. This completes the induction. [/proof] Since $N=DB$ and $D$ only multiplies rows by signs, every square submatrix of $N$ has determinant equal to the determinant of the corresponding square submatrix of $B$, multiplied by a sign. Therefore $N$ is totally unimodular. [guided] The reason for orienting the graph is that signed incidence matrices have a determinant structure that is easy to control. We prove this from first principles. A real matrix is totally unimodular if every square submatrix has determinant $-1$, $0$, or $1$. Let $A$ be a $k \times k$ square submatrix of the directed incidence matrix $B$. We use induction on $k$. If $k=1$, then $A$ consists of a single entry of $B$, and every entry of $B$ is $-1$, $0$, or $1$, so the determinant condition holds. Now assume $k \geq 2$. If a column of $A$ is the zero column, then $\det A=0$. If a column of $A$ has exactly one non-zero entry, then Laplace expansion along that column gives \begin{align*} \det A = \pm \det A', \end{align*} where $A'$ is a $(k-1)\times(k-1)$ square submatrix of $B$. The induction hypothesis gives $\det A' \in \{-1,0,1\}$, hence $\det A \in \{-1,0,1\}$. The only remaining possibility is that every column of $A$ has at least two non-zero entries. But each column of the full directed incidence matrix $B$ corresponds to one oriented edge from $U$ to $W$, so it has exactly one $1$ and exactly one $-1$. Therefore every column of $A$ contains both of these entries. Summing all rows of $A$ gives the zero row vector because the entries in each column add to $1+(-1)=0$. Hence the rows of $A$ are linearly dependent, and $\det A=0$. Thus every square submatrix of $B$ has determinant in $\{-1,0,1\}$, so $B$ is totally unimodular. Finally, the unsigned degree matrix $N$ is obtained from $B$ by multiplying every row indexed by $W$ by $-1$. Multiplying rows by signs multiplies any square determinant by a sign, so the set of possible determinant values remains $\{-1,0,1\}$. Hence $N$ is totally unimodular. [/guided] [/step] [step:Add the non-negativity constraints without losing total unimodularity] Define the full constraint matrix $C \in \mathbb{R}^{(V \sqcup E)\times E}$ by declaring its row indexed by $v \in V$ to be the row $N_{v,\cdot}$ of $N$, and its row indexed by $e \in E$ to be the row $-(I_E)_{e,\cdot}$ of $-I_E$, where $I_E \in \mathbb{R}^{E \times E}$ is the identity matrix indexed by $E$. Define $b \in \mathbb{R}^{V \sqcup E}$ by \begin{align*} b_v := 1 \text{ for } v \in V, \qquad b_e := 0 \text{ for } e \in E. \end{align*} Then \begin{align*} Q_M(G)=\{x \in \mathbb{R}^{E}: Cx \leq b\}. \end{align*} We claim that $C$ is totally unimodular. Let $A$ be a square submatrix of $C$. If $A$ uses no row from $-I_E$, then $A$ is a square submatrix of $N$, so $\det A \in \{-1,0,1\}$. If $A$ uses a row from $-I_E$, then that row has either no non-zero entry inside the selected columns, in which case $\det A=0$, or exactly one non-zero entry, equal to $-1$. Expanding along such rows successively reduces $\det A$ to $0$ or to $\pm \det A_0$, where $A_0$ is a square submatrix of $N$. Since $N$ is totally unimodular, $\det A_0 \in \{-1,0,1\}$, and hence $\det A \in \{-1,0,1\}$. Thus $C$ is totally unimodular. [/step] [step:Use total unimodularity to prove that every vertex is integral] Let $x_0 \in Q_M(G)$ be a vertex. We first justify the active-constraint reduction. Let $R(x_0) \subset \mathbb{R}^{E}$ be the set of row vectors of $C$ whose inequalities are active at $x_0$. If $\operatorname{span} R(x_0) \neq \mathbb{R}^{E}$, choose a non-zero vector $h \in \mathbb{R}^{E}$ orthogonal to every row in $R(x_0)$. For all constraints inactive at $x_0$, strict slack and finiteness of the constraint list imply that there exists $\varepsilon>0$ such that $x_0+th \in Q_M(G)$ for every $t \in (-\varepsilon,\varepsilon)$. For active constraints, orthogonality gives equality along the whole segment. Hence $x_0$ lies in a non-trivial line segment contained in $Q_M(G)$, contradicting that $x_0$ is a vertex. Therefore the active constraint normals span $\mathbb{R}^{E}$. Choose $|E|$ linearly independent active rows. They form a square nonsingular submatrix $C_0 \in \mathbb{R}^{E \times E}$ of $C$, with a corresponding vector $b_0 \in \mathbb{Z}^{E}$ of active right-hand sides, such that \begin{align*} C_0 x_0 = b_0. \end{align*} Because $C$ is totally unimodular and $C_0$ is nonsingular, \begin{align*} \det C_0 \in \{-1,1\}. \end{align*} By [Cramer's formula](/page/Cramer's%20Rule), for each $e \in E$ the coordinate $(x_0)_e$ equals \begin{align*} (x_0)_e = \frac{\det C_{0,e}}{\det C_0}, \end{align*} where $C_{0,e}$ is the matrix obtained from $C_0$ by replacing the column indexed by $e$ with $b_0$. Since $C_0$ and $b_0$ have integer entries, $\det C_{0,e} \in \mathbb{Z}$. Since $\det C_0=\pm 1$, it follows that $(x_0)_e \in \mathbb{Z}$ for every $e \in E$. Hence $x_0 \in \mathbb{Z}^{E}$. [/step] [step:Identify the integral feasible points with matchings] Let $x \in Q_M(G) \cap \mathbb{Z}^{E}$. Since $x_e \geq 0$ for every $e \in E$ and, for any endpoint $v$ of $e$, the constraint \begin{align*} \sum_{f \in \delta(v)} x_f \leq 1 \end{align*} holds, we have $x_e \leq 1$. Thus $x_e \in \{0,1\}$ for every $e \in E$. Define \begin{align*} M_x := \{e \in E : x_e=1\}. \end{align*} For every vertex $v \in V$, the inequality \begin{align*} \sum_{e \in \delta(v)} x_e \leq 1 \end{align*} says that at most one edge of $M_x$ is incident to $v$. Therefore $M_x$ is a matching, and $x=\mathbb{1}_{M_x}$. Conversely, if $M \subset E$ is a matching, then its incidence vector $\mathbb{1}_M \in \{0,1\}^{E}$ satisfies \begin{align*} \sum_{e \in \delta(v)} (\mathbb{1}_M)_e \leq 1 \end{align*} for every $v \in V$, and $(\mathbb{1}_M)_e \geq 0$ for every $e \in E$. Hence $\mathbb{1}_M \in Q_M(G)$. Thus the integral feasible points of $Q_M(G)$ are exactly the incidence vectors of matchings in $G$. [/step] [step:Conclude the linear program solves maximum weight matching] Since $0 \leq x_e \leq 1$ for every $x \in Q_M(G)$ and every $e \in E$, the polytope $Q_M(G)$ is bounded. Since $Q_M(G)$ is the intersection of finitely many closed half-spaces in $\mathbb{R}^{E}$ and is nonempty because $0 \in Q_M(G)$, it is compact. A compact polytope is the convex hull of its vertices; applying the preceding two steps gives \begin{align*} Q_M(G)=\operatorname{conv}\{\mathbb{1}_M : M \subset E \text{ is a matching in }G\}. \end{align*} Let $w \in \mathbb{R}^{E}$. The linear functional \begin{align*} x \mapsto w \cdot x \end{align*} attains its maximum over $Q_M(G)$ by compactness. If a maximizer is written as a convex combination of vertices, linearity implies that at least one vertex appearing with positive coefficient has objective value equal to the maximum. Hence the maximum is attained at a vertex. Every vertex of $Q_M(G)$ is integral, and the preceding step identifies every integral feasible point with the incidence vector of a matching. Therefore the linear program \begin{align*} \max\{w \cdot x : x \in Q_M(G)\} \end{align*} has an optimal solution of the form $\mathbb{1}_M$, where $M$ is a matching in $G$. For every matching $M \subset E$, the objective value at its incidence vector is \begin{align*} w \cdot \mathbb{1}_M = \sum_{e \in M} w_e. \end{align*} Therefore an optimal integral solution of the linear program is exactly an incidence vector of a maximum weight matching. This proves both the integrality of $Q_M(G)$ and the stated consequence for maximum weight matching. [/step]