AFTD Auto-Formalizing Theoretical Domains

oriented_diameter_four_lower_bound

theoremverifiedformalization

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.

  1. 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.

    lines 8–10

    uses decidable_of_iff

    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])
  2. 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).

    lines 14–25

    uses ct_reach_potential

    theorem 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
    
  3. 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).

    lines 26–38

    uses Or.inl, ct_reach_potential

    theorem 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
    
  4. 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.

    lines 42–68

    uses ct_contra

    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)
  5. 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.

    lines 69–123

    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)
    
  6. 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.

    lines 128–138

    uses SimpleGraph.Walk.nil, le_refl, Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, ct_bfs_walk, SimpleGraph.Walk.length_concat

    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⟩
    
  7. 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).

    lines 139–146

    uses ct_walk_potential, SimpleGraph.Walk.length_cons

    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]; omega
    
  8. 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.

    lines 147–152

    uses ct_bfs_walk, ct_to_root, SimpleGraph.edist_le

    theorem 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)
    
  9. 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.

    lines 153–156

    uses ct_bfs_walk, ct_to_root

    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⟩
  10. 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.

    lines 158–176

    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_ediam

    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_ediam
    
    theorem ct_diam : ct_graph.diam = 4 := by
      rw [SimpleGraph.diam, ct_ediam]; rfl
  11. 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.

    lines 178–180

    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])
  12. 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.

    lines 182–203

    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_connected

    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 +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
    
  13. 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.

    lines 204–205

    uses ct_no_orientation_le_eleven, ct_graph, ct_connected, ct_bridgeless, ct_diam

    theorem 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

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

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)
See it in the graphDiscuss this resultChallenge it