A bipartite graph (aka bigraph) is a graph whose vertices can be divided into two disjoint sets such that vertices from one set only connect to the vertices from the other set and not each other.
The integraloty theorem tells us that if all capacities in a flow network are integers, then there is a maximum …
bipartite network-flow