讓我們首先回顧一下最小費用循環的線性規劃主模型（Primal Problem）、以及其對偶模型（Dual Problem）。令 $f(u, v)$ 為線性規劃模型的變數、$y(u, v)$ 以及 $d(v)$ 為其對偶模型的變數名。我們定義以下三種條件：
- P 條件：$f$ 滿足線性規劃模型的條件，即 $f$ 是一個合法的網路流。
- D 條件：$y, d$ 滿足對偶模型的條件，即 $y(u, v)-d(u)+d(v) \le cost(u, v)$。
- CS 條件：$f, y, d$ 滿足互補差餘條件，即
$$ \begin{cases} f(u, v) > 0 & \implies y(u, v) = d(u) + cost(u, v) - d(v)\ f(u, v) < cap(u, v) & \implies y(u, v) = 0 \end{cases} $$
由線性規劃的各種性質我們可以知道，只要 $f, y, d$ 這三組變數同時滿足 P條件、D條件以及 CS條件的話，保證 $f, y, d$ 分別是主模型和對偶模型的最佳解。
證明
我們只需要證明「存在滿足條件的 $d^*$ 函數」等價於「存在滿足 D 條件和 CS 條件的 $y, d$」即可。