[proofplan] Fix an arbitrary assignment $\pi \in S_n$. The feasibility inequalities may be applied with $j=\pi(i)$ in each row $i$, giving $u_i+v_{\pi(i)} \le c_{i,\pi(i)}$. Summing these inequalities over all rows produces the assignment cost on the right, while the permutation property of $\pi$ identifies $\sum_i v_{\pi(i)}$ with $\sum_j v_j$. [/proofplan] [step:Apply the dual feasibility inequality along the chosen assignment] Fix $\pi \in S_n$. For each $i \in \{1,\dots,n\}$, the hypothesis applied to the pair $(i,\pi(i))$ gives \begin{align*} u_i + v_{\pi(i)} \leq c_{i,\pi(i)}. \end{align*} Summing these $n$ inequalities over $i \in \{1,\dots,n\}$ yields \begin{align*} \sum_{i=1}^{n} \bigl(u_i + v_{\pi(i)}\bigr) \leq \sum_{i=1}^{n} c_{i,\pi(i)}. \end{align*} [guided] We fix an arbitrary permutation $\pi \in S_n$ because the theorem asserts the inequality for every assignment. Once $\pi$ is fixed, each row index $i \in \{1,\dots,n\}$ is matched to the column index $\pi(i) \in \{1,\dots,n\}$. The hypothesis says that the inequality \begin{align*} u_i + v_j \leq c_{ij} \end{align*} holds for every pair of indices $i,j \in \{1,\dots,n\}$. Therefore it is valid in particular for the pair $j=\pi(i)$, so for every $i \in \{1,\dots,n\}$ we have \begin{align*} u_i + v_{\pi(i)} \leq c_{i,\pi(i)}. \end{align*} Because there are finitely many inequalities, one for each row index $i$, we may add their left-hand sides and right-hand sides term by term. This gives \begin{align*} \sum_{i=1}^{n} \bigl(u_i + v_{\pi(i)}\bigr) \leq \sum_{i=1}^{n} c_{i,\pi(i)}. \end{align*} This is the only place where the entrywise bound $u_i+v_j \le c_{ij}$ is used: we restrict it to the $n$ matrix entries selected by the assignment $\pi$. [/guided] [/step] [step:Use the permutation property to rewrite the summed left hand side] Since $\pi \in S_n$, the map \begin{align*} \pi: \{1,\dots,n\} &\to \{1,\dots,n\} \end{align*} is a bijection. Hence the list $\pi(1),\dots,\pi(n)$ is a reordering of $1,\dots,n$, and therefore \begin{align*} \sum_{i=1}^{n} v_{\pi(i)} = \sum_{j=1}^{n} v_j. \end{align*} Using finite additivity of sums, we also have \begin{align*} \sum_{i=1}^{n} \bigl(u_i + v_{\pi(i)}\bigr) = \sum_{i=1}^{n} u_i + \sum_{i=1}^{n} v_{\pi(i)} = \sum_{i=1}^{n} u_i + \sum_{j=1}^{n} v_j. \end{align*} Substituting this identity into the inequality from the previous step gives \begin{align*} \sum_{i=1}^{n} u_i + \sum_{j=1}^{n} v_j \leq \sum_{i=1}^{n} c_{i,\pi(i)}. \end{align*} Because $\pi \in S_n$ was arbitrary, the inequality holds for every assignment $\pi \in S_n$. [/step]