AFTD Auto-Formalizing Theoretical Domains

forest_carpool_append_edge_disconnected

theoremverified

When a new edge appended to an edge sequence still forms a forest with no duplicate undirected edges, its endpoints lie in distinct components of the preceding graph.

Statement

theorem forest_carpool_append_edge_disconnected (n : ℕ)
    (edges : List (Fin n × Fin n)) (u v : Fin n)
    (hf : CarpoolForestEdgeSequence n (edges ++ [(u, v)])) :
  ¬ (SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ edges}).Reachable u v
Source
Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • CarpoolForestEdgeSequenceA list of edges on Fin n is an oblivious forest edge sequence for online carpooling if all edges connect distinct vertices, no undirected…
  • ValidCarpoolEdgeSequenceA list of edges on n vertices is valid for online carpooling if every arriving edge connects two distinct vertices.
Used by 2

The proof, explained

The proof proceeds by contradiction. If u and v were reachable in the graph formed by edges, they would also be reachable in the extended graph H after removing the newly appended edge {u, v}, because no previous edge duplicates {u, v}. However, the extended graph H is acyclic (a forest), so every edge in H is a bridge; in particular, removing {u, v} must disconnect u and v. This contradiction shows that u and v could not have been reachable in the original graph.

  1. The endpoints u and v are distinct.

    The sequence hypothesis implies that every edge in the extended list is valid, which means it cannot be a self-loop. Since (u, v) is in the extended list, u ≠ v.

    lines 5–6

      obtain ⟨hval, hnd, hac⟩ := hf
      have huv : u ≠ v := hval (u, v) (by simp)
  2. No edge in the preceding list edges has the same undirected endpoints as {u, v}.

    The hypothesis that the extended edge list has no duplicate undirected edges is expanded across list concatenation using List.map_append and List.nodup_append. This implies that no edge from edges can map to the undirected edge s(u, v).

    lines 7–10

    uses List.map_append, List.nodup_append, List.mem_map.mpr

      have hnot : ∀ e ∈ edges, s(e.1, e.2) ≠ s(u, v) := by
        intro e he heq
        rw [List.map_append, List.nodup_append] at hnd
        exact hnd.2.2 _ (List.mem_map.mpr ⟨e, he, rfl⟩) _ (by simp) heq
  3. In the extended graph H, s(u, v) is an edge.

    Let H be the graph formed by all edges in edges ++ [(u, v)]. Because (u, v) appears in this list and u ≠ v, SimpleGraph.mem_edgeSet and SimpleGraph.fromEdgeSet_adj confirm that s(u, v) is an edge of H.

    lines 11–14

    uses SimpleGraph.mem_edgeSet, SimpleGraph.fromEdgeSet_adj

      set H := SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ edges ++ [(u, v)]}
      have hedge : s(u, v) ∈ H.edgeSet := by
        rw [SimpleGraph.mem_edgeSet, SimpleGraph.fromEdgeSet_adj]
        exact ⟨⟨(u, v), by simp, rfl⟩, huv⟩
  4. The edge s(u, v) is a bridge in H, meaning u and v are disconnected in H with s(u, v) deleted.

    Since H is acyclic, every edge in H is a bridge by SimpleGraph.isAcyclic_iff_forall_isBridge.mp. By the characterization of bridges (SimpleGraph.isBridge_iff), removing s(u, v) from H leaves u and v unreachable from one another.

    lines 15–16

    uses SimpleGraph.isAcyclic_iff_forall_isBridge.mp, SimpleGraph.isBridge_iff

      have hb := (SimpleGraph.isAcyclic_iff_forall_isBridge.mp hac) hedge
      rw [SimpleGraph.isBridge_iff] at hb
  5. To obtain a contradiction, it suffices to show that the graph of edges is a subgraph of H with s(u, v) removed.

    Assume for contradiction that u and v are reachable in the graph formed by edges. Because reachability is monotonic with respect to graph inclusion, if every edge of edges is also present in H after deleting s(u, v), then u and v would remain reachable in H with s(u, v) deleted, contradicting that s(u, v) is a bridge.

    lines 17–19

      intro hr
      apply hb
      refine hr.mono ?_
  6. Every edge in the graph of edges is indeed an edge of H with s(u, v) removed, completing the proof.

    Take any adjacent vertices x and y in the graph of edges, corresponding to an edge e in edges with x ≠ y. Since e is in edges, it is also in edges ++ [(u, v)] by List.mem_append_left, so {x, y} is an edge in H. Furthermore, since no edge in edges matches {u, v}, the edge {x, y} is not equal to {u, v} (via Set.mem_singleton_iff). By SimpleGraph.deleteEdges_adj, {x, y} remains an edge in H with s(u, v) deleted.

    lines 20–27

    uses SimpleGraph.fromEdgeSet_adj, SimpleGraph.deleteEdges_adj, List.mem_append_left, Set.mem_singleton_iff

      intro x y hxy
      rw [SimpleGraph.fromEdgeSet_adj] at hxy
      obtain ⟨⟨e, he, hex⟩, hne⟩ := hxy
      rw [SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj]
      refine ⟨⟨⟨e, List.mem_append_left _ he, hex⟩, hne⟩, ?_⟩
      simp only [Set.mem_singleton_iff]
      rw [← hex]
      exact hnot e he
