Let $m,n \in \mathbb{N}$, let $a=(a_1,\dots,a_m) \in [0,\infty)^m$ and $b=(b_1,\dots,b_n) \in [0,\infty)^n$ satisfy

\begin{align*} \sum_{i=1}^m a_i = \sum_{j=1}^n b_j. \end{align*}

Let

\begin{align*} \Pi(a,b) := \left\{P=(p_{ij}) \in [0,\infty)^{m \times n} : \sum_{j=1}^n p_{ij}=a_i \text{ for every } i,\ \sum_{i=1}^m p_{ij}=b_j \text{ for every } j\right\}. \end{align*}

For $P \in \Pi(a,b)$, define its support graph $G(P)$ to be the bipartite graph with row vertices $R_1,\dots,R_m$, column vertices $C_1,\dots,C_n$, and edge $R_iC_j$ exactly when $p_{ij}>0$.

If $G(P)$ contains a cycle, then $P$ is not an extreme point of $\Pi(a,b)$. Conversely, suppose $a_i>0$ for every $i$ and $b_j>0$ for every $j$. If $G(P)$ is a spanning tree on the $m+n$ row and column vertices, equivalently if $G(P)$ is acyclic and $P$ has exactly $m+n-1$ positive entries, then $P$ is a nondegenerate basic feasible solution of the standard transportation linear system.