oriented_diameter_four_lower_bound
f(4) >= 12: there is a finite connected bridgeless simple graph of diameter 4 that has no strong orientation of directed diameter at most 11.
Statement
theorem oriented_diameter_four_lower_bound : ¬ oriented_diameter_bound_holds 4 11- Formalizes
- arXiv:2610.09648 (An asymptotically tight bound on oriented diameter), Section 1: the general lower bound f(d) >= ceil(d^2/2) + d (from a 1978 construction, cited there), at d = 4.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- oriented_diameter_bound_holdsoriented_diameter_bound_holds d k: every finite connected bridgeless simple graph of diameter d (taken on vertex set Fin n, which loses…
- digraph_reach_withindigraph_reach_within D k u v: there is a directed walk of length at most k from u to v in the digraph D (equivalently, the directed…
- has_strong_orientation_of_diameter_leThe simple graph G has an orientation D (each edge of G gets exactly one direction, no other arcs) in which every ordered pair of vertices…
- is_graph_orientationA digraph D is an orientation of a simple graph G if every edge of G is assigned exactly one direction in D, and non-adjacent pairs in G…
- Arena.Reachable.transReachability is transitive.
The proof, explained
The theorem proves that there is a finite connected bridgeless simple graph of diameter 4 with no strong orientation of directed diameter at most 11, disproving f(4) ≤ 11 and thereby establishing f(4) ≥ 12. The counterexample is an explicit 17-vertex graph `ct_graph` formed by two 5-cycles meeting at a central root vertex 0, with a triangle attached to each of the four neighbors of 0. Using BFS search and finite kernel computations, the graph is verified to be connected, bridgeless, and of diameter exactly 4. To prove that no orientation has directed diameter at most 11, the argument uses potential functions as discrete Lipschitz certificates: six regional constraints force orientations along cycles and triangles, and an exhaustive 16-case split demonstrates that every possible orientation would force the directed distance between two vertices to exceed 11.
Adjacency in ct_graph is decidable.
Decidability of ct_graph adjacency between vertices a and b is established via `decidable_of_iff` by reducing it to checking whether a ≠ b and either (a, b) or (b, a) belongs to the finite edge list ct_edges, which `simp` evaluates.
uses
decidable_of_iffinstance ct_graph_dec : DecidableRel ct_graph.Adj := fun a b => decidable_of_iff (a ≠ b ∧ ((a.val, b.val) ∈ ct_edges ∨ (b.val, a.val) ∈ ct_edges)) (by simp [ct_graph])
A 1-Lipschitz potential bounds directed reachability: φ(v) ≤ φ(u) + k whenever v is reachable from u within k steps.
We prove `ct_reach_potential` by induction on k. At k = 0, u = v, so φ(v) ≤ φ(u) + 0 is trivial. For k + 1, either v was reachable in k steps (where the induction hypothesis applies directly), or there is an initial edge u → w followed by a walk of length at most k from w to v. Applying the 1-Lipschitz edge hypothesis φ(w) ≤ φ(u) + 1 and the induction hypothesis φ(v) ≤ φ(w) + k, linear arithmetic (`omega`) yields φ(v) ≤ φ(u) + (k + 1).
uses
ct_reach_potentialtheorem ct_reach_potential {V : Type*} (D : Digraph V) (φ : V → ℕ) (h : ∀ x y, D.Adj x y → φ y ≤ φ x + 1) : ∀ k u v, digraph_reach_within D k u v → φ v ≤ φ u + k | 0, u, v, h0 => by have : u = v := h0 subst this; omega | k + 1, u, v, h1 => by rcases h1 with h1 | ⟨w, hw, h1⟩ · have := ct_reach_potential D φ h k u v h1; omega · have := ct_reach_potential D φ h k w v h1 have := h u w hw; omega
An orientation of diameter at most 11 cannot have a potential function satisfying φ(u) + 11 < φ(v) on any vertex pair, provided all valid edges are 1-Lipschitz.
In `ct_contra`, let D be an orientation with diameter at most 11, and let `bad` be a list of edges proven absent from D. If every undirected edge in ct_graph either satisfies φ(y) ≤ φ(x) + 1 or belongs to `bad`, then every directed edge present in D satisfies φ(y) ≤ φ(x) + 1. By `ct_reach_potential`, any path of length at most 11 forces φ(v) ≤ φ(u) + 11, which directly contradicts φ(u) + 11 < φ(v).
uses
Or.inl,ct_reach_potentialtheorem ct_contra (D : Digraph (Fin 17)) (hD : is_graph_orientation ct_graph D) (hall : ∀ u v, digraph_reach_within D 11 u v) (l : List ℕ) (bad : List (Fin 17 × Fin 17)) (hbad : ∀ p ∈ bad, ¬ D.Adj p.1 p.2) (hG : ∀ x y, ct_graph.Adj x y → ct_pot l y ≤ ct_pot l x + 1 ∨ (x, y) ∈ bad) (u v : Fin 17) (huv : ct_pot l u + 11 < ct_pot l v) : False := by have hφ : ∀ x y, D.Adj x y → ct_pot l y ≤ ct_pot l x + 1 := by intro x y hxy rcases hG x y ((hD.1 x y).mp (Or.inl hxy)) with h | h · exact h · exact absurd hxy (hbad _ h) have := ct_reach_potential D (ct_pot l) hφ 11 u v (hall u v) omega
Any strong orientation of ct_graph of diameter at most 11 satisfies six regional orientation constraints.
Assuming an orientation D has diameter at most 11, we deduce six disjunctions: 0 → 1 ∨ 0 → 4 (F1), 5 → 0 ∨ 8 → 0 (F3), 1 → 9 ∨ 1 → 10 (T1), 4 → 11 ∨ 4 → 12 (T4), 13 → 5 ∨ 14 → 5 (T5), and 15 → 8 ∨ 16 → 8 (T8). In each case, assuming by contradiction that both directions fail, the corresponding subgraph is cut off; an explicit two-valued potential function (0 on one side, 100 on the other) separates the regions, and `ct_contra` with kernel evaluation (`decide +kernel`) derives a contradiction.
uses
ct_contratheorem ct_no_orientation_le_eleven : ¬ has_strong_orientation_of_diameter_le ct_graph 11 := by rintro ⟨D, hD, hall⟩ -- region facts have F1 : D.Adj 0 1 ∨ D.Adj 0 4 := by by_contra h; push Not at h exact ct_contra D hD hall [0,100,100,100,100,0,0,0,0,100,100,100,100,0,0,0,0] [(0,1),(0,4)] (by simpa using h) (by decide +kernel) 0 2 (by decide +kernel) have F3 : D.Adj 5 0 ∨ D.Adj 8 0 := by by_contra h; push Not at h exact ct_contra D hD hall [100,100,100,100,100,0,0,0,0,100,100,100,100,0,0,0,0] [(5,0),(8,0)] (by simpa using h) (by decide +kernel) 6 0 (by decide +kernel) have T1 : D.Adj 1 9 ∨ D.Adj 1 10 := by by_contra h; push Not at h exact ct_contra D hD hall [0,0,0,0,0,0,0,0,0,100,100,0,0,0,0,0,0] [(1,9),(1,10)] (by simpa using h) (by decide +kernel) 0 9 (by decide +kernel) have T4 : D.Adj 4 11 ∨ D.Adj 4 12 := by by_contra h; push Not at h exact ct_contra D hD hall [0,0,0,0,0,0,0,0,0,0,0,100,100,0,0,0,0] [(4,11),(4,12)] (by simpa using h) (by decide +kernel) 0 11 (by decide +kernel) have T5 : D.Adj 13 5 ∨ D.Adj 14 5 := by by_contra h; push Not at h exact ct_contra D hD hall [100,100,100,100,100,100,100,100,100,100,100,100,100,0,0,100,100] [(13,5),(14,5)] (by simpa using h) (by decide +kernel) 13 0 (by decide +kernel) have T8 : D.Adj 15 8 ∨ D.Adj 16 8 := by by_contra h; push Not at h exact ct_contra D hD hall [100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,0,0] [(15,8),(16,8)] (by simpa using h) (by decide +kernel) 15 0 (by decide +kernel)
ct_graph has no strong orientation with directed diameter at most 11. automation
We split into 16 cases according to the choices from F1, F3, and the triangle orientations T1, T4, T5, and T8. In each branch, `ct_anti` deduces that the opposite directed edges are absent, and `ct_contra` is supplied with an explicit 17-element potential list where the potential difference between a chosen source and sink vertex is 12 (strictly exceeding 11). Lean's kernel verifies by finite check (`decide +kernel`) that the 1-Lipschitz condition holds on all remaining edges, closing all 16 branches.
uses
ct_contra,ct_anti-- main potentials -- vertex order: 0 r; 1..4 C5#1; 5..8 C5#2; 9 10 at 1; 11 12 at 4; 13 14 at 5; 15 16 at 8 rcases F1 with h01 | h04 · -- s1 = 1, C5#1 long way 1,2,3,4 ; triangle at 4 gets 6 rcases T1 with ht | ht · -- t1 = 9 (0), 10 (1) rcases F3 with h50 | h80 · -- s2 = 5 (10), s2' = 8 (7): 8:7, 7:8, 6:9, 5:10; triangle at 8: 8,8 rcases T5 with hs | hs · -- t2 = 13 (12), 14 (11) exact ct_contra D hD hall [6,2,3,4,5,10,9,8,7,0,1,6,6,12,11,8,8] [(1,0),(9,1),(0,5),(5,13)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 9 13 (by decide +kernel) · exact ct_contra D hD hall [6,2,3,4,5,10,9,8,7,0,1,6,6,11,12,8,8] [(1,0),(9,1),(0,5),(5,14)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 9 14 (by decide +kernel) · rcases T8 with hs | hs · exact ct_contra D hD hall [6,2,3,4,5,7,8,9,10,0,1,6,6,8,8,12,11] [(1,0),(9,1),(0,8),(8,15)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 9 15 (by decide +kernel) · exact ct_contra D hD hall [6,2,3,4,5,7,8,9,10,0,1,6,6,8,8,11,12] [(1,0),(9,1),(0,8),(8,16)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 9 16 (by decide +kernel) · rcases F3 with h50 | h80 · rcases T5 with hs | hs · exact ct_contra D hD hall [6,2,3,4,5,10,9,8,7,1,0,6,6,12,11,8,8] [(1,0),(10,1),(0,5),(5,13)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 10 13 (by decide +kernel) · exact ct_contra D hD hall [6,2,3,4,5,10,9,8,7,1,0,6,6,11,12,8,8] [(1,0),(10,1),(0,5),(5,14)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 10 14 (by decide +kernel) · rcases T8 with hs | hs · exact ct_contra D hD hall [6,2,3,4,5,7,8,9,10,1,0,6,6,8,8,12,11] [(1,0),(10,1),(0,8),(8,15)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 10 15 (by decide +kernel) · exact ct_contra D hD hall [6,2,3,4,5,7,8,9,10,1,0,6,6,8,8,11,12] [(1,0),(10,1),(0,8),(8,16)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 10 16 (by decide +kernel) · -- s1 = 4: 4:2, 3:3, 2:4, 1:5; triangle at 1 gets 6; t1 in {11,12} rcases T4 with ht | ht · rcases F3 with h50 | h80 · rcases T5 with hs | hs · exact ct_contra D hD hall [6,5,4,3,2,10,9,8,7,6,6,0,1,12,11,8,8] [(4,0),(11,4),(0,5),(5,13)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 11 13 (by decide +kernel) · exact ct_contra D hD hall [6,5,4,3,2,10,9,8,7,6,6,0,1,11,12,8,8] [(4,0),(11,4),(0,5),(5,14)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 11 14 (by decide +kernel) · rcases T8 with hs | hs · exact ct_contra D hD hall [6,5,4,3,2,7,8,9,10,6,6,0,1,8,8,12,11] [(4,0),(11,4),(0,8),(8,15)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 11 15 (by decide +kernel) · exact ct_contra D hD hall [6,5,4,3,2,7,8,9,10,6,6,0,1,8,8,11,12] [(4,0),(11,4),(0,8),(8,16)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 11 16 (by decide +kernel) · rcases F3 with h50 | h80 · rcases T5 with hs | hs · exact ct_contra D hD hall [6,5,4,3,2,10,9,8,7,6,6,1,0,12,11,8,8] [(4,0),(12,4),(0,5),(5,13)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 12 13 (by decide +kernel) · exact ct_contra D hD hall [6,5,4,3,2,10,9,8,7,6,6,1,0,11,12,8,8] [(4,0),(12,4),(0,5),(5,14)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 12 14 (by decide +kernel) · rcases T8 with hs | hs · exact ct_contra D hD hall [6,5,4,3,2,7,8,9,10,6,6,1,0,8,8,12,11] [(4,0),(12,4),(0,8),(8,15)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 12 15 (by decide +kernel) · exact ct_contra D hD hall [6,5,4,3,2,7,8,9,10,6,6,1,0,8,8,11,12] [(4,0),(12,4),(0,8),(8,16)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 12 16 (by decide +kernel)
Every vertex found in the k-step BFS set is reachable by a walk of length at most k.
We prove `ct_bfs_walk` by induction on k. At k = 0, y ∈ {u} means y = u, witnessed by the empty walk `SimpleGraph.Walk.nil` of length 0. At step k + 1, y is either reached at step k (where induction gives a walk of length ≤ k ≤ k + 1), or y is adjacent to some x reached at step k. Appending the edge x ~ y to the walk to x via `concat` yields a walk of length at most k + 1.
uses
SimpleGraph.Walk.nil,le_refl,Finset.mem_union,Finset.mem_filter,Finset.mem_univ,true_and,ct_bfs_walk,SimpleGraph.Walk.length_concattheorem ct_bfs_walk (H : SimpleGraph (Fin 17)) [DecidableRel H.Adj] : ∀ k u y, y ∈ ct_bfs H k u → ∃ p : H.Walk u y, p.length ≤ k | 0, u, y, h => by simp [ct_bfs] at h; subst h; exact ⟨SimpleGraph.Walk.nil, le_refl _⟩ | k + 1, u, y, h => by simp only [ct_bfs, Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and] at h rcases h with h | ⟨x, hx, hxy⟩ · obtain ⟨p, hp⟩ := ct_bfs_walk H k u y h; exact ⟨p, by omega⟩ · obtain ⟨p, hp⟩ := ct_bfs_walk H k u x hx exact ⟨p.concat hxy, by rw [SimpleGraph.Walk.length_concat]; omega⟩
A 1-Lipschitz potential function on an undirected graph bounds the length of any walk: φ(v) ≤ φ(u) + length(p).
In `ct_walk_potential`, we induct on the walk p. The empty walk is trivial. For a walk cons(hxy, p'), the induction hypothesis gives φ(v) ≤ φ(y) + length(p'), while the 1-Lipschitz hypothesis gives φ(y) ≤ φ(u) + 1. Adding these inequalities gives φ(v) ≤ φ(u) + (length(p') + 1).
uses
ct_walk_potential,SimpleGraph.Walk.length_constheorem ct_walk_potential (φ : Fin 17 → ℕ) (h : ∀ x y, ct_graph.Adj x y → φ y ≤ φ x + 1) : ∀ {u v : Fin 17} (p : ct_graph.Walk u v), φ v ≤ φ u + p.length | _, _, .nil => by simp | _, _, .cons hxy p => by have := ct_walk_potential φ h p have := h _ _ hxy simp only [SimpleGraph.Walk.length_cons]; omega
Every vertex of ct_graph is within extended distance 2 of the central root vertex 0.
`ct_to_root` verifies by kernel evaluation (`decide +kernel`) that 0 is in the 2-step BFS set from every vertex u. Then `ct_edist_root` applies `ct_bfs_walk` to obtain a walk of length at most 2 to 0, which by `SimpleGraph.edist_le` implies edist(u, 0) ≤ 2.
uses
ct_bfs_walk,ct_to_root,SimpleGraph.edist_letheorem ct_to_root : ∀ u : Fin 17, (0 : Fin 17) ∈ ct_bfs ct_graph 2 u := by decide +kernel theorem ct_edist_root (u : Fin 17) : ct_graph.edist u 0 ≤ 2 := by obtain ⟨p, hp⟩ := ct_bfs_walk ct_graph 2 u 0 (ct_to_root u) exact (SimpleGraph.edist_le p).trans (by exact_mod_cast hp)
ct_graph is connected.
Every vertex can reach the central vertex 0 via the walk from `ct_to_root`. Composing the walk from u to 0 with the reversed walk from 0 to v proves that every pair u, v is connected by a walk.
uses
ct_bfs_walk,ct_to_roottheorem ct_connected : ct_graph.Connected := by have h : ∀ u, ct_graph.Reachable u 0 := fun u => (ct_bfs_walk ct_graph 2 u 0 (ct_to_root u)).elim fun p _ => ⟨p⟩ exact ⟨fun u v => (h u).trans (h v).symm⟩
ct_graph has diameter exactly 4.
For the upper bound, the triangle inequality through the root 0 gives edist(u, v) ≤ edist(u, 0) + edist(0, v) ≤ 2 + 2 = 4, so ediam ≤ 4 by `SimpleGraph.ediam_le_of_edist_le`. For the lower bound, an explicit potential list separating vertices 9 and 13 is verified to be 1-Lipschitz by kernel evaluation; by `ct_walk_potential`, any walk between them has length at least φ(13) - φ(9) = 4 - 0 = 4, so ediam ≥ 4. Antisymmetry yields ediam = 4, and projecting to Nat gives diam = 4.
uses
le_antisymm,SimpleGraph.ediam_le_of_edist_le,SimpleGraph.edist_triangle,ct_edist_root,SimpleGraph.edist_comm,ct_connected,ct_walk_potential,SimpleGraph.edist_le_ediam,SimpleGraph.diam,ct_ediamtheorem ct_ediam : ct_graph.ediam = 4 := by apply le_antisymm · apply SimpleGraph.ediam_le_of_edist_le intro u v calc ct_graph.edist u v ≤ ct_graph.edist u 0 + ct_graph.edist 0 v := SimpleGraph.edist_triangle _ ≤ 2 + 2 := by gcongr · exact ct_edist_root u · rw [SimpleGraph.edist_comm]; exact ct_edist_root v _ = 4 := by norm_num · obtain ⟨p, hp⟩ := (ct_connected 9 13).exists_walk_length_eq_edist have := ct_walk_potential (ct_pot [2,1,2,3,3,3,4,4,3,0,1,4,4,4,4,4,4]) (by decide +kernel) p have h4 : 4 ≤ p.length := by simpa [ct_pot] using this calc (4 : ℕ∞) ≤ p.length := by exact_mod_cast h4 _ = ct_graph.edist 9 13 := hp _ ≤ ct_graph.ediam := SimpleGraph.edist_le_ediam theorem ct_diam : ct_graph.diam = 4 := by rw [SimpleGraph.diam, ct_ediam]; rfl
Adjacency in the edge-deleted graph ct_graph \ {s(x, y)} is decidable.
The instance `ct_del_dec` shows that adjacency after deleting an edge s(x, y) is decidable by rewriting via `SimpleGraph.deleteEdges_adj` to the decidable conjunction of original adjacency and non-equality of unordered pairs.
uses
decidable_of_iff,SimpleGraph.deleteEdges_adj@[instance_reducible] def ct_del_dec (x y : Fin 17) : DecidableRel (ct_graph.deleteEdges {s(x, y)}).Adj := fun a b => decidable_of_iff (ct_graph.Adj a b ∧ ¬((a = x ∧ b = y) ∨ (a = y ∧ b = x))) (by simp [SimpleGraph.deleteEdges_adj])
ct_graph is bridgeless.
`ct_cycles` checks by kernel evaluation that for every adjacent pair x ~ y, y is reachable from x within 4 steps in ct_graph \ {s(x, y)}. Then `ct_bridgeless` inducts on the unordered pair e = s(x, y). If x and y are adjacent, the 4-step alternative walk shows they remain reachable after deleting e, so e is not a bridge by `SimpleGraph.isBridge_iff`. If x and y are not adjacent, deleting s(x, y) leaves all edges intact, so reachability is preserved from connectedness.
uses
Sym2.ind,SimpleGraph.isBridge_iff,not_not,ct_bfs_walk,ct_del_dec,ct_cycles,SimpleGraph.deleteEdges_adj,Set.mem_singleton_iff,Sym2.eq_iff,ct_connectedtheorem ct_cycles : ∀ x y : Fin 17, ct_graph.Adj x y → y ∈ @ct_bfs (ct_graph.deleteEdges {s(x, y)}) (ct_del_dec x y) 4 x := by decide +kernel theorem ct_bridgeless : ∀ e, ¬ ct_graph.IsBridge e := by intro e induction e using Sym2.ind with | _ x y => rw [SimpleGraph.isBridge_iff, not_not] by_cases h : ct_graph.Adj x y · obtain ⟨p, _⟩ := @ct_bfs_walk _ (ct_del_dec x y) 4 x y (ct_cycles x y h) exact ⟨p⟩ · have hle : ct_graph ≤ ct_graph.deleteEdges {s(x, y)} := by intro a b hab rw [SimpleGraph.deleteEdges_adj] refine ⟨hab, ?_⟩ intro hm simp only [Set.mem_singleton_iff, Sym2.eq_iff] at hm rcases hm with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h hab · exact h hab.symm exact (ct_connected x y).mono hle
The oriented diameter bound f(4) ≤ 11 fails, establishing f(4) ≥ 12.
If `oriented_diameter_bound_holds 4 11` held, then applying it to the 17-vertex graph ct_graph—which is connected (`ct_connected`), bridgeless (`ct_bridgeless`), and has diameter 4 (`ct_diam`)—would guarantee a strong orientation of directed diameter at most 11. But `ct_no_orientation_le_eleven` proves no such orientation exists, a contradiction.
uses
ct_no_orientation_le_eleven,ct_graph,ct_connected,ct_bridgeless,ct_diamtheorem oriented_diameter_four_lower_bound : ¬ oriented_diameter_bound_holds 4 11 := fun h => ct_no_orientation_le_eleven (h 17 ct_graph ct_connected ct_bridgeless ct_diam)
decidable_of_iff- a proposition is decidable if it is logically equivalent to a decidable proposition
ct_reach_potential- if every directed edge increases potential φ by at most 1, then reachability in at most k steps implies φ(v) ≤ φ(u) + k
Or.inl- from a proof of P, concludes the disjunction P ∨ Q
ct_contra- derives a contradiction if an orientation of diameter at most 11 avoids a forbidden edge set and respects a potential φ with φ(u) + 11 < φ(v)
ct_anti- in an orientation of a simple graph, if directed edge x → y is present, then directed edge y → x is absent
SimpleGraph.Walk.nil- the empty walk from a vertex to itself, of length 0
le_refl- reflexivity of ≤: every element is less than or equal to itself
Finset.mem_union- an element belongs to the union s ∪ t if and only if it belongs to s or to t
Finset.mem_filter- an element belongs to Finset.filter p s if and only if it belongs to s and satisfies p
Finset.mem_univ- every element of a finite type belongs to Finset.univ
true_and- True ∧ P is logically equivalent to P
ct_bfs_walk- if y is in the k-step BFS set from u, there is a walk from u to y of length at most k
SimpleGraph.Walk.length_concat- the length of a walk concatenated with an edge at the end is its length plus 1
ct_walk_potential- for any 1-Lipschitz potential function on an undirected graph, the potential difference between endpoints of a walk is at most the walk's length
SimpleGraph.Walk.length_cons- the length of a walk prepended by an edge is the tail walk's length plus 1
ct_to_root- every vertex in ct_graph has the root vertex 0 in its 2-step BFS set
SimpleGraph.edist_le- the extended distance between two vertices is bounded above by the length of any walk connecting them
ct_edist_root- the extended distance in ct_graph from any vertex to 0 is at most 2
ct_connected- ct_graph is a connected graph
le_antisymm- antisymmetry of partial orders: a ≤ b and b ≤ a imply a = b
SimpleGraph.ediam_le_of_edist_le- if the extended distance between all pairs of vertices is at most k, the extended diameter is at most k
SimpleGraph.edist_triangle- the triangle inequality for extended distance: edist(u, w) ≤ edist(u, v) + edist(v, w)
SimpleGraph.edist_comm- extended distance in an undirected graph is symmetric: edist(u, v) = edist(v, u)
SimpleGraph.edist_le_ediam- the extended distance between any two vertices is at most the graph's extended diameter
SimpleGraph.diam- the natural-number diameter of a simple graph is the projection of its extended diameter
ct_ediam- the extended diameter of ct_graph equals 4
ct_del_dec- adjacency in the edge-deleted graph ct_graph.deleteEdges {s(x, y)} is decidable
SimpleGraph.deleteEdges_adj- two vertices are adjacent in an edge-deleted graph iff they were adjacent and the edge is not in the deleted set
ct_cycles- for every edge {x, y} in ct_graph, y is reachable from x in at most 4 steps after deleting {x, y}
Sym2.ind- induction principle on unordered pairs: every element of Sym2(V) is of the form s(x, y)
SimpleGraph.isBridge_iff- an edge s(u, v) is a bridge if and only if u and v are unreachable in the graph with s(u, v) deleted
not_not- double negation elimination: ¬¬P ↔ P
Set.mem_singleton_iff- an element belongs to the singleton {b} if and only if it equals b
Sym2.eq_iff- unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z ∧ y = w) ∨ (x = w ∧ y = z)
ct_no_orientation_le_eleven- ct_graph has no strong orientation with directed diameter at most 11
ct_graph- the 17-vertex simple graph with two 5-cycles meeting at 0 and four attached triangles
ct_bridgeless- no edge in ct_graph is a bridge
ct_diam- the diameter of ct_graph is 4
- The proof relies extensively on kernel-level computation (`decide +kernel`) to verify: (a) that the 2-step BFS from every vertex contains the root vertex 0 (`ct_to_root`), (b) that for every edge e, the endpoints are connected in G \ {e} by a 4-step walk (`ct_cycles`), and (c) the discrete 1-Lipschitz condition φ(y) ≤ φ(x) + 1 ∨ (x, y) ∈ bad across all edges in the 6 regional orientation constraints and all 16 case-by-case contradiction calls.
- The case split in `ct_no_orientation_le_eleven` covers 16 combinations of edge directions. Each branch provides an explicit potential vector on the 17 vertices, and the kernel computation checks that the potential difference along valid directed edges never exceeds 1 while the potential difference between the designated source and sink vertices is at least 12.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
def ct_edges : List (ℕ × ℕ) := [(0,1),(1,2),(2,3),(3,4),(4,0),(0,5),(5,6),(6,7),(7,8),(8,0),(1,9),(1,10),(9,10), (4,11),(4,12),(11,12),(5,13),(5,14),(13,14),(8,15),(8,16),(15,16)]def ct_graph : SimpleGraph (Fin 17) := SimpleGraph.fromRel (fun a b => (a.val, b.val) ∈ ct_edges)instance ct_graph_dec : DecidableRel ct_graph.Adj := fun a b => decidable_of_iff (a ≠ b ∧ ((a.val, b.val) ∈ ct_edges ∨ (b.val, a.val) ∈ ct_edges)) (by simp [ct_graph])def ct_pot (l : List ℕ) (i : Fin 17) : ℕ := l.getD i.val 0theorem ct_reach_potential {V : Type*} (D : Digraph V) (φ : V → ℕ) (h : ∀ x y, D.Adj x y → φ y ≤ φ x + 1) : ∀ k u v, digraph_reach_within D k u v → φ v ≤ φ u + k | 0, u, v, h0 => by have : u = v := h0 subst this; omega | k + 1, u, v, h1 => by rcases h1 with h1 | ⟨w, hw, h1⟩ · have := ct_reach_potential D φ h k u v h1; omega · have := ct_reach_potential D φ h k w v h1 have := h u w hw; omegatheorem ct_contra (D : Digraph (Fin 17)) (hD : is_graph_orientation ct_graph D) (hall : ∀ u v, digraph_reach_within D 11 u v) (l : List ℕ) (bad : List (Fin 17 × Fin 17)) (hbad : ∀ p ∈ bad, ¬ D.Adj p.1 p.2) (hG : ∀ x y, ct_graph.Adj x y → ct_pot l y ≤ ct_pot l x + 1 ∨ (x, y) ∈ bad) (u v : Fin 17) (huv : ct_pot l u + 11 < ct_pot l v) : False := by have hφ : ∀ x y, D.Adj x y → ct_pot l y ≤ ct_pot l x + 1 := by intro x y hxy rcases hG x y ((hD.1 x y).mp (Or.inl hxy)) with h | h · exact h · exact absurd hxy (hbad _ h) have := ct_reach_potential D (ct_pot l) hφ 11 u v (hall u v) omegatheorem ct_anti {D : Digraph (Fin 17)} (hD : is_graph_orientation ct_graph D) {x y : Fin 17} (h : D.Adj x y) : ¬ D.Adj y x := fun h' => hD.2 x y ⟨h, h'⟩theorem ct_no_orientation_le_eleven : ¬ has_strong_orientation_of_diameter_le ct_graph 11 := by rintro ⟨D, hD, hall⟩ -- region facts have F1 : D.Adj 0 1 ∨ D.Adj 0 4 := by by_contra h; push Not at h exact ct_contra D hD hall [0,100,100,100,100,0,0,0,0,100,100,100,100,0,0,0,0] [(0,1),(0,4)] (by simpa using h) (by decide +kernel) 0 2 (by decide +kernel) have F3 : D.Adj 5 0 ∨ D.Adj 8 0 := by by_contra h; push Not at h exact ct_contra D hD hall [100,100,100,100,100,0,0,0,0,100,100,100,100,0,0,0,0] [(5,0),(8,0)] (by simpa using h) (by decide +kernel) 6 0 (by decide +kernel) have T1 : D.Adj 1 9 ∨ D.Adj 1 10 := by by_contra h; push Not at h exact ct_contra D hD hall [0,0,0,0,0,0,0,0,0,100,100,0,0,0,0,0,0] [(1,9),(1,10)] (by simpa using h) (by decide +kernel) 0 9 (by decide +kernel) have T4 : D.Adj 4 11 ∨ D.Adj 4 12 := by by_contra h; push Not at h exact ct_contra D hD hall [0,0,0,0,0,0,0,0,0,0,0,100,100,0,0,0,0] [(4,11),(4,12)] (by simpa using h) (by decide +kernel) 0 11 (by decide +kernel) have T5 : D.Adj 13 5 ∨ D.Adj 14 5 := by by_contra h; push Not at h exact ct_contra D hD hall [100,100,100,100,100,100,100,100,100,100,100,100,100,0,0,100,100] [(13,5),(14,5)] (by simpa using h) (by decide +kernel) 13 0 (by decide +kernel) have T8 : D.Adj 15 8 ∨ D.Adj 16 8 := by by_contra h; push Not at h exact ct_contra D hD hall [100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,0,0] [(15,8),(16,8)] (by simpa using h) (by decide +kernel) 15 0 (by decide +kernel) -- main potentials -- vertex order: 0 r; 1..4 C5#1; 5..8 C5#2; 9 10 at 1; 11 12 at 4; 13 14 at 5; 15 16 at 8 rcases F1 with h01 | h04 · -- s1 = 1, C5#1 long way 1,2,3,4 ; triangle at 4 gets 6 rcases T1 with ht | ht · -- t1 = 9 (0), 10 (1) rcases F3 with h50 | h80 · -- s2 = 5 (10), s2' = 8 (7): 8:7, 7:8, 6:9, 5:10; triangle at 8: 8,8 rcases T5 with hs | hs · -- t2 = 13 (12), 14 (11) exact ct_contra D hD hall [6,2,3,4,5,10,9,8,7,0,1,6,6,12,11,8,8] [(1,0),(9,1),(0,5),(5,13)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 9 13 (by decide +kernel) · exact ct_contra D hD hall [6,2,3,4,5,10,9,8,7,0,1,6,6,11,12,8,8] [(1,0),(9,1),(0,5),(5,14)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 9 14 (by decide +kernel) · rcases T8 with hs | hs · exact ct_contra D hD hall [6,2,3,4,5,7,8,9,10,0,1,6,6,8,8,12,11] [(1,0),(9,1),(0,8),(8,15)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 9 15 (by decide +kernel) · exact ct_contra D hD hall [6,2,3,4,5,7,8,9,10,0,1,6,6,8,8,11,12] [(1,0),(9,1),(0,8),(8,16)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 9 16 (by decide +kernel) · rcases F3 with h50 | h80 · rcases T5 with hs | hs · exact ct_contra D hD hall [6,2,3,4,5,10,9,8,7,1,0,6,6,12,11,8,8] [(1,0),(10,1),(0,5),(5,13)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 10 13 (by decide +kernel) · exact ct_contra D hD hall [6,2,3,4,5,10,9,8,7,1,0,6,6,11,12,8,8] [(1,0),(10,1),(0,5),(5,14)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 10 14 (by decide +kernel) · rcases T8 with hs | hs · exact ct_contra D hD hall [6,2,3,4,5,7,8,9,10,1,0,6,6,8,8,12,11] [(1,0),(10,1),(0,8),(8,15)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 10 15 (by decide +kernel) · exact ct_contra D hD hall [6,2,3,4,5,7,8,9,10,1,0,6,6,8,8,11,12] [(1,0),(10,1),(0,8),(8,16)] (by simp [ct_anti hD h01, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 10 16 (by decide +kernel) · -- s1 = 4: 4:2, 3:3, 2:4, 1:5; triangle at 1 gets 6; t1 in {11,12} rcases T4 with ht | ht · rcases F3 with h50 | h80 · rcases T5 with hs | hs · exact ct_contra D hD hall [6,5,4,3,2,10,9,8,7,6,6,0,1,12,11,8,8] [(4,0),(11,4),(0,5),(5,13)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 11 13 (by decide +kernel) · exact ct_contra D hD hall [6,5,4,3,2,10,9,8,7,6,6,0,1,11,12,8,8] [(4,0),(11,4),(0,5),(5,14)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 11 14 (by decide +kernel) · rcases T8 with hs | hs · exact ct_contra D hD hall [6,5,4,3,2,7,8,9,10,6,6,0,1,8,8,12,11] [(4,0),(11,4),(0,8),(8,15)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 11 15 (by decide +kernel) · exact ct_contra D hD hall [6,5,4,3,2,7,8,9,10,6,6,0,1,8,8,11,12] [(4,0),(11,4),(0,8),(8,16)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 11 16 (by decide +kernel) · rcases F3 with h50 | h80 · rcases T5 with hs | hs · exact ct_contra D hD hall [6,5,4,3,2,10,9,8,7,6,6,1,0,12,11,8,8] [(4,0),(12,4),(0,5),(5,13)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 12 13 (by decide +kernel) · exact ct_contra D hD hall [6,5,4,3,2,10,9,8,7,6,6,1,0,11,12,8,8] [(4,0),(12,4),(0,5),(5,14)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h50, ct_anti hD hs]) (by decide +kernel) 12 14 (by decide +kernel) · rcases T8 with hs | hs · exact ct_contra D hD hall [6,5,4,3,2,7,8,9,10,6,6,1,0,8,8,12,11] [(4,0),(12,4),(0,8),(8,15)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 12 15 (by decide +kernel) · exact ct_contra D hD hall [6,5,4,3,2,7,8,9,10,6,6,1,0,8,8,11,12] [(4,0),(12,4),(0,8),(8,16)] (by simp [ct_anti hD h04, ct_anti hD ht, ct_anti hD h80, ct_anti hD hs]) (by decide +kernel) 12 16 (by decide +kernel)def ct_bfs (H : SimpleGraph (Fin 17)) [DecidableRel H.Adj] : ℕ → Fin 17 → Finset (Fin 17) | 0, u => {u} | k + 1, u => ct_bfs H k u ∪ Finset.univ.filter (fun y => ∃ x ∈ ct_bfs H k u, H.Adj x y)theorem ct_bfs_walk (H : SimpleGraph (Fin 17)) [DecidableRel H.Adj] : ∀ k u y, y ∈ ct_bfs H k u → ∃ p : H.Walk u y, p.length ≤ k | 0, u, y, h => by simp [ct_bfs] at h; subst h; exact ⟨SimpleGraph.Walk.nil, le_refl _⟩ | k + 1, u, y, h => by simp only [ct_bfs, Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and] at h rcases h with h | ⟨x, hx, hxy⟩ · obtain ⟨p, hp⟩ := ct_bfs_walk H k u y h; exact ⟨p, by omega⟩ · obtain ⟨p, hp⟩ := ct_bfs_walk H k u x hx exact ⟨p.concat hxy, by rw [SimpleGraph.Walk.length_concat]; omega⟩theorem ct_walk_potential (φ : Fin 17 → ℕ) (h : ∀ x y, ct_graph.Adj x y → φ y ≤ φ x + 1) : ∀ {u v : Fin 17} (p : ct_graph.Walk u v), φ v ≤ φ u + p.length | _, _, .nil => by simp | _, _, .cons hxy p => by have := ct_walk_potential φ h p have := h _ _ hxy simp only [SimpleGraph.Walk.length_cons]; omegatheorem ct_to_root : ∀ u : Fin 17, (0 : Fin 17) ∈ ct_bfs ct_graph 2 u := by decide +kerneltheorem ct_edist_root (u : Fin 17) : ct_graph.edist u 0 ≤ 2 := by obtain ⟨p, hp⟩ := ct_bfs_walk ct_graph 2 u 0 (ct_to_root u) exact (SimpleGraph.edist_le p).trans (by exact_mod_cast hp)theorem ct_connected : ct_graph.Connected := by have h : ∀ u, ct_graph.Reachable u 0 := fun u => (ct_bfs_walk ct_graph 2 u 0 (ct_to_root u)).elim fun p _ => ⟨p⟩ exact ⟨fun u v => (h u).trans (h v).symm⟩theorem ct_ediam : ct_graph.ediam = 4 := by apply le_antisymm · apply SimpleGraph.ediam_le_of_edist_le intro u v calc ct_graph.edist u v ≤ ct_graph.edist u 0 + ct_graph.edist 0 v := SimpleGraph.edist_triangle _ ≤ 2 + 2 := by gcongr · exact ct_edist_root u · rw [SimpleGraph.edist_comm]; exact ct_edist_root v _ = 4 := by norm_num · obtain ⟨p, hp⟩ := (ct_connected 9 13).exists_walk_length_eq_edist have := ct_walk_potential (ct_pot [2,1,2,3,3,3,4,4,3,0,1,4,4,4,4,4,4]) (by decide +kernel) p have h4 : 4 ≤ p.length := by simpa [ct_pot] using this calc (4 : ℕ∞) ≤ p.length := by exact_mod_cast h4 _ = ct_graph.edist 9 13 := hp _ ≤ ct_graph.ediam := SimpleGraph.edist_le_ediamtheorem ct_diam : ct_graph.diam = 4 := by rw [SimpleGraph.diam, ct_ediam]; rfl@[instance_reducible] def ct_del_dec (x y : Fin 17) : DecidableRel (ct_graph.deleteEdges {s(x, y)}).Adj := fun a b => decidable_of_iff (ct_graph.Adj a b ∧ ¬((a = x ∧ b = y) ∨ (a = y ∧ b = x))) (by simp [SimpleGraph.deleteEdges_adj])theorem ct_cycles : ∀ x y : Fin 17, ct_graph.Adj x y → y ∈ @ct_bfs (ct_graph.deleteEdges {s(x, y)}) (ct_del_dec x y) 4 x := by decide +kerneltheorem ct_bridgeless : ∀ e, ¬ ct_graph.IsBridge e := by intro e induction e using Sym2.ind with | _ x y => rw [SimpleGraph.isBridge_iff, not_not] by_cases h : ct_graph.Adj x y · obtain ⟨p, _⟩ := @ct_bfs_walk _ (ct_del_dec x y) 4 x y (ct_cycles x y h) exact ⟨p⟩ · have hle : ct_graph ≤ ct_graph.deleteEdges {s(x, y)} := by intro a b hab rw [SimpleGraph.deleteEdges_adj] refine ⟨hab, ?_⟩ intro hm simp only [Set.mem_singleton_iff, Sym2.eq_iff] at hm rcases hm with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h hab · exact h hab.symm exact (ct_connected x y).mono hletheorem oriented_diameter_four_lower_bound : ¬ oriented_diameter_bound_holds 4 11 := fun h => ct_no_orientation_le_eleven (h 17 ct_graph ct_connected ct_bridgeless ct_diam)