AFTD Auto-Formalizing Theoretical Domains

four_vertex_cycle_cost_potential

theoremverified

If every closed four-step walk on four vertices has nonnegative cost and loops cost zero, a real vertex potential makes every reduced edge cost nonnegative.

Statement

theorem four_vertex_cycle_cost_potential (c : Fin 4 → Fin 4 → ℝ)
    (hd : ∀ i, c i i = 0)
    (hc : ∀ i j k l, 0 ≤ c i j + c j k + c k l + c l i) :
    ∃ p : Fin 4 → ℝ, ∀ i j, p j ≤ p i + c i j
Source
Sector-bound formalization for IN-166; arXiv:math/0508176, Theorem 5.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • four_vertex_balanced_cost_nonnegOn four vertices, a balanced edge weighting, nonnegative away from the diagonal, assigns nonnegative total cost whenever every closed…

The proof, explained

The proof constructs a vertex potential $p$ on the four-vertex complete directed graph by fixing $p_0 = 0$ and defining each remaining $p_v$ as the shortest-path distance from vertex 0 to $v$, expressed as the explicit minimum over all five simple paths from 0 to $v$. Because every four-step closed walk has nonnegative cost and loops cost zero, all cycles of lengths 2, 3, and 4 have nonnegative cost as well. To verify the triangle inequality $p_j \le p_i + c(i, j)$, appending the edge $(i, j)$ to any simple path to $i$ produces either a simple path to $j$ (bounded by $p_j$) or a cycle plus a subpath to $j$ (whose cost is at least $p_j$ because cycles are nonnegative). Finally, an exhaustive verification over all sixteen vertex pairs confirms that this potential satisfies the required condition for all edges.

  1. Candidate potential values $p_1, p_2, p_3$ are defined as the shortest simple paths from vertex 0, and bounded by each path cost.

    For each vertex $v \in \{1, 2, 3\}$, there are five simple directed paths from vertex 0 to $v$ in the complete graph on 4 vertices: the single edge $0 \to v$, two 2-edge paths, and two 3-edge paths. We define $p_v$ as the nested minimum of the costs of these five paths. By applying the standard properties of the binary minimum (`min_le_left`, `min_le_right`, `le_trans`, and `le_rfl`), we record explicit inequalities ($hp1_0$ through $hp3_4$) stating that $p_v$ is bounded above by the cost of each individual path.

    lines 5–22

    uses min_le_left, le_trans, min_le_right, le_rfl

      let p1 : ℝ := min (c 0 1) (min (c 0 2 + c 2 1) (min (c 0 3 + c 3 1) (min (c 0 2 + c 2 3 + c 3 1) (c 0 3 + c 3 2 + c 2 1))))
      have hp1_0 : p1 ≤ c 0 1 := min_le_left _ _
      have hp1_1 : p1 ≤ c 0 2 + c 2 1 := le_trans (min_le_right _ _) (min_le_left _ _)
      have hp1_2 : p1 ≤ c 0 3 + c 3 1 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _))
      have hp1_3 : p1 ≤ c 0 2 + c 2 3 + c 3 1 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _)))
      have hp1_4 : p1 ≤ c 0 3 + c 3 2 + c 2 1 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_rfl))))
      let p2 : ℝ := min (c 0 2) (min (c 0 1 + c 1 2) (min (c 0 3 + c 3 2) (min (c 0 1 + c 1 3 + c 3 2) (c 0 3 + c 3 1 + c 1 2))))
      have hp2_0 : p2 ≤ c 0 2 := min_le_left _ _
      have hp2_1 : p2 ≤ c 0 1 + c 1 2 := le_trans (min_le_right _ _) (min_le_left _ _)
      have hp2_2 : p2 ≤ c 0 3 + c 3 2 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _))
      have hp2_3 : p2 ≤ c 0 1 + c 1 3 + c 3 2 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _)))
      have hp2_4 : p2 ≤ c 0 3 + c 3 1 + c 1 2 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_rfl))))
      let p3 : ℝ := min (c 0 3) (min (c 0 1 + c 1 3) (min (c 0 2 + c 2 3) (min (c 0 1 + c 1 2 + c 2 3) (c 0 2 + c 2 1 + c 1 3))))
      have hp3_0 : p3 ≤ c 0 3 := min_le_left _ _
      have hp3_1 : p3 ≤ c 0 1 + c 1 3 := le_trans (min_le_right _ _) (min_le_left _ _)
      have hp3_2 : p3 ≤ c 0 2 + c 2 3 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _))
      have hp3_3 : p3 ≤ c 0 1 + c 1 2 + c 2 3 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _)))
      have hp3_4 : p3 ≤ c 0 2 + c 2 1 + c 1 3 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_rfl))))
  2. Every directed cycle of length 2, 3, or 4 has nonnegative total cost.

    The theorem hypothesis states that every 4-step closed walk $i \to j \to k \to l \to i$ has nonnegative total cost. Because self-loops have zero cost ($c(i, i) = 0$), setting repeated vertices specializes this hypothesis to shorter cycles: setting three vertices identical yields the nonnegativity of all six 2-cycles ($hc0$–$hc5$); setting two vertices identical yields the nonnegativity of all eight 3-cycles ($hc6$–$hc13$); and distinct vertices yield all six 4-cycles ($hc14$–$hc19$). Each identity is simplified by removing zero loop costs using `add_zero` and `zero_add`.

    lines 23–62

    uses add_zero, zero_add

      have hc0 : 0 ≤ c 0 1 + c 1 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 1 1 1
      have hc1 : 0 ≤ c 0 2 + c 2 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 2 2 2
      have hc2 : 0 ≤ c 0 3 + c 3 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 3 3 3
      have hc3 : 0 ≤ c 1 2 + c 2 1 := by
        simpa only [hd, add_zero, zero_add] using hc 1 2 2 2
      have hc4 : 0 ≤ c 1 3 + c 3 1 := by
        simpa only [hd, add_zero, zero_add] using hc 1 3 3 3
      have hc5 : 0 ≤ c 2 3 + c 3 2 := by
        simpa only [hd, add_zero, zero_add] using hc 2 3 3 3
      have hc6 : 0 ≤ c 0 1 + c 1 2 + c 2 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 1 2 2
      have hc7 : 0 ≤ c 0 1 + c 1 3 + c 3 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 1 3 3
      have hc8 : 0 ≤ c 0 2 + c 2 1 + c 1 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 2 1 1
      have hc9 : 0 ≤ c 0 2 + c 2 3 + c 3 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 2 3 3
      have hc10 : 0 ≤ c 0 3 + c 3 1 + c 1 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 3 1 1
      have hc11 : 0 ≤ c 0 3 + c 3 2 + c 2 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 3 2 2
      have hc12 : 0 ≤ c 1 2 + c 2 3 + c 3 1 := by
        simpa only [hd, add_zero, zero_add] using hc 1 2 3 3
      have hc13 : 0 ≤ c 1 3 + c 3 2 + c 2 1 := by
        simpa only [hd, add_zero, zero_add] using hc 1 3 2 2
      have hc14 : 0 ≤ c 0 1 + c 1 2 + c 2 3 + c 3 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 1 2 3
      have hc15 : 0 ≤ c 0 1 + c 1 3 + c 3 2 + c 2 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 1 3 2
      have hc16 : 0 ≤ c 0 2 + c 2 1 + c 1 3 + c 3 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 2 1 3
      have hc17 : 0 ≤ c 0 2 + c 2 3 + c 3 1 + c 1 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 2 3 1
      have hc18 : 0 ≤ c 0 3 + c 3 1 + c 1 2 + c 2 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 3 1 2
      have hc19 : 0 ≤ c 0 3 + c 3 2 + c 2 1 + c 1 0 := by
        simpa only [hd, add_zero, zero_add] using hc 0 3 2 1
  3. The reduced cost inequality $p_j \le p_0 + c(0, j)$ holds for edges outgoing from the source vertex 0.

    Setting the source potential $p_0 = 0$, the requirement $p_j \le 0 + c(0, j)$ simplifies to $p_j \le c(0, j)$ via `zero_add`. This inequality holds directly because $c(0, j)$, the cost of the direct edge $0 \to j$, is the first term in the minimum defining $p_j$.

    lines 63–68

    uses zero_add

      have h01 : p1 ≤ 0 + c 0 1 := by
        simpa only [zero_add] using hp1_0
      have h02 : p2 ≤ 0 + c 0 2 := by
        simpa only [zero_add] using hp2_0
      have h03 : p3 ≤ 0 + c 0 3 := by
        simpa only [zero_add] using hp3_0
  4. The reduced cost inequality $p_j \le p_i + c(i, j)$ holds for all remaining directed edges between distinct vertices.

    For each of the remaining 9 directed edges $i \to j$ (with $i \ne 0$ and $i \ne j$, setting $p_0 = 0$): distributing addition by $c(i, j)$ across the nested minimum defining $p_i$ via `min_add_add_right` and splitting with `le_min_iff` reduces the goal $p_j \le p_i + c(i, j)$ to five separate subgoals, one for each simple path $P$ from 0 to $i$. If $j = 0$, appending $i \to 0$ to $P$ forms a cycle whose cost is nonnegative by Step 2. If $j \ne 0$ and $P$ does not visit $j$, $P$ followed by $i \to j$ is a simple path from 0 to $j$, so its cost is bounded below by $p_j$ by definition. If $P$ already visits $j$, the walk decomposes into a simple path from 0 to $j$ plus a cycle containing $(i, j)$; since cycles have nonnegative cost, the total cost is at least the path cost to $j$, which is at least $p_j$. In each branch, linear arithmetic (`linarith`) completes the check using the precomputed cycle nonnegativities and path bounds.

    lines 69–149

    uses min_add_add_right, le_min_iff

      have h10 : 0 ≤ p1 + c 1 0 := by
        dsimp only [p1]
        simp only [← min_add_add_right, le_min_iff]
        refine ⟨?_, ?_, ?_, ?_, ?_⟩
        · linarith only [hc0]
        · linarith only [hc8]
        · linarith only [hc10]
        · linarith only [hc17]
        · linarith only [hc19]
      have h12 : p2 ≤ p1 + c 1 2 := by
        dsimp only [p1]
        simp only [← min_add_add_right, le_min_iff]
        refine ⟨?_, ?_, ?_, ?_, ?_⟩
        · linarith only [hp2_1]
        · linarith only [hp2_0, hc3]
        · linarith only [hp2_4]
        · linarith only [hp2_0, hc12]
        · linarith only [hp2_2, hc3]
      have h13 : p3 ≤ p1 + c 1 3 := by
        dsimp only [p1]
        simp only [← min_add_add_right, le_min_iff]
        refine ⟨?_, ?_, ?_, ?_, ?_⟩
        · linarith only [hp3_1]
        · linarith only [hp3_4]
        · linarith only [hp3_0, hc4]
        · linarith only [hp3_2, hc4]
        · linarith only [hp3_0, hc13]
      have h20 : 0 ≤ p2 + c 2 0 := by
        dsimp only [p2]
        simp only [← min_add_add_right, le_min_iff]
        refine ⟨?_, ?_, ?_, ?_, ?_⟩
        · linarith only [hc1]
        · linarith only [hc6]
        · linarith only [hc11]
        · linarith only [hc15]
        · linarith only [hc18]
      have h21 : p1 ≤ p2 + c 2 1 := by
        dsimp only [p2]
        simp only [← min_add_add_right, le_min_iff]
        refine ⟨?_, ?_, ?_, ?_, ?_⟩
        · linarith only [hp1_1]
        · linarith only [hp1_0, hc3]
        · linarith only [hp1_4]
        · linarith only [hp1_0, hc13]
        · linarith only [hp1_2, hc3]
      have h23 : p3 ≤ p2 + c 2 3 := by
        dsimp only [p2]
        simp only [← min_add_add_right, le_min_iff]
        refine ⟨?_, ?_, ?_, ?_, ?_⟩
        · linarith only [hp3_2]
        · linarith only [hp3_3]
        · linarith only [hp3_0, hc5]
        · linarith only [hp3_1, hc5]
        · linarith only [hp3_0, hc12]
      have h30 : 0 ≤ p3 + c 3 0 := by
        dsimp only [p3]
        simp only [← min_add_add_right, le_min_iff]
        refine ⟨?_, ?_, ?_, ?_, ?_⟩
        · linarith only [hc2]
        · linarith only [hc7]
        · linarith only [hc9]
        · linarith only [hc14]
        · linarith only [hc16]
      have h31 : p1 ≤ p3 + c 3 1 := by
        dsimp only [p3]
        simp only [← min_add_add_right, le_min_iff]
        refine ⟨?_, ?_, ?_, ?_, ?_⟩
        · linarith only [hp1_2]
        · linarith only [hp1_0, hc4]
        · linarith only [hp1_3]
        · linarith only [hp1_0, hc12]
        · linarith only [hp1_1, hc4]
      have h32 : p2 ≤ p3 + c 3 2 := by
        dsimp only [p3]
        simp only [← min_add_add_right, le_min_iff]
        refine ⟨?_, ?_, ?_, ?_, ?_⟩
        · linarith only [hp2_2]
        · linarith only [hp2_3]
        · linarith only [hp2_0, hc5]
        · linarith only [hp2_1, hc5]
        · linarith only [hp2_0, hc13]
  5. The potential vector $p = (0, p_1, p_2, p_3)$ satisfies $p_j \le p_i + c(i, j)$ for all $i, j \in \{0, 1, 2, 3\}$.

    We provide $p = ![0, p_1, p_2, p_3]$ as the witness potential. An exhaustive case split (`fin_cases`) over all 16 pairs $(i, j) \in \operatorname{Fin} 4 \times \operatorname{Fin} 4$ reduces each case: the four diagonal cases $i = j$ reduce to $p_i \le p_i + 0$ since loops cost zero, solved by simplification with `Matrix.cons_val_zero`, `Matrix.cons_val_succ`, `add_zero`, and reflexivity `le_refl`; while the twelve off-diagonal cases match the inequalities established in steps 3 and 4.

    lines 150–168

    uses Matrix.cons_val_zero, Matrix.cons_val_succ, add_zero, le_refl

      refine ⟨![0, p1, p2, p3], ?_⟩
      intro i j
      fin_cases i <;> fin_cases j
      · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl]
      · exact h01
      · exact h02
      · exact h03
      · exact h10
      · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl]
      · exact h12
      · exact h13
      · exact h20
      · exact h21
      · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl]
      · exact h23
      · exact h30
      · exact h31
      · exact h32
      · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl]
min_le_left
The minimum of two elements is less than or equal to the first: $\min(a, b) \le a$.
min_le_right
The minimum of two elements is less than or equal to the second: $\min(a, b) \le b$.
le_trans
Order is transitive: if $a \le b$ and $b \le c$, then $a \le c$.
le_rfl
Order is reflexive: $a \le a$.
le_refl
Order is reflexive: $a \le a$.
add_zero
Adding zero on the right leaves an element unchanged: $a + 0 = a$.
zero_add
Adding zero on the left leaves an element unchanged: $0 + a = a$.
min_add_add_right
Addition distributes over minimum on the right: $\min(a, b) + c = \min(a + c, b + c)$.
le_min_iff
An element is bounded above by a minimum if and only if it is bounded by both operands: $c \le \min(a, b) \iff c \le a \land c \le b$.
Matrix.cons_val_zero
The 0-th entry of a vector constructed by prepending an element $x$ is $x$.
Matrix.cons_val_succ
The $(i + 1)$-th entry of a vector constructed by prepending an element is the $i$-th entry of the original vector.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem four_vertex_cycle_cost_potential (c : Fin 4 → Fin 4 → ℝ)    (hd : ∀ i, c i i = 0)    (hc : ∀ i j k l, 0 ≤ c i j + c j k + c k l + c l i) :    ∃ p : Fin 4 → ℝ, ∀ i j, p j ≤ p i + c i j := by  let p1 : ℝ := min (c 0 1) (min (c 0 2 + c 2 1) (min (c 0 3 + c 3 1) (min (c 0 2 + c 2 3 + c 3 1) (c 0 3 + c 3 2 + c 2 1))))  have hp1_0 : p1 ≤ c 0 1 := min_le_left _ _  have hp1_1 : p1 ≤ c 0 2 + c 2 1 := le_trans (min_le_right _ _) (min_le_left _ _)  have hp1_2 : p1 ≤ c 0 3 + c 3 1 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _))  have hp1_3 : p1 ≤ c 0 2 + c 2 3 + c 3 1 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _)))  have hp1_4 : p1 ≤ c 0 3 + c 3 2 + c 2 1 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_rfl))))  let p2 : ℝ := min (c 0 2) (min (c 0 1 + c 1 2) (min (c 0 3 + c 3 2) (min (c 0 1 + c 1 3 + c 3 2) (c 0 3 + c 3 1 + c 1 2))))  have hp2_0 : p2 ≤ c 0 2 := min_le_left _ _  have hp2_1 : p2 ≤ c 0 1 + c 1 2 := le_trans (min_le_right _ _) (min_le_left _ _)  have hp2_2 : p2 ≤ c 0 3 + c 3 2 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _))  have hp2_3 : p2 ≤ c 0 1 + c 1 3 + c 3 2 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _)))  have hp2_4 : p2 ≤ c 0 3 + c 3 1 + c 1 2 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_rfl))))  let p3 : ℝ := min (c 0 3) (min (c 0 1 + c 1 3) (min (c 0 2 + c 2 3) (min (c 0 1 + c 1 2 + c 2 3) (c 0 2 + c 2 1 + c 1 3))))  have hp3_0 : p3 ≤ c 0 3 := min_le_left _ _  have hp3_1 : p3 ≤ c 0 1 + c 1 3 := le_trans (min_le_right _ _) (min_le_left _ _)  have hp3_2 : p3 ≤ c 0 2 + c 2 3 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _))  have hp3_3 : p3 ≤ c 0 1 + c 1 2 + c 2 3 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _)))  have hp3_4 : p3 ≤ c 0 2 + c 2 1 + c 1 3 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_rfl))))  have hc0 : 0 ≤ c 0 1 + c 1 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 1 1 1  have hc1 : 0 ≤ c 0 2 + c 2 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 2 2 2  have hc2 : 0 ≤ c 0 3 + c 3 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 3 3 3  have hc3 : 0 ≤ c 1 2 + c 2 1 := by    simpa only [hd, add_zero, zero_add] using hc 1 2 2 2  have hc4 : 0 ≤ c 1 3 + c 3 1 := by    simpa only [hd, add_zero, zero_add] using hc 1 3 3 3  have hc5 : 0 ≤ c 2 3 + c 3 2 := by    simpa only [hd, add_zero, zero_add] using hc 2 3 3 3  have hc6 : 0 ≤ c 0 1 + c 1 2 + c 2 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 1 2 2  have hc7 : 0 ≤ c 0 1 + c 1 3 + c 3 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 1 3 3  have hc8 : 0 ≤ c 0 2 + c 2 1 + c 1 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 2 1 1  have hc9 : 0 ≤ c 0 2 + c 2 3 + c 3 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 2 3 3  have hc10 : 0 ≤ c 0 3 + c 3 1 + c 1 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 3 1 1  have hc11 : 0 ≤ c 0 3 + c 3 2 + c 2 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 3 2 2  have hc12 : 0 ≤ c 1 2 + c 2 3 + c 3 1 := by    simpa only [hd, add_zero, zero_add] using hc 1 2 3 3  have hc13 : 0 ≤ c 1 3 + c 3 2 + c 2 1 := by    simpa only [hd, add_zero, zero_add] using hc 1 3 2 2  have hc14 : 0 ≤ c 0 1 + c 1 2 + c 2 3 + c 3 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 1 2 3  have hc15 : 0 ≤ c 0 1 + c 1 3 + c 3 2 + c 2 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 1 3 2  have hc16 : 0 ≤ c 0 2 + c 2 1 + c 1 3 + c 3 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 2 1 3  have hc17 : 0 ≤ c 0 2 + c 2 3 + c 3 1 + c 1 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 2 3 1  have hc18 : 0 ≤ c 0 3 + c 3 1 + c 1 2 + c 2 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 3 1 2  have hc19 : 0 ≤ c 0 3 + c 3 2 + c 2 1 + c 1 0 := by    simpa only [hd, add_zero, zero_add] using hc 0 3 2 1  have h01 : p1 ≤ 0 + c 0 1 := by    simpa only [zero_add] using hp1_0  have h02 : p2 ≤ 0 + c 0 2 := by    simpa only [zero_add] using hp2_0  have h03 : p3 ≤ 0 + c 0 3 := by    simpa only [zero_add] using hp3_0  have h10 : 0 ≤ p1 + c 1 0 := by    dsimp only [p1]    simp only [← min_add_add_right, le_min_iff]    refine ⟨?_, ?_, ?_, ?_, ?_⟩    · linarith only [hc0]    · linarith only [hc8]    · linarith only [hc10]    · linarith only [hc17]    · linarith only [hc19]  have h12 : p2 ≤ p1 + c 1 2 := by    dsimp only [p1]    simp only [← min_add_add_right, le_min_iff]    refine ⟨?_, ?_, ?_, ?_, ?_⟩    · linarith only [hp2_1]    · linarith only [hp2_0, hc3]    · linarith only [hp2_4]    · linarith only [hp2_0, hc12]    · linarith only [hp2_2, hc3]  have h13 : p3 ≤ p1 + c 1 3 := by    dsimp only [p1]    simp only [← min_add_add_right, le_min_iff]    refine ⟨?_, ?_, ?_, ?_, ?_⟩    · linarith only [hp3_1]    · linarith only [hp3_4]    · linarith only [hp3_0, hc4]    · linarith only [hp3_2, hc4]    · linarith only [hp3_0, hc13]  have h20 : 0 ≤ p2 + c 2 0 := by    dsimp only [p2]    simp only [← min_add_add_right, le_min_iff]    refine ⟨?_, ?_, ?_, ?_, ?_⟩    · linarith only [hc1]    · linarith only [hc6]    · linarith only [hc11]    · linarith only [hc15]    · linarith only [hc18]  have h21 : p1 ≤ p2 + c 2 1 := by    dsimp only [p2]    simp only [← min_add_add_right, le_min_iff]    refine ⟨?_, ?_, ?_, ?_, ?_⟩    · linarith only [hp1_1]    · linarith only [hp1_0, hc3]    · linarith only [hp1_4]    · linarith only [hp1_0, hc13]    · linarith only [hp1_2, hc3]  have h23 : p3 ≤ p2 + c 2 3 := by    dsimp only [p2]    simp only [← min_add_add_right, le_min_iff]    refine ⟨?_, ?_, ?_, ?_, ?_⟩    · linarith only [hp3_2]    · linarith only [hp3_3]    · linarith only [hp3_0, hc5]    · linarith only [hp3_1, hc5]    · linarith only [hp3_0, hc12]  have h30 : 0 ≤ p3 + c 3 0 := by    dsimp only [p3]    simp only [← min_add_add_right, le_min_iff]    refine ⟨?_, ?_, ?_, ?_, ?_⟩    · linarith only [hc2]    · linarith only [hc7]    · linarith only [hc9]    · linarith only [hc14]    · linarith only [hc16]  have h31 : p1 ≤ p3 + c 3 1 := by    dsimp only [p3]    simp only [← min_add_add_right, le_min_iff]    refine ⟨?_, ?_, ?_, ?_, ?_⟩    · linarith only [hp1_2]    · linarith only [hp1_0, hc4]    · linarith only [hp1_3]    · linarith only [hp1_0, hc12]    · linarith only [hp1_1, hc4]  have h32 : p2 ≤ p3 + c 3 2 := by    dsimp only [p3]    simp only [← min_add_add_right, le_min_iff]    refine ⟨?_, ?_, ?_, ?_, ?_⟩    · linarith only [hp2_2]    · linarith only [hp2_3]    · linarith only [hp2_0, hc5]    · linarith only [hp2_1, hc5]    · linarith only [hp2_0, hc13]  refine ⟨![0, p1, p2, p3], ?_⟩  intro i j  fin_cases i <;> fin_cases j  · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl]  · exact h01  · exact h02  · exact h03  · exact h10  · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl]  · exact h12  · exact h13  · exact h20  · exact h21  · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl]  · exact h23  · exact h30  · exact h31  · exact h32  · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl]
See it in the graphDiscuss this resultChallenge it