# Maximum weight matching on bipartite graph with unequal set cardinalities

Consider a maximum weight matching problem on a bipartite graph $G = (E,V)$ with $V = U \cup W$ such that the sets of vertices $U$ and $W$ have different cardinalities, i.e., $|U| \neq |W|$. Given this discrepancy in the number of vertices in $U$ and $W$, will the LP relaxation of this problem still have integral solutions?

Yes! The result is due to the vertex-edge incidence matrix of any bipartite graph being totally unimodular. The proof of that result doesn't depend on the sizes of $U,W$ (as long as none are nonempty, then the graph is not bipartite at all).