AFTD Auto-Formalizing Theoretical Domains

five_vertex_t_star_dist_eq

theoremverified

In the T-graph: d(0,1) = 1, d(0,2) = 2, d(3,1) = 2, d(4,1) = 2, d(3,2) = d(4,2) = 3.

Statement

theorem five_vertex_t_star_dist_eq :
    five_vertex_t_star.dist 0 1 = 1 ∧ five_vertex_t_star.dist 0 2 = 2 ∧
      five_vertex_t_star.dist 3 1 = 2 ∧ five_vertex_t_star.dist 4 1 = 2 ∧
      five_vertex_t_star.dist 3 2 = 3 ∧ five_vertex_t_star.dist 4 2 = 3
Source
step towards lly_positive_edge_connectivity_threshold_five
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 4

The proof, explained

The theorem calculates the shortest-path distances between six pairs of vertices in the 5-vertex tree five_vertex_t_star, whose central hub 0 connects to 1, 3, and 4, with 1 further connected to 2. Distances between adjacent vertices are determined immediately from the adjacency relation. Distances of 2 (d(0,2), d(3,1), and d(4,1)) are bounded above by the triangle inequality and below by non-adjacency. Finally, the distances d(3,2) and d(4,2) are bounded above by 3 via path 3-0-2 (or 4-0-2), while any walk of length at most 2 is ruled out by exhaustive search because 0 is the unique neighbor of 3 and 4 but is not adjacent to 2.

  1. Every walk of length at most 2 connects equal vertices, adjacent vertices, or vertices that share a common neighbor.

    We proceed by case analysis on the structure of the walk p. If p is empty (length 0), the endpoints u and v are identical. If p consists of a single edge followed by the empty walk (length 1), u and v are adjacent. If p consists of two edges followed by the empty walk (length 2), the intermediate vertex witnesses a common neighbor of u and v. If p has three or more edges, its length is at least 3, which contradicts the hypothesis that the length is at most 2.

    lines 4–14

    uses Or.inl, Or.inr, SimpleGraph.Walk.length_cons

      cases p with
      | nil => exact Or.inl rfl
      | cons h1 q =>
        cases q with
        | nil => exact Or.inr (Or.inl h1)
        | cons h2 r =>
          cases r with
          | nil => exact Or.inr (Or.inr ⟨_, h1, h2⟩)
          | cons h3 s =>
            simp only [SimpleGraph.Walk.length_cons] at hp
            omega
  2. The graph five_vertex_t_star is connected, and the distances d(0,1), d(1,2), d(3,0), and d(4,0) are all 1.

    Graph connectivity is verified by finite computation (`decide`). For each vertex pair (0,1), (1,2), (3,0), and (4,0), the distance in a graph is 1 if and only if the vertices are adjacent (using `SimpleGraph.dist_eq_one_iff_adj`, combined with symmetry `SimpleGraph.dist_comm` where needed). Each corresponding adjacency check is directly decided from the edge relations defining five_vertex_t_star.

    lines 21–33

    uses SimpleGraph.dist_eq_one_iff_adj, SimpleGraph.dist_comm

      have hconn : five_vertex_t_star.Connected := by decide
      have d01 : five_vertex_t_star.dist 0 1 = 1 := by
        rw [SimpleGraph.dist_eq_one_iff_adj]
        decide
      have d12 : five_vertex_t_star.dist 1 2 = 1 := by
        rw [SimpleGraph.dist_eq_one_iff_adj]
        decide
      have d30 : five_vertex_t_star.dist 3 0 = 1 := by
        rw [SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj]
        decide
      have d40 : five_vertex_t_star.dist 4 0 = 1 := by
        rw [SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj]
        decide
  3. The distance d(0, 2) equals 2.

    By the triangle inequality through vertex 1, d(0, 2) ≤ d(0, 1) + d(1, 2) = 1 + 1 = 2. In the other direction, since 0 ≠ 2 and 0 is not adjacent to 2 (both verified by finite computation), the distance is strictly greater than 1. Combining these two inequalities yields d(0, 2) = 2.

    lines 34–40

      have d02 : five_vertex_t_star.dist 0 2 = 2 := by
        have hle : five_vertex_t_star.dist 0 2 ≤ 2 := by
          have := hconn.dist_triangle (u := 0) (v := 1) (w := 2)
          omega
        have hlt : 1 < five_vertex_t_star.dist 0 2 :=
          hconn.one_lt_dist_of_ne_of_not_adj (by decide) (by decide)
        omega
  4. The distance d(3, 1) equals 2.

    By the triangle inequality through vertex 0, d(3, 1) ≤ d(3, 0) + d(0, 1) = 1 + 1 = 2. Conversely, because 3 ≠ 1 and 3 is not adjacent to 1 (both checked by `decide`), the distance is strictly greater than 1. Thus d(3, 1) = 2.

    lines 41–47

      have d31 : five_vertex_t_star.dist 3 1 = 2 := by
        have hle : five_vertex_t_star.dist 3 1 ≤ 2 := by
          have := hconn.dist_triangle (u := 3) (v := 0) (w := 1)
          omega
        have hlt : 1 < five_vertex_t_star.dist 3 1 :=
          hconn.one_lt_dist_of_ne_of_not_adj (by decide) (by decide)
        omega
  5. The distance d(4, 1) equals 2.

    By the triangle inequality through vertex 0, d(4, 1) ≤ d(4, 0) + d(0, 1) = 1 + 1 = 2. Conversely, since 4 ≠ 1 and 4 is not adjacent to 1, the distance is strictly greater than 1. Thus d(4, 1) = 2.

    lines 48–54

      have d41 : five_vertex_t_star.dist 4 1 = 2 := by
        have hle : five_vertex_t_star.dist 4 1 ≤ 2 := by
          have := hconn.dist_triangle (u := 4) (v := 0) (w := 1)
          omega
        have hlt : 1 < five_vertex_t_star.dist 4 1 :=
          hconn.one_lt_dist_of_ne_of_not_adj (by decide) (by decide)
        omega
  6. The distance d(3, 2) equals 3.

    The triangle inequality through vertex 0 gives d(3, 2) ≤ d(3, 0) + d(0, 2) = 1 + 2 = 3. For the lower bound, suppose for contradiction that d(3, 2) ≤ 2. In a connected graph, there exists a walk from 3 to 2 realizing the distance, so its length is at most 2. By our characterization lemma, this requires 3 = 2, adjacency of 3 and 2, or a common neighbor between 3 and 2. Lean's `decide` tactic checks every vertex of the finite graph and refutes all three cases (3's only neighbor is 0, and 0 is not adjacent to 2). This contradiction implies ¬(d(3, 2) ≤ 2), and linear arithmetic concludes d(3, 2) = 3.

    lines 55–66

    uses five_vertex_t_star_dist_eq_walk_length_le_two

      have d32 : five_vertex_t_star.dist 3 2 = 3 := by
        have hle : five_vertex_t_star.dist 3 2 ≤ 3 := by
          have := hconn.dist_triangle (u := 3) (v := 0) (w := 2)
          omega
        have hgt : ¬ (five_vertex_t_star.dist 3 2 ≤ 2) := by
          intro hle2
          obtain ⟨p, hp⟩ := hconn.exists_walk_length_eq_dist 3 2
          have hp2 : p.length ≤ 2 := by omega
          have hcases := five_vertex_t_star_dist_eq_walk_length_le_two p hp2
          revert hcases
          decide
        omega
  7. The distance d(4, 2) equals 3.

    Similarly, the triangle inequality through vertex 0 gives d(4, 2) ≤ d(4, 0) + d(0, 2) = 1 + 2 = 3. To show d(4, 2) > 2, assume for contradiction d(4, 2) ≤ 2. A shortest walk from 4 to 2 has length at most 2, which by the characterization lemma would mean 4 = 2, adjacency of 4 and 2, or a common neighbor. An exhaustive evaluation (`decide`) across all five vertices confirms none of these hold, since 4's only neighbor is 0 and 0 is not adjacent to 2. Hence d(4, 2) = 3.

    lines 67–78

    uses five_vertex_t_star_dist_eq_walk_length_le_two

      have d42 : five_vertex_t_star.dist 4 2 = 3 := by
        have hle : five_vertex_t_star.dist 4 2 ≤ 3 := by
          have := hconn.dist_triangle (u := 4) (v := 0) (w := 2)
          omega
        have hgt : ¬ (five_vertex_t_star.dist 4 2 ≤ 2) := by
          intro hle2
          obtain ⟨p, hp⟩ := hconn.exists_walk_length_eq_dist 4 2
          have hp2 : p.length ≤ 2 := by omega
          have hcases := five_vertex_t_star_dist_eq_walk_length_le_two p hp2
          revert hcases
          decide
        omega
  8. All six distance equations hold simultaneously.

    We assemble the six verified distances—d(0,1) = 1, d(0,2) = 2, d(3,1) = 2, d(4,1) = 2, d(3,2) = 3, and d(4,2) = 3—into the target conjunction.

    line 79

      exact ⟨d01, d02, d31, d41, d32, d42⟩
