[proofplan] A cycle in the support graph gives an alternating signed perturbation of the matrix $P$: add $\varepsilon$ on every other cycle edge and subtract $\varepsilon$ on the remaining cycle edges. The signs cancel at every row and column vertex, so the row and column marginals are preserved, while choosing $\varepsilon$ smaller than the positive cycle entries preserves non-negativity. For the converse, delete one redundant marginal equation and prove that the columns indexed by the tree edges are linearly independent by a leaf-removal argument. Since there are exactly $m+n-1$ positive variables and the reduced transportation constraint matrix has rank $m+n-1$, those columns form a basis and all basic variables are positive. [/proofplan] [step:Perturb along a support cycle while preserving every marginal] Assume first that $G(P)$ contains a cycle. Since $G(P)$ is bipartite, this cycle has even length. Choose distinct row indices $i_1,\dots,i_k \in \{1,\dots,m\}$ and distinct column indices $j_1,\dots,j_k \in \{1,\dots,n\}$, with $k \geq 2$, such that the cycle edges are \begin{align*} R_{i_1}C_{j_1},\ R_{i_2}C_{j_1},\ R_{i_2}C_{j_2},\ R_{i_3}C_{j_2},\dots,\ R_{i_k}C_{j_k},\ R_{i_1}C_{j_k}. \end{align*} Here and below the index $i_{k+1}$ denotes $i_1$. Define a matrix \begin{align*} H=(h_{ij}) \in \mathbb{R}^{m \times n} \end{align*} by setting $h_{i_\ell j_\ell}=1$ and $h_{i_{\ell+1}j_\ell}=-1$ for every $\ell \in \{1,\dots,k\}$, and setting all other entries equal to $0$. Each row vertex on the cycle is incident to exactly one $+1$ entry and exactly one $-1$ entry of $H$, and each column vertex on the cycle is also incident to exactly one $+1$ entry and exactly one $-1$ entry of $H$. Therefore \begin{align*} \sum_{j=1}^n h_{ij}=0 \quad \text{for every } i \in \{1,\dots,m\} \end{align*} and \begin{align*} \sum_{i=1}^m h_{ij}=0 \quad \text{for every } j \in \{1,\dots,n\}. \end{align*} Since every edge of the chosen cycle belongs to the support of $P$, every corresponding entry of $P$ is positive. Define \begin{align*} \delta := \min\{p_{i_\ell j_\ell},p_{i_{\ell+1}j_\ell} : \ell \in \{1,\dots,k\}\}. \end{align*} Then $\delta>0$. Choose $\varepsilon \in \mathbb{R}$ with $0<\varepsilon<\delta$ and define \begin{align*} P_+ := P+\varepsilon H \quad \text{and} \quad P_- := P-\varepsilon H. \end{align*} At entries outside the cycle, $P_+$ and $P_-$ agree with $P$. At entries on the cycle, the entries of $P_+$ and $P_-$ are obtained from positive entries of $P$ by adding or subtracting $\varepsilon<\delta$, so all entries remain non-negative. The row and column sum identities for $H$ give, for every row index $i$, \begin{align*} \sum_{j=1}^n (p_{ij}\pm \varepsilon h_{ij}) = \sum_{j=1}^n p_{ij} \pm \varepsilon \sum_{j=1}^n h_{ij}=a_i, \end{align*} and, for every column index $j$, \begin{align*} \sum_{i=1}^m (p_{ij}\pm \varepsilon h_{ij}) = \sum_{i=1}^m p_{ij} \pm \varepsilon \sum_{i=1}^m h_{ij}=b_j. \end{align*} Thus $P_+,P_- \in \Pi(a,b)$. [guided] The purpose of the perturbation is to move inside the transportation polytope without changing any marginal. A cycle in a bipartite graph alternates between row vertices and column vertices, so we may write it as \begin{align*} R_{i_1}C_{j_1},\ R_{i_2}C_{j_1},\ R_{i_2}C_{j_2},\ R_{i_3}C_{j_2},\dots,\ R_{i_k}C_{j_k},\ R_{i_1}C_{j_k}. \end{align*} The indices $i_1,\dots,i_k$ are distinct row indices, the indices $j_1,\dots,j_k$ are distinct column indices, and $k \geq 2$. We use the convention $i_{k+1}=i_1$ to close the cycle. Define the perturbation matrix $H=(h_{ij}) \in \mathbb{R}^{m \times n}$ by putting $+1$ on the cycle edge $R_{i_\ell}C_{j_\ell}$ and $-1$ on the next cycle edge $R_{i_{\ell+1}}C_{j_\ell}$, for each $\ell \in \{1,\dots,k\}$. All entries away from the cycle are $0$. Why these signs? At every column vertex $C_{j_\ell}$, the perturbation has one $+1$ and one $-1$, so the column sum of the perturbation is zero. At every row vertex $R_{i_\ell}$, the perturbation also has one $+1$ and one $-1$: the $+1$ occurs at $(i_\ell,j_\ell)$ and the $-1$ occurs at $(i_\ell,j_{\ell-1})$, with the cyclic interpretation of the index. Hence \begin{align*} \sum_{j=1}^n h_{ij}=0 \quad \text{for every } i \in \{1,\dots,m\} \end{align*} and \begin{align*} \sum_{i=1}^m h_{ij}=0 \quad \text{for every } j \in \{1,\dots,n\}. \end{align*} Now we choose the size of the perturbation. Since every edge of the cycle lies in the support graph, every entry of $P$ on the cycle is strictly positive. Define \begin{align*} \delta := \min\{p_{i_\ell j_\ell},p_{i_{\ell+1}j_\ell} : \ell \in \{1,\dots,k\}\}. \end{align*} This is the minimum of finitely many positive numbers, so $\delta>0$. Choose $\varepsilon \in \mathbb{R}$ with $0<\varepsilon<\delta$, and set \begin{align*} P_+ := P+\varepsilon H \quad \text{and} \quad P_- := P-\varepsilon H. \end{align*} At a cycle entry, the new value is either $p_{ij}+\varepsilon$ or $p_{ij}-\varepsilon$. The subtraction case remains non-negative because $p_{ij}\geq \delta>\varepsilon$. Away from the cycle, nothing changes. Therefore $P_+$ and $P_-$ are non-negative matrices. It remains to check that the row and column marginals are unchanged. For every row index $i$, \begin{align*} \sum_{j=1}^n (p_{ij}\pm \varepsilon h_{ij}) = \sum_{j=1}^n p_{ij} \pm \varepsilon \sum_{j=1}^n h_{ij}=a_i. \end{align*} For every column index $j$, \begin{align*} \sum_{i=1}^m (p_{ij}\pm \varepsilon h_{ij}) = \sum_{i=1}^m p_{ij} \pm \varepsilon \sum_{i=1}^m h_{ij}=b_j. \end{align*} Thus both perturbed matrices still lie in $\Pi(a,b)$. [/guided] [/step] [step:Express $P$ as a nontrivial midpoint] The matrix $H$ is not the zero matrix because the cycle is nonempty. Since $\varepsilon>0$, we have $P_+ \neq P_-$. By construction, \begin{align*} P=\frac{1}{2}P_+ + \frac{1}{2}P_-. \end{align*} Thus $P$ is a convex combination of two distinct points of $\Pi(a,b)$, so $P$ is not an extreme point of $\Pi(a,b)$. [/step] [step:Reduce the transportation equations to a full-rank system] Now assume that $a_i>0$ for every $i$, $b_j>0$ for every $j$, and that $G(P)$ is a spanning tree. Let $S \subset \{1,\dots,m\}\times \{1,\dots,n\}$ denote the support of $P$: \begin{align*} S := \{(i,j):p_{ij}>0\}. \end{align*} Because $G(P)$ is a tree on $m+n$ vertices, it has exactly $m+n-1$ edges, so $|S|=m+n-1$. Delete the last column marginal equation. Define the reduced transportation constraint matrix \begin{align*} A:\mathbb{R}^{mn}\to \mathbb{R}^{m+n-1} \end{align*} as follows: the coordinate rows of $\mathbb{R}^{m+n-1}$ are indexed by $R_1,\dots,R_m,C_1,\dots,C_{n-1}$, and the column of $A$ indexed by the variable $p_{ij}$ is \begin{align*} A_{ij}=e_{R_i}+ \mathbb{1}_{\{j<n\}}e_{C_j}. \end{align*} Here $e_{R_i}$ and $e_{C_j}$ denote the corresponding standard coordinate vectors in $\mathbb{R}^{m+n-1}$. The rows of $A$ are linearly independent. Indeed, suppose [real numbers](/page/Real%20Numbers) $\alpha_1,\dots,\alpha_m$ and $\beta_1,\dots,\beta_{n-1}$ define a linear relation among the rows. Looking at the column indexed by $(i,n)$ gives $\alpha_i=0$ for every $i$. Looking next at the column indexed by $(i,j)$ with $j<n$ gives $\alpha_i+\beta_j=0$, hence $\beta_j=0$ for every $j<n$. Therefore the only row relation is the zero relation, and \begin{align*} \operatorname{rank} A=m+n-1. \end{align*} [/step] [step:Prove that the tree support columns are linearly independent] We prove that the family of reduced columns $\{A_{ij}:(i,j)\in S\}$ is linearly independent. Suppose that real numbers $\gamma_{ij}$, indexed by $(i,j)\in S$, satisfy \begin{align*} \sum_{(i,j)\in S}\gamma_{ij}A_{ij}=0. \end{align*} We show that every $\gamma_{ij}$ is zero. Root the tree $G(P)$ at the column vertex $C_n$. Since $G(P)$ is a finite tree, if it has more than one vertex then it has a leaf different from the root. Choose such a leaf vertex. If the leaf is a row vertex $R_i$, then the $R_i$-coordinate of the displayed relation contains exactly one coefficient, namely the coefficient $\gamma_{ij}$ on the unique support edge incident to $R_i$. Hence $\gamma_{ij}=0$. If the leaf is a column vertex $C_j$ with $j<n$, then the $C_j$-coordinate of the relation contains exactly one coefficient, namely the coefficient $\gamma_{ij}$ on the unique support edge incident to $C_j$. Hence $\gamma_{ij}=0$. Remove this leaf and its incident edge from the tree. Since the coefficient on the removed edge is zero, the remaining coefficients still satisfy the same kind of linear relation on the reduced tree. Repeating this finite leaf-removal procedure eventually removes every edge, and each removed edge has coefficient zero. Therefore $\gamma_{ij}=0$ for every $(i,j)\in S$, proving [linear independence](/page/Linear%20Independence). [guided] We need to show that no nonzero linear dependence can occur among the columns of $A$ corresponding to positive entries of $P$. Suppose, toward a direct verification, that \begin{align*} \sum_{(i,j)\in S}\gamma_{ij}A_{ij}=0 \end{align*} for real coefficients $\gamma_{ij}$. The goal is to force each coefficient $\gamma_{ij}$ to vanish. The graph-theoretic input is that $G(P)$ is a tree. Root this tree at $C_n$, the one column vertex whose marginal equation was deleted from the reduced matrix. A finite rooted tree always has a leaf different from the root unless there are no edges left. Pick such a leaf. If the leaf is a row vertex $R_i$, then only one support edge touches $R_i$; write it as $R_iC_j$. In the reduced matrix, every column $A_{ij}$ with row index $i$ contributes $1$ to the $R_i$-coordinate, and no column whose edge is not incident to $R_i$ contributes to that coordinate. Since $R_i$ is a leaf, the $R_i$-coordinate of the linear relation is exactly \begin{align*} \gamma_{ij}=0. \end{align*} Thus the coefficient on the unique edge incident to that leaf is zero. If the leaf is a column vertex $C_j$, then $j<n$ because the root is $C_n$ and the chosen leaf is not the root. Let $R_iC_j$ be the unique support edge incident to $C_j$. In the reduced matrix, the $C_j$-coordinate records exactly the variables in column $j$. Since $C_j$ is a leaf, the $C_j$-coordinate of the relation is exactly \begin{align*} \gamma_{ij}=0. \end{align*} Again the coefficient on the unique incident edge is zero. After finding a zero coefficient on a leaf edge, remove that leaf and its incident edge from the tree. Removing a zero term from the displayed linear relation does not change the relation. The remaining graph is still a tree, now with fewer edges, and the same argument applies again. Because the original tree is finite, this leaf-removal process terminates after finitely many removals. Every edge is removed at some stage, and at the moment it is removed its coefficient is shown to be zero. Hence all coefficients $\gamma_{ij}$ vanish, so the family $\{A_{ij}:(i,j)\in S\}$ is linearly independent. [/guided] [/step] [step:Conclude that the feasible point is a nondegenerate basic feasible solution] The reduced system has rank $m+n-1$, and the support set $S$ has $m+n-1$ indices. The preceding step proves that the columns $\{A_{ij}:(i,j)\in S\}$ are linearly independent, so they form a basis of the column space of the reduced transportation constraint matrix. The variables indexed by $S$ are exactly the positive variables of $P$, and every one of them is strictly positive by definition of $S$. Therefore $P$ is a basic feasible solution with exactly $m+n-1$ positive basic variables, so $P$ is nondegenerate. Finally, because every $a_i$ and every $b_j$ is positive, every row vertex and every column vertex is incident to at least one support edge. Hence an acyclic support graph with $m+n-1$ edges is necessarily connected and spanning, so it is a spanning tree. This proves the stated equivalence and completes the proof. [/step]