forest_carpool_append_edge_disconnected
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
- forest_carpool_disjoint_components_independentIf appending the edge u-v to the given prefix yields a forest, then under uniformly random prefix coins the two endpoint final…
- forest_carpool_final_one_sided_fibonacci_tailFor any forest arrival sequence and any vertex, the finite uniform probability that its final greedy discrepancy is at least D is bounded…
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.
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.
obtain ⟨hval, hnd, hac⟩ := hf have huv : u ≠ v := hval (u, v) (by simp)
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).
uses
List.map_append,List.nodup_append,List.mem_map.mprhave 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
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.
uses
SimpleGraph.mem_edgeSet,SimpleGraph.fromEdgeSet_adjset 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⟩
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.
uses
SimpleGraph.isAcyclic_iff_forall_isBridge.mp,SimpleGraph.isBridge_iffhave hb := (SimpleGraph.isAcyclic_iff_forall_isBridge.mp hac) hedge rw [SimpleGraph.isBridge_iff] at hb
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.
intro hr apply hb refine hr.mono ?_
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.
uses
SimpleGraph.fromEdgeSet_adj,SimpleGraph.deleteEdges_adj,List.mem_append_left,Set.mem_singleton_iffintro 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
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.
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