What is a min-max theorem in graph theory?
A min-max theorem is simply a theorem that says that the minimum value possible for one quantity is the maximum value possible for some other.
For example,


Max-flow min-cut says that the value of the biggest flow between two vertices in a weighted graph is equal to the value of the minimum cut that separates them.  Closely related, Menger's Theorem says that the maximum number of edge-disjoint paths between two vertex sets is equal to the size of the minimum cut that separates them.
Edmonds' Theorem says that the maximum number of edge-disjoint spanning arborescences is equal to the minimum value of something called $\varrho(X)$ over certain non-empty vertex sets.
The cops and robbers characterization of treewidth says that the minimum width over all tree decompositions is equal to the maximum number of cops that a robber can escape (er, plus or minus one, probably).