List.map_append
Mapping a function across the concatenation of two lists is the concatenation of the mapped lists.
List.nodup_append
The concatenation of two lists has no duplicate elements if and only if each list has no duplicates and they share no common elements.
List.mem_map.mpr
An element y is in the image of a list under f if there exists an element x in the list with f(x) = y.
SimpleGraph.mem_edgeSet
An undirected edge s(v, w) belongs to the edge set of a simple graph if and only if v and w are adjacent.
SimpleGraph.fromEdgeSet_adj
Vertices v and w are adjacent in the graph generated from an edge set s if and only if s(v, w) ∈ s and v ≠ w.
SimpleGraph.isAcyclic_iff_forall_isBridge.mp
In an acyclic graph (a forest), every edge in the edge set is a bridge.
SimpleGraph.isBridge_iff
An edge s(u, v) is a bridge if and only if u and v are not reachable from each other after removing that edge.
SimpleGraph.deleteEdges_adj
Vertices v and w are adjacent in a graph with edges deleted if and only if they were adjacent in the original graph and their edge was not in the deleted set.
List.mem_append_left
If an element belongs to a list, it also belongs to that list concatenated with another list.
Set.mem_singleton_iff
An element belongs to a singleton set {b} if and only if it equals b.

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 forest_carpool_append_edge_disconnected (n : ℕ)    (edges : List (Fin n × Fin n)) (u v : Fin n)    (hf : CarpoolForestEdgeSequence n (edges ++ [(u, v)])) :  ¬ (SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ edges}).Reachable u v := by  obtain ⟨hval, hnd, hac⟩ := hf  have huv : u ≠ v := hval (u, v) (by simp)  have hnot : ∀ e ∈ edges, s(e.1, e.2) ≠ s(u, v) := by    intro e he heq    rw [List.map_append, List.nodup_append] at hnd    exact hnd.2.2 _ (List.mem_map.mpr ⟨e, he, rfl⟩) _ (by simp) heq  set H := SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ edges ++ [(u, v)]}  have hedge : s(u, v) ∈ H.edgeSet := by    rw [SimpleGraph.mem_edgeSet, SimpleGraph.fromEdgeSet_adj]    exact ⟨⟨(u, v), by simp, rfl⟩, huv⟩  have hb := (SimpleGraph.isAcyclic_iff_forall_isBridge.mp hac) hedge  rw [SimpleGraph.isBridge_iff] at hb  intro hr  apply hb  refine hr.mono ?_  intro x y hxy  rw [SimpleGraph.fromEdgeSet_adj] at hxy  obtain ⟨⟨e, he, hex⟩, hne⟩ := hxy  rw [SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj]  refine ⟨⟨⟨e, List.mem_append_left _ he, hex⟩, hne⟩, ?_⟩  simp only [Set.mem_singleton_iff]  rw [← hex]  exact hnot e he
See it in the graphDiscuss this resultChallenge it