In graph theory, a cut of a graph or directed graph G=(V,E) is just a partition of the vertices V = Γ ∪ Γ'. The set of edges between an element of Γ and an element of Γ' is also called the cut.

For instance, in the below graph

  a / \ b
   / c \
  |\_   |
 d|  -_ |g
  |  f \|
there is a cut between the vertices "*" and the vertices "O". The edges of the cut are b,c,e and f. a and d, between two "*"s, and g, between two "O"s, are not included in the cut.

If G is a capacitated network with capacities c:E→[0,∞), the value of the cut Γ is

e ∈ Γ×Γ'c(e)
(the sum of the capacities of all edges going "the right way" across Γ; note that edges from Γ' to Γ are ignored).

The above definition is assymmetrical. Usually, we'll require that the source s∈Γ and the sink t∈Γ'; that helps explain the assymmetry.

These are the two basic questions given a capacitated network:

max cut - What is the maximal possible value of a cut Γ in the network?
This is an NP-complete problem.
min cut - What is the minimal possible value of a cut Γ in the network?
Duality in linear programming shows that this value is the same as the value of the maximal feasible flow in the graph. The proof of the Ford-Fulkerson algorithm gives an easier way to see this than full-blown linear programming.