Corollary 3.2, p. 6 — an odd cycle is not cost-minimizing
ProvedLNTopology.Local.corollary_3_2Let be a channel cost function satisfying (MO), (SY), (CI) and (SA), and let be a Lightning Network on a finite node set supporting the flow . Suppose contains a cycle of odd length : distinct nodes with a channel between and for and between and , the flow in each channel going in either direction,
Then is not cost-minimizing for .
Together with König's characterization of bipartite graphs, this gives Corollary 3.3: the channel graph of a cost-minimizing network has no odd cycle.
Formalization Note The cycle is a map (Fin k), injective, with successor given by finRotate k (, and ). "A channel connects" is read as a nonzero net flow, in either direction. (SA) is used in the corrected form for all (the printed range is unsatisfiable). Cost-minimizing compares with networks on the same node set.
import Mathlib import Definitions.Def_LNTopology_Local_Model
namespace LNTopology.Local
/-- Corollary 3.2 (SSRN 4439190, p. 6; proof p. 10): a Lightning Network containing a cycle of
odd length `k` — distinct nodes `u 0, …, u (k-1)` with a channel (nonzero net flow, in either
direction) between `u j` and its cyclic successor `u (finRotate k j)` — is not cost-minimizing. -/
theorem corollary_3_2 {V : Type*} [Fintype V] (c : ℝ → ℝ) (hc : IsChannelCost c)
(f : V → ℝ) (Λ : V → V → ℝ) (hΛ : IsLN Λ) (hsupp : Supports Λ f)
(k : ℕ) (hk : 3 ≤ k) (hodd : Odd k) (u : Fin k → V) (hu : Function.Injective u)
(hcyc : ∀ j : Fin k, Λ (u j) (u (finRotate k j)) ≠ 0) :
¬ IsCostMinimizing c f Λ := by sorry
end LNTopology.Local
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.