Past exam of the mathematics course of the University of Cambridge / 2025 / ib / Paper 4 / 18H / b / Solution

One of the $m+n$ balance equations is redundant, and the remaining $m+n-1$ have full rank. A nondegenerate basic feasible solution therefore has exactly $m+n-1$ positive variables. Equivalently, its positive cells form a spanning tree of the complete bipartite row--column graph.