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 \
*-----O
|\_ |
d| -_ |g
| f \|
*-----O
e

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.