Say we have an $n\times n$ matrix and for every entry $a_{ij}$, it equals $1$ if flight $j$ starts after flight $i$ ends. Otherwise it is $0$. Suppose the largest matching contains $M$ marriages (i.e. $1$'s in $n\times n$ matrix is covered by $M$ lines.)
I was told from the textbook that an airline can make $n$ flights with $n-M$ airplanes except I'm having trouble seeing that. Additionally how do you prove that we cannot have less than $n-M$?
Assume we have fixed some minimum cover with $M$ rows or columns. If the $i$-th row $A_{i \cdot}$ is chosen to be in the minimum cover, then there is some $j$ such that $a_{ij}=1$ but the $j$-th column is not chosen to be in the minimum cover. We take some such $j$, and assign it to $i$ or more precisely to $A_{i \cdot}$, say $\phi(i):=j$. We also do such assignment for each column member of the minimum cover. In arranging the airlines, we can use one airline for both $i$ and $\phi(i)$. By our definition/property of $\phi(i)$, we can use just $n-M$ airlines.