Or.inl
From a proof of the left disjunct, infer the disjunction.
Or.inr
From a proof of the right disjunct, infer the disjunction.
SimpleGraph.Walk.length_cons
The length of a walk formed by prepending an edge to a walk is the tail walk's length plus one.
SimpleGraph.dist_eq_one_iff_adj
The graph distance between two vertices is 1 if and only if they are adjacent.
SimpleGraph.dist_comm
Graph distance is symmetric: d(u, v) = d(v, u).
five_vertex_t_star_dist_eq_walk_length_le_two
Any walk of length at most 2 connects identical vertices, adjacent vertices, or vertices with a common neighbor.

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

lemma five_vertex_t_star_dist_eq_walk_length_le_two {V : Type*} {G : SimpleGraph V}    {u v : V} (p : G.Walk u v) (hp : p.length ≤ 2) :    u = v ∨ G.Adj u v ∨ ∃ w, G.Adj u w ∧ G.Adj w v := by  cases p with  | nil => exact Or.inl rfl  | cons h1 q =>    cases q with    | nil => exact Or.inr (Or.inl h1)    | cons h2 r =>      cases r with      | nil => exact Or.inr (Or.inr ⟨_, h1, h2⟩)      | cons h3 s =>        simp only [SimpleGraph.Walk.length_cons] at hp        omega/-- The six distances in the T-graph that both Wasserstein bounds need. `dist 0 2 = 2` by the triangle inequality through 1 plus non-adjacency; `dist 3 2 = 3` is the only non-trivial one: upper bound by the triangle 3-0-1-2, lower bound because a walk of length at most 2 would give a common neighbour of 3 and 2, and 3's only neighbour is 0 which is not adjacent to 2. -/theorem five_vertex_t_star_dist_eq :    five_vertex_t_star.dist 0 1 = 1 ∧ five_vertex_t_star.dist 0 2 = 2 ∧      five_vertex_t_star.dist 3 1 = 2 ∧ five_vertex_t_star.dist 4 1 = 2 ∧      five_vertex_t_star.dist 3 2 = 3 ∧ five_vertex_t_star.dist 4 2 = 3 := by  have hconn : five_vertex_t_star.Connected := by decide  have d01 : five_vertex_t_star.dist 0 1 = 1 := by    rw [SimpleGraph.dist_eq_one_iff_adj]    decide  have d12 : five_vertex_t_star.dist 1 2 = 1 := by    rw [SimpleGraph.dist_eq_one_iff_adj]    decide  have d30 : five_vertex_t_star.dist 3 0 = 1 := by    rw [SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj]    decide  have d40 : five_vertex_t_star.dist 4 0 = 1 := by    rw [SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj]    decide  have d02 : five_vertex_t_star.dist 0 2 = 2 := by    have hle : five_vertex_t_star.dist 0 2 ≤ 2 := by      have := hconn.dist_triangle (u := 0) (v := 1) (w := 2)      omega    have hlt : 1 < five_vertex_t_star.dist 0 2 :=      hconn.one_lt_dist_of_ne_of_not_adj (by decide) (by decide)    omega  have d31 : five_vertex_t_star.dist 3 1 = 2 := by    have hle : five_vertex_t_star.dist 3 1 ≤ 2 := by      have := hconn.dist_triangle (u := 3) (v := 0) (w := 1)      omega    have hlt : 1 < five_vertex_t_star.dist 3 1 :=      hconn.one_lt_dist_of_ne_of_not_adj (by decide) (by decide)    omega  have d41 : five_vertex_t_star.dist 4 1 = 2 := by    have hle : five_vertex_t_star.dist 4 1 ≤ 2 := by      have := hconn.dist_triangle (u := 4) (v := 0) (w := 1)      omega    have hlt : 1 < five_vertex_t_star.dist 4 1 :=      hconn.one_lt_dist_of_ne_of_not_adj (by decide) (by decide)    omega  have d32 : five_vertex_t_star.dist 3 2 = 3 := by    have hle : five_vertex_t_star.dist 3 2 ≤ 3 := by      have := hconn.dist_triangle (u := 3) (v := 0) (w := 2)      omega    have hgt : ¬ (five_vertex_t_star.dist 3 2 ≤ 2) := by      intro hle2      obtain ⟨p, hp⟩ := hconn.exists_walk_length_eq_dist 3 2      have hp2 : p.length ≤ 2 := by omega      have hcases := five_vertex_t_star_dist_eq_walk_length_le_two p hp2      revert hcases      decide    omega  have d42 : five_vertex_t_star.dist 4 2 = 3 := by    have hle : five_vertex_t_star.dist 4 2 ≤ 3 := by      have := hconn.dist_triangle (u := 4) (v := 0) (w := 2)      omega    have hgt : ¬ (five_vertex_t_star.dist 4 2 ≤ 2) := by      intro hle2      obtain ⟨p, hp⟩ := hconn.exists_walk_length_eq_dist 4 2      have hp2 : p.length ≤ 2 := by omega      have hcases := five_vertex_t_star_dist_eq_walk_length_le_two p hp2      revert hcases      decide    omega  exact ⟨d01, d02, d31, d41, d32, d42⟩
See it in the graphDiscuss this resultChallenge it