import Mathlib /-! # Graph Valid Tree You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i in the graph. Return true if the edges of the given graph make up a valid tree, and false otherwise. ## Constraints - 1 <= n <= 2000 - 0 <= edges.length <= 5000 - edges[i].length == 2 - 0 <= a_i, b_i < n - a_i != b_i - There are no self-loops or repeated edges. ## Provided examples - `n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]` → `true` - `n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]` → `false` - `n = 1, edges = []` → `true` ## Synthesized negative examples - invalid input: `n = 0, edges = []` ([structural] a predicate that admits 1 <= n <= 2000. below the stated minimum) - invalid input: `n = 2, edges = [[0]]` ([structural] a predicate that admits edges[i].length == 2. edge missing its second endpoint) - invalid input: `n = 2, edges = [[2, 1]]` ([structural] a predicate that admits 0 <= ai, bi < n. ai is n; legal for a larger n, not for this graph) - `n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]` → `false` is wrong ([structural] edge-count condition checks n edges instead of n-1. connected acyclic graph has 4 edges, not 5) - `n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]` → `true` is wrong ([structural] only connectivity is checked; acyclicity is dropped. graph is connected but has a cycle) - `n = 1, edges = []` → `false` is wrong ([structural] tree edge count stated as n rather than n-1. single-node tree has 0 edges, so n-edge test fails) -/ namespace PGraphValidTree abbrev Input := (Nat) × (List (List Nat)) abbrev Output := Bool /-! ### Specification helpers -/ /-- Bridge from the serialized edge literal to the input's edge-list type. -/ def edgesFromPairLists (es : List (List Nat)) : List (List Nat) := es /-- The simple graph on vertices `0, …, n-1` with `a` adjacent to `b` when `[a, b]` or `[b, a]` is listed in `edges`. -/ def edgeGraph (n : Nat) (edges : List (List Nat)) : SimpleGraph (Fin n) where Adj a b := a ≠ b ∧ ∃ e ∈ edges, e = [a.val, b.val] ∨ e = [b.val, a.val] symm := by constructor intro a b h obtain ⟨hne, e, he, h⟩ := h exact ⟨hne.symm, e, he, h.symm⟩ loopless := by constructor intro a h exact h.1 rfl /-- Some path joins every two vertices of the edge graph on `n` vertices. -/ def IsConnectedGraph (n : Nat) (edges : List (List Nat)) : Prop := (edgeGraph n edges).Connected /-- The edge graph on `n` vertices has no cycle. -/ def IsAcyclicGraph (n : Nat) (edges : List (List Nat)) : Prop := (edgeGraph n edges).IsAcyclic /-- The unordered vertex pair an edge denotes, or `none` when it is malformed. -/ def edgePair (e : List Nat) : Option (Nat × Nat) := match e with | [a, b] => some (min a b, max a b) | _ => none /-! ### Validity predicate (V) -/ /-- Valid input: `1 ≤ n ≤ 2000`, at most 5000 edges, each a pair of distinct vertices below `n`, and no undirected edge repeated. -/ def isValidInput (input : Input) : Bool := let n := input.1 let edges := input.2 1 ≤ n && n ≤ 2000 && edges.length ≤ 5000 && edges.all (fun e => match e with | [a, b] => a < n && b < n && a != b | _ => false) && (edges.filterMap edgePair).Nodup /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when the edge graph is both connected and acyclic. -/ def validTree_spec (input : Input) (result : Output) : Prop := result ↔ (IsConnectedGraph input.1 input.2 ∧ IsAcyclicGraph input.1 input.2) /-! ### Decidable specification (P_check) -/ /-- The vertices of `visited` plus every endpoint sharing an edge of `edges` with one of them. -/ def expandOnce (edges : List (List Nat)) (visited : List Nat) : List Nat := (visited ++ edges.filterMap (fun e => match e with | [a, b] => if visited.contains a then some b else if visited.contains b then some a else none | _ => none)).dedup /-- The vertices reachable from `visited` within `fuel` rounds of one-edge expansion. -/ def expandN : Nat → List (List Nat) → List Nat → List Nat | 0, _, visited => visited | k + 1, edges, visited => expandN k edges (expandOnce edges visited) /-- Vertex `0` reaches every vertex below `n` within `n` expansion rounds, and a vertex exists. -/ def connectedDec (n : Nat) (edges : List (List Nat)) : Bool := let reached := expandN n edges [0] n != 0 && (List.range n).all (fun v => reached.contains v) /-- Executable checker for `validTree_spec`: connected, and acyclic via the `n - 1` edge count. -/ def validTree_check (input : Input) (result : Output) : Bool := let n := input.1 let edges := input.2 result == (connectedDec n edges && edges.length == n - 1) theorem gv_check_eq (input : Input) (result : Output) : validTree_check input result = (result == (connectedDec input.1 input.2 && input.2.length == input.1 - 1)) := rfl theorem gv_valid (input : Input) (h : isValidInput input = true) : 1 ≤ input.1 ∧ (∀ e ∈ input.2, ∃ a b, e = [a, b] ∧ a < input.1 ∧ b < input.1 ∧ a ≠ b) ∧ (input.2.filterMap edgePair).Nodup := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true] at h obtain ⟨⟨⟨⟨hn, -⟩, -⟩, hall⟩, hnd⟩ := h refine ⟨hn, ?_, hnd⟩ intro e he have hm := hall e he rcases e with _ | ⟨a, _ | ⟨b, _ | ⟨c, t⟩⟩⟩ · simp at hm · simp at hm · simp at hm refine ⟨a, b, rfl, ?_, ?_, ?_⟩ <;> omega · simp at hm theorem gv_adj_of_edge (n : Nat) (edges : List (List Nat)) (a b : Nat) (ha : a < n) (hb : b < n) (hab : a ≠ b) (he : [a, b] ∈ edges ∨ [b, a] ∈ edges) : (edgeGraph n edges).Adj ⟨a, ha⟩ ⟨b, hb⟩ := by show (⟨a, ha⟩ : Fin n) ≠ ⟨b, hb⟩ ∧ ∃ e ∈ edges, e = [a, b] ∨ e = [b, a] refine ⟨fun h => hab (congrArg Fin.val h), ?_⟩ rcases he with he | he · exact ⟨[a, b], he, Or.inl rfl⟩ · exact ⟨[b, a], he, Or.inr rfl⟩ theorem gv_expandN_succ' : ∀ (k : Nat) (edges : List (List Nat)) (vis : List Nat), expandN (k + 1) edges vis = expandOnce edges (expandN k edges vis) := by intro k induction k with | zero => intro edges vis; rfl | succ k ih => intro edges vis show expandN (k + 1) edges (expandOnce edges vis) = _ rw [ih] rfl theorem gv_mem_expandOnce_of_mem (edges : List (List Nat)) (vis : List Nat) (x : Nat) (hx : x ∈ vis) : x ∈ expandOnce edges vis := by unfold expandOnce rw [List.mem_dedup] exact List.mem_append_left _ hx theorem gv_mem_expandOnce_of_edge (edges : List (List Nat)) (vis : List Nat) (u v : Nat) (hu : u ∈ vis) (he : [u, v] ∈ edges ∨ [v, u] ∈ edges) : v ∈ expandOnce edges vis := by unfold expandOnce rw [List.mem_dedup, List.mem_append, List.mem_filterMap] rcases he with he | he · right exact ⟨[u, v], he, by simp [List.contains_iff_mem, hu]⟩ · by_cases hv : v ∈ vis · left exact hv · right exact ⟨[v, u], he, by simp [List.contains_iff_mem, hu, hv]⟩ theorem gv_expandOnce_sound (edges : List (List Nat)) (vis : List Nat) (x : Nat) (hx : x ∈ expandOnce edges vis) : x ∈ vis ∨ ∃ u ∈ vis, [u, x] ∈ edges ∨ [x, u] ∈ edges := by unfold expandOnce at hx rw [List.mem_dedup, List.mem_append, List.mem_filterMap] at hx rcases hx with hx | ⟨e, he, hsome⟩ · exact Or.inl hx · right rcases e with _ | ⟨a, _ | ⟨b, _ | ⟨c, t⟩⟩⟩ · simp at hsome · simp at hsome · by_cases ha : a ∈ vis · have hbx : b = x := by simpa [List.contains_iff_mem, ha] using hsome subst hbx exact ⟨a, ha, Or.inl he⟩ · by_cases hb : b ∈ vis · have hax : a = x := by simpa [List.contains_iff_mem, ha, hb] using hsome subst hax exact ⟨b, hb, Or.inr he⟩ · simp [List.contains_iff_mem, ha, hb] at hsome · simp at hsome theorem gv_expandN_sound (n : Nat) (edges : List (List Nat)) (hn : 0 < n) (hwf : ∀ e ∈ edges, ∃ a b, e = [a, b] ∧ a < n ∧ b < n ∧ a ≠ b) : ∀ (k : Nat) (vis : List Nat), (∀ x ∈ vis, ∃ hx : x < n, (edgeGraph n edges).Reachable ⟨0, hn⟩ ⟨x, hx⟩) → ∀ x ∈ expandN k edges vis, ∃ hx : x < n, (edgeGraph n edges).Reachable ⟨0, hn⟩ ⟨x, hx⟩ := by intro k induction k with | zero => intro vis hvis; exact hvis | succ k ih => intro vis hvis show ∀ x ∈ expandN k edges (expandOnce edges vis), _ apply ih (expandOnce edges vis) intro x hx rcases gv_expandOnce_sound edges vis x hx with hx | ⟨u, hu, he⟩ · exact hvis x hx · obtain ⟨hu', hr⟩ := hvis u hu rcases he with he | he · obtain ⟨a, b, heq, ha, hb, hab⟩ := hwf _ he simp only [List.cons.injEq, and_true] at heq obtain ⟨rfl, rfl⟩ := heq exact ⟨hb, hr.trans ⟨SimpleGraph.Walk.cons (gv_adj_of_edge n edges _ _ hu' hb hab (Or.inl he)) SimpleGraph.Walk.nil⟩⟩ · obtain ⟨a, b, heq, ha, hb, hab⟩ := hwf _ he simp only [List.cons.injEq, and_true] at heq obtain ⟨rfl, rfl⟩ := heq exact ⟨ha, hr.trans ⟨SimpleGraph.Walk.cons (gv_adj_of_edge n edges _ _ hu' ha (Ne.symm hab) (Or.inr he)) SimpleGraph.Walk.nil⟩⟩ theorem gv_walk_mem (n : Nat) (edges : List (List Nat)) : ∀ {u v : Fin n} (p : (edgeGraph n edges).Walk u v) (vis : List Nat), u.val ∈ vis → v.val ∈ expandN p.length edges vis := by intro u v p induction p with | nil => intro vis hu; exact hu | cons hadj p ih => intro vis hu rw [SimpleGraph.Walk.length_cons] show _ ∈ expandN p.length edges (expandOnce edges vis) apply ih (expandOnce edges vis) obtain ⟨_, e, he, hor⟩ := hadj rcases hor with rfl | rfl · exact gv_mem_expandOnce_of_edge edges vis _ _ hu (Or.inl he) · exact gv_mem_expandOnce_of_edge edges vis _ _ hu (Or.inr he) theorem gv_expandN_mono (edges : List (List Nat)) (vis : List Nat) (x : Nat) : ∀ (k d : Nat), x ∈ expandN k edges vis → x ∈ expandN (k + d) edges vis := by intro k d induction d with | zero => intro hx; exact hx | succ d ih => intro hx rw [← Nat.add_assoc, gv_expandN_succ'] exact gv_mem_expandOnce_of_mem _ _ _ (ih hx) theorem gv_connected_iff (n : Nat) (edges : List (List Nat)) (hn : 1 ≤ n) (hwf : ∀ e ∈ edges, ∃ a b, e = [a, b] ∧ a < n ∧ b < n ∧ a ≠ b) : connectedDec n edges = true ↔ (edgeGraph n edges).Connected := by have hn' : 0 < n := hn have hdec : connectedDec n edges = (n != 0 && (List.range n).all (fun v => (expandN n edges [0]).contains v)) := rfl rw [hdec, Bool.and_eq_true, List.all_eq_true, SimpleGraph.connected_iff] constructor · rintro ⟨-, hall⟩ have hsound := gv_expandN_sound n edges hn' hwf n [0] (by intro x hx rw [List.mem_singleton] at hx subst hx exact ⟨hn', ⟨SimpleGraph.Walk.nil⟩⟩) have hreach : ∀ v : Fin n, (edgeGraph n edges).Reachable ⟨0, hn'⟩ v := by intro v have hv := hall v.val (List.mem_range.mpr v.isLt) rw [List.contains_iff_mem] at hv obtain ⟨_, hr⟩ := hsound v.val hv exact hr exact ⟨fun u v => (hreach u).symm.trans (hreach v), ⟨⟨0, hn'⟩⟩⟩ · rintro ⟨hpre, -⟩ refine ⟨?_, ?_⟩ · simp omega · intro v hv rw [List.mem_range] at hv rw [List.contains_iff_mem] obtain ⟨p⟩ := hpre ⟨0, hn'⟩ ⟨v, hv⟩ have hlen : p.bypass.length < n := by have := (SimpleGraph.Walk.bypass_isPath p).length_lt simpa using this have hmem := gv_walk_mem n edges p.bypass [0] (by simp) have hfin := gv_expandN_mono edges [0] v p.bypass.length (n - p.bypass.length) hmem rwa [Nat.add_sub_of_le hlen.le] at hfin def gvSym : List Nat → Sym2 Nat | [a, b] => s(a, b) | _ => s(0, 0) def gvMinMax : Sym2 Nat → Nat × Nat := Sym2.lift ⟨fun a b => (min a b, max a b), fun a b => Prod.ext (min_comm a b) (max_comm a b)⟩ theorem gv_filterMap_eq (n : Nat) : ∀ l : List (List Nat), (∀ e ∈ l, ∃ a b, e = [a, b] ∧ a < n ∧ b < n ∧ a ≠ b) → l.filterMap edgePair = (l.map gvSym).map gvMinMax := by intro l induction l with | nil => intro _; rfl | cons e l ih => intro hl have ih' := ih (fun e' he' => hl e' (by simp [he'])) obtain ⟨a, b, rfl, -, -, -⟩ := hl e (by simp) have h1 : edgePair [a, b] = some (min a b, max a b) := rfl have h2 : gvMinMax (gvSym [a, b]) = (min a b, max a b) := by simp [gvMinMax, gvSym, Sym2.lift_mk] rw [List.filterMap_cons, h1, ih', List.map_cons, List.map_cons, h2] theorem gv_card_edgeSet (n : Nat) (edges : List (List Nat)) (hwf : ∀ e ∈ edges, ∃ a b, e = [a, b] ∧ a < n ∧ b < n ∧ a ≠ b) (hnd : (edges.filterMap edgePair).Nodup) : Nat.card (edgeGraph n edges).edgeSet = edges.length := by classical have himg : Sym2.map Fin.val '' (edgeGraph n edges).edgeSet = ↑(edges.map gvSym).toFinset := by ext z rw [Finset.mem_coe, List.mem_toFinset, List.mem_map, Set.mem_image] constructor · rintro ⟨x, hx, rfl⟩ induction x using Sym2.ind with | h i j => rw [SimpleGraph.mem_edgeSet] at hx obtain ⟨_, e, he, hor⟩ := hx refine ⟨e, he, ?_⟩ rcases hor with rfl | rfl · simp [gvSym] · simp [gvSym, Sym2.eq_swap] · rintro ⟨e, he, rfl⟩ obtain ⟨a, b, rfl, ha, hb, hab⟩ := hwf e he refine ⟨s(⟨a, ha⟩, ⟨b, hb⟩), ?_, ?_⟩ · rw [SimpleGraph.mem_edgeSet] exact gv_adj_of_edge n edges a b ha hb hab (Or.inl he) · simp [gvSym] have hnodup : (edges.map gvSym).Nodup := by rw [gv_filterMap_eq n edges hwf] at hnd exact List.Nodup.of_map gvMinMax hnd rw [Nat.card_coe_set_eq, ← Set.ncard_image_of_injective _ (Sym2.map.injective Fin.val_injective), himg, Set.ncard_coe_finset, List.toFinset_card_of_nodup hnodup, List.length_map] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem validTree_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : validTree_check input result ↔ validTree_spec input result := by obtain ⟨hn, hwf, hnd⟩ := gv_valid input h rw [gv_check_eq, validTree_spec, IsConnectedGraph, IsAcyclicGraph, beq_iff_eq, Bool.eq_iff_iff] refine iff_congr Iff.rfl ?_ rw [Bool.and_eq_true, beq_iff_eq, gv_connected_iff input.1 input.2 hn hwf] have hcard := gv_card_edgeSet input.1 input.2 hwf hnd have htree : (edgeGraph input.1 input.2).IsTree ↔ _ := SimpleGraph.isTree_iff_connected_and_card rw [hcard, Nat.card_fin] at htree constructor · rintro ⟨hc, hl⟩ exact ⟨hc, (htree.mpr ⟨hc, by omega⟩).isAcyclic⟩ · rintro ⟨hc, ha⟩ have hlen := (htree.mp ⟨hc, ha⟩).2 exact ⟨hc, by omega⟩ /-! ### Implementation helpers -/ /-- Neighbor list of every vertex: each edge literal is decoded by `edgePair` and recorded at both endpoints. -/ def buildAdjacency (n : Nat) (edges : List (List Nat)) : Array (List Nat) := edges.foldl (fun adj e => match edgePair e with | some (a, b) => if a < n && b < n then if ha : a < adj.size then let withB := adj.set a (b :: adj.getD a []) ha if hb : b < withB.size then withB.set b (a :: withB.getD b []) hb else withB else adj else adj | none => adj) (List.replicate n ([] : List Nat)).toArray /-- The vertices left unvisited after depth-first search from `frontier`, erasing each reached vertex from `unvisited`. -/ def exploreFrom (adj : Array (List Nat)) : List Nat → List Nat → List Nat | [], unvisited => unvisited | v :: rest, unvisited => if h : v ∈ unvisited then exploreFrom adj (rest ++ ((adj.getD v []).filter (· ∈ unvisited.erase v))) (unvisited.erase v) else exploreFrom adj rest unvisited termination_by frontier unvisited => (unvisited.length, frontier.length) decreasing_by · simp_wf have hlen := List.length_erase_of_mem h have hpos : 0 < unvisited.length := by cases unvisited with | nil => simp at h | cons => simp first | (apply Prod.Lex.left; change _ < _; omega) | (left; omega) · simp_wf apply Prod.Lex.right change rest.length < (v :: rest).length simp /-- True when depth-first search from vertex `0` over the adjacency lists reaches every vertex below `n`. -/ def isConnectedFast (n : Nat) (adj : Array (List Nat)) : Bool := if n = 0 then false else exploreFrom adj [0] (List.range n) == [] /-! ### Main algorithm (impl) -/ /-- A tree test: exactly `n - 1` edges, and DFS from vertex `0` over the adjacency lists reaches all `n` vertices. -/ def isValidTree (input : Input) : Output := let n := input.1 let edges := input.2 edges.length == n - 1 && isConnectedFast n (buildAdjacency n edges) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem isValidTree_correct (input : Input) (h : isValidInput input) : validTree_spec input (isValidTree input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (5, [[0, 1], [0, 2], [0, 3], [1, 4]]) #guard isValidInput (5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]) #guard isValidInput (1, []) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (0, [])) #guard !(isValidInput (2, [[0]])) #guard !(isValidInput (2, [[2, 1]])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard validTree_check (5, (edgesFromPairLists [[0, 1], [0, 2], [0, 3], [1, 4]])) true #guard validTree_check (5, (edgesFromPairLists [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]])) false #guard validTree_check (1, (edgesFromPairLists [])) true /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(validTree_check (5, (edgesFromPairLists [[0, 1], [0, 2], [0, 3], [1, 4]])) false) #guard !(validTree_check (5, (edgesFromPairLists [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]])) true) #guard !(validTree_check (1, (edgesFromPairLists [])) false) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard isValidTree (5, edgesFromPairLists [[0, 1], [0, 2], [0, 3], [1, 4]]) == true #guard isValidTree (5, edgesFromPairLists [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]) == false #guard isValidTree (1, edgesFromPairLists []) == true /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard validTree_check (5, edgesFromPairLists [[0, 1], [0, 2], [0, 3], [1, 4]]) (isValidTree (5, edgesFromPairLists [[0, 1], [0, 2], [0, 3], [1, 4]])) #guard validTree_check (5, edgesFromPairLists [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]) (isValidTree (5, edgesFromPairLists [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]])) #guard validTree_check (1, edgesFromPairLists []) (isValidTree (1, edgesFromPairLists [])) end PGraphValidTree