combinatorics.simple_graph.acyclic | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

b0768801

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

832f7b91

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -99,23 +99,23 @@ theorem IsAcyclic.path_unique {G : SimpleGraph V} (h : G.IsAcyclic) {v w : V} (p
   obtain ⟨q, hq⟩ := q
   simp only
   induction' p with u pu pv pw ph p ih generalizing q
-  · rw [walk.is_path_iff_eq_nil] at hq 
+  · rw [walk.is_path_iff_eq_nil] at hq
     exact hq.symm
-  · rw [is_acyclic_iff_forall_adj_is_bridge] at h 
+  · rw [is_acyclic_iff_forall_adj_is_bridge] at h
     specialize h ph
-    rw [is_bridge_iff_adj_and_forall_walk_mem_edges] at h 
+    rw [is_bridge_iff_adj_and_forall_walk_mem_edges] at h
     replace h := h.2 (q.append p.reverse)
-    simp only [walk.edges_append, walk.edges_reverse, List.mem_append, List.mem_reverse] at h 
+    simp only [walk.edges_append, walk.edges_reverse, List.mem_append, List.mem_reverse] at h
     cases h
     · cases q
       · simpa [walk.is_path_def] using hp
-      · rw [walk.cons_is_path_iff] at hp hq 
-        simp only [walk.edges_cons, List.mem_cons, Sym2.eq_iff] at h 
+      · rw [walk.cons_is_path_iff] at hp hq
+        simp only [walk.edges_cons, List.mem_cons, Sym2.eq_iff] at h
         obtain (⟨h, rfl⟩ | ⟨rfl, rfl⟩) | h := h
         · rw [ih hp.1 _ hq.1]
         · simpa using hq
         · exact absurd (walk.fst_mem_support_of_mem_edges _ h) hq.2
-    · rw [walk.cons_is_path_iff] at hp 
+    · rw [walk.cons_is_path_iff] at hp
       exact absurd (walk.fst_mem_support_of_mem_edges _ h) hp.2
 #align simple_graph.is_acyclic.path_unique SimpleGraph.IsAcyclic.path_unique
 -/
@@ -124,13 +124,13 @@ theorem IsAcyclic.path_unique {G : SimpleGraph V} (h : G.IsAcyclic) {v w : V} (p
 theorem isAcyclic_of_path_unique (h : ∀ (v w : V) (p q : G.Path v w), p = q) : G.IsAcyclic :=
   by
   intro v c hc
-  simp only [walk.is_cycle_def, Ne.def] at hc 
+  simp only [walk.is_cycle_def, Ne.def] at hc
   cases c
   · exact absurd rfl hc.2.1
   · simp only [walk.cons_is_trail_iff, not_false_iff, walk.support_cons, List.tail_cons,
-      true_and_iff] at hc 
+      true_and_iff] at hc
     specialize h _ _ ⟨c_p, by simp only [walk.is_path_def, hc.2]⟩ (path.singleton (G.symm c_h))
-    simp only [path.singleton] at h 
+    simp only [path.singleton] at h
     simpa [-Quotient.eq', Sym2.eq_swap, h] using hc
 #align simple_graph.is_acyclic_of_path_unique SimpleGraph.isAcyclic_of_path_unique
 -/

832f7b91

bump to nightly-2024-02-01-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

5433bded

Diff

@@ -143,7 +143,26 @@ theorem isAcyclic_iff_path_unique : G.IsAcyclic ↔ ∀ ⦃v w : V⦄ (p q : G.P
 
 #print SimpleGraph.isTree_iff_existsUnique_path /-
 theorem isTree_iff_existsUnique_path :
-    G.IsTree ↔ Nonempty V ∧ ∀ v w : V, ∃! p : G.Walk v w, p.IsPath := by classical
+    G.IsTree ↔ Nonempty V ∧ ∀ v w : V, ∃! p : G.Walk v w, p.IsPath := by
+  classical
+  rw [is_tree_iff, is_acyclic_iff_path_unique]
+  constructor
+  · rintro ⟨hc, hu⟩
+    refine' ⟨hc.nonempty, _⟩
+    intro v w
+    let q := (hc v w).some.toPath
+    use q
+    simp only [true_and_iff, path.is_path]
+    intro p hp
+    specialize hu ⟨p, hp⟩ q
+    exact subtype.ext_iff.mp hu
+  · rintro ⟨hV, h⟩
+    refine' ⟨connected.mk _, _⟩
+    · intro v w
+      obtain ⟨p, hp⟩ := h v w
+      exact p.reachable
+    · rintro v w ⟨p, hp⟩ ⟨q, hq⟩
+      simp only [ExistsUnique.unique (h v w) hp hq]
 #align simple_graph.is_tree_iff_exists_unique_path SimpleGraph.isTree_iff_existsUnique_path
 -/

832f7b91

bump to nightly-2024-01-31-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

61100fe9

Diff

@@ -143,26 +143,7 @@ theorem isAcyclic_iff_path_unique : G.IsAcyclic ↔ ∀ ⦃v w : V⦄ (p q : G.P
 
 #print SimpleGraph.isTree_iff_existsUnique_path /-
 theorem isTree_iff_existsUnique_path :
-    G.IsTree ↔ Nonempty V ∧ ∀ v w : V, ∃! p : G.Walk v w, p.IsPath := by
-  classical
-  rw [is_tree_iff, is_acyclic_iff_path_unique]
-  constructor
-  · rintro ⟨hc, hu⟩
-    refine' ⟨hc.nonempty, _⟩
-    intro v w
-    let q := (hc v w).some.toPath
-    use q
-    simp only [true_and_iff, path.is_path]
-    intro p hp
-    specialize hu ⟨p, hp⟩ q
-    exact subtype.ext_iff.mp hu
-  · rintro ⟨hV, h⟩
-    refine' ⟨connected.mk _, _⟩
-    · intro v w
-      obtain ⟨p, hp⟩ := h v w
-      exact p.reachable
-    · rintro v w ⟨p, hp⟩ ⟨q, hq⟩
-      simp only [ExistsUnique.unique (h v w) hp hq]
+    G.IsTree ↔ Nonempty V ∧ ∀ v w : V, ∃! p : G.Walk v w, p.IsPath := by classical
 #align simple_graph.is_tree_iff_exists_unique_path SimpleGraph.isTree_iff_existsUnique_path
 -/

832f7b91

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2022 Kyle Miller. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kyle Miller
 -/
-import Mathbin.Combinatorics.SimpleGraph.Connectivity
+import Combinatorics.SimpleGraph.Connectivity
 
 #align_import combinatorics.simple_graph.acyclic from "leanprover-community/mathlib"@"832f7b9162039c28b9361289c8681f155cae758f"

832f7b91

bump to nightly-2023-08-02-01

mathlib commit https://github.com/leanprover-community/mathlib/commit/63721b2c3eba6c325ecf8ae8cca27155a4f6306f

7aca3f15

Diff

@@ -105,7 +105,7 @@ theorem IsAcyclic.path_unique {G : SimpleGraph V} (h : G.IsAcyclic) {v w : V} (p
     specialize h ph
     rw [is_bridge_iff_adj_and_forall_walk_mem_edges] at h 
     replace h := h.2 (q.append p.reverse)
-    simp only [walk.edges_append, walk.edges_reverse, List.mem_append, List.mem_reverse'] at h 
+    simp only [walk.edges_append, walk.edges_reverse, List.mem_append, List.mem_reverse] at h 
     cases h
     · cases q
       · simpa [walk.is_path_def] using hp

832f7b91

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,14 +2,11 @@
 Copyright (c) 2022 Kyle Miller. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kyle Miller
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.acyclic
-! leanprover-community/mathlib commit 832f7b9162039c28b9361289c8681f155cae758f
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Combinatorics.SimpleGraph.Connectivity
 
+#align_import combinatorics.simple_graph.acyclic from "leanprover-community/mathlib"@"832f7b9162039c28b9361289c8681f155cae758f"
+
 /-!
 
 # Acyclic graphs and trees

832f7b91

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -88,10 +88,12 @@ theorem isAcyclic_iff_forall_adj_isBridge :
 #align simple_graph.is_acyclic_iff_forall_adj_is_bridge SimpleGraph.isAcyclic_iff_forall_adj_isBridge
 -/
 
+#print SimpleGraph.isAcyclic_iff_forall_edge_isBridge /-
 theorem isAcyclic_iff_forall_edge_isBridge :
     G.IsAcyclic ↔ ∀ ⦃e⦄, e ∈ G.edgeSetEmbedding → G.IsBridge e := by
   simp [is_acyclic_iff_forall_adj_is_bridge, Sym2.forall]
 #align simple_graph.is_acyclic_iff_forall_edge_is_bridge SimpleGraph.isAcyclic_iff_forall_edge_isBridge
+-/
 
 #print SimpleGraph.IsAcyclic.path_unique /-
 theorem IsAcyclic.path_unique {G : SimpleGraph V} (h : G.IsAcyclic) {v w : V} (p q : G.Path v w) :

832f7b91

bump to nightly-2023-06-04-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

3fb4268b

Diff

@@ -146,24 +146,24 @@ theorem isAcyclic_iff_path_unique : G.IsAcyclic ↔ ∀ ⦃v w : V⦄ (p q : G.P
 theorem isTree_iff_existsUnique_path :
     G.IsTree ↔ Nonempty V ∧ ∀ v w : V, ∃! p : G.Walk v w, p.IsPath := by
   classical
-    rw [is_tree_iff, is_acyclic_iff_path_unique]
-    constructor
-    · rintro ⟨hc, hu⟩
-      refine' ⟨hc.nonempty, _⟩
-      intro v w
-      let q := (hc v w).some.toPath
-      use q
-      simp only [true_and_iff, path.is_path]
-      intro p hp
-      specialize hu ⟨p, hp⟩ q
-      exact subtype.ext_iff.mp hu
-    · rintro ⟨hV, h⟩
-      refine' ⟨connected.mk _, _⟩
-      · intro v w
-        obtain ⟨p, hp⟩ := h v w
-        exact p.reachable
-      · rintro v w ⟨p, hp⟩ ⟨q, hq⟩
-        simp only [ExistsUnique.unique (h v w) hp hq]
+  rw [is_tree_iff, is_acyclic_iff_path_unique]
+  constructor
+  · rintro ⟨hc, hu⟩
+    refine' ⟨hc.nonempty, _⟩
+    intro v w
+    let q := (hc v w).some.toPath
+    use q
+    simp only [true_and_iff, path.is_path]
+    intro p hp
+    specialize hu ⟨p, hp⟩ q
+    exact subtype.ext_iff.mp hu
+  · rintro ⟨hV, h⟩
+    refine' ⟨connected.mk _, _⟩
+    · intro v w
+      obtain ⟨p, hp⟩ := h v w
+      exact p.reachable
+    · rintro v w ⟨p, hp⟩ ⟨q, hq⟩
+      simp only [ExistsUnique.unique (h v w) hp hq]
 #align simple_graph.is_tree_iff_exists_unique_path SimpleGraph.isTree_iff_existsUnique_path
 -/

832f7b91

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -100,23 +100,23 @@ theorem IsAcyclic.path_unique {G : SimpleGraph V} (h : G.IsAcyclic) {v w : V} (p
   obtain ⟨q, hq⟩ := q
   simp only
   induction' p with u pu pv pw ph p ih generalizing q
-  · rw [walk.is_path_iff_eq_nil] at hq
+  · rw [walk.is_path_iff_eq_nil] at hq 
     exact hq.symm
-  · rw [is_acyclic_iff_forall_adj_is_bridge] at h
+  · rw [is_acyclic_iff_forall_adj_is_bridge] at h 
     specialize h ph
-    rw [is_bridge_iff_adj_and_forall_walk_mem_edges] at h
+    rw [is_bridge_iff_adj_and_forall_walk_mem_edges] at h 
     replace h := h.2 (q.append p.reverse)
-    simp only [walk.edges_append, walk.edges_reverse, List.mem_append, List.mem_reverse'] at h
+    simp only [walk.edges_append, walk.edges_reverse, List.mem_append, List.mem_reverse'] at h 
     cases h
     · cases q
       · simpa [walk.is_path_def] using hp
-      · rw [walk.cons_is_path_iff] at hp hq
-        simp only [walk.edges_cons, List.mem_cons, Sym2.eq_iff] at h
+      · rw [walk.cons_is_path_iff] at hp hq 
+        simp only [walk.edges_cons, List.mem_cons, Sym2.eq_iff] at h 
         obtain (⟨h, rfl⟩ | ⟨rfl, rfl⟩) | h := h
         · rw [ih hp.1 _ hq.1]
         · simpa using hq
         · exact absurd (walk.fst_mem_support_of_mem_edges _ h) hq.2
-    · rw [walk.cons_is_path_iff] at hp
+    · rw [walk.cons_is_path_iff] at hp 
       exact absurd (walk.fst_mem_support_of_mem_edges _ h) hp.2
 #align simple_graph.is_acyclic.path_unique SimpleGraph.IsAcyclic.path_unique
 -/
@@ -125,13 +125,13 @@ theorem IsAcyclic.path_unique {G : SimpleGraph V} (h : G.IsAcyclic) {v w : V} (p
 theorem isAcyclic_of_path_unique (h : ∀ (v w : V) (p q : G.Path v w), p = q) : G.IsAcyclic :=
   by
   intro v c hc
-  simp only [walk.is_cycle_def, Ne.def] at hc
+  simp only [walk.is_cycle_def, Ne.def] at hc 
   cases c
   · exact absurd rfl hc.2.1
   · simp only [walk.cons_is_trail_iff, not_false_iff, walk.support_cons, List.tail_cons,
-      true_and_iff] at hc
+      true_and_iff] at hc 
     specialize h _ _ ⟨c_p, by simp only [walk.is_path_def, hc.2]⟩ (path.singleton (G.symm c_h))
-    simp only [path.singleton] at h
+    simp only [path.singleton] at h 
     simpa [-Quotient.eq', Sym2.eq_swap, h] using hc
 #align simple_graph.is_acyclic_of_path_unique SimpleGraph.isAcyclic_of_path_unique
 -/

832f7b91

bump to nightly-2023-05-28-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

ba5d8b97

Diff

@@ -88,12 +88,6 @@ theorem isAcyclic_iff_forall_adj_isBridge :
 #align simple_graph.is_acyclic_iff_forall_adj_is_bridge SimpleGraph.isAcyclic_iff_forall_adj_isBridge
 -/
 
-/- warning: simple_graph.is_acyclic_iff_forall_edge_is_bridge -> SimpleGraph.isAcyclic_iff_forall_edge_isBridge is a dubious translation:
-lean 3 declaration is
-  forall {V : Type.{u1}} {G : SimpleGraph.{u1} V}, Iff (SimpleGraph.IsAcyclic.{u1} V G) (forall {{e : Sym2.{u1} V}}, (Membership.Mem.{u1, u1} (Sym2.{u1} V) (Set.{u1} (Sym2.{u1} V)) (Set.hasMem.{u1} (Sym2.{u1} V)) e (coeFn.{succ u1, succ u1} (OrderEmbedding.{u1, u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)) (SimpleGraph.hasLe.{u1} V) (Set.hasLe.{u1} (Sym2.{u1} V))) (fun (_x : RelEmbedding.{u1, u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)) (LE.le.{u1} (SimpleGraph.{u1} V) (SimpleGraph.hasLe.{u1} V)) (LE.le.{u1} (Set.{u1} (Sym2.{u1} V)) (Set.hasLe.{u1} (Sym2.{u1} V)))) => (SimpleGraph.{u1} V) -> (Set.{u1} (Sym2.{u1} V))) (RelEmbedding.hasCoeToFun.{u1, u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)) (LE.le.{u1} (SimpleGraph.{u1} V) (SimpleGraph.hasLe.{u1} V)) (LE.le.{u1} (Set.{u1} (Sym2.{u1} V)) (Set.hasLe.{u1} (Sym2.{u1} V)))) (SimpleGraph.edgeSetEmbedding.{u1} V) G)) -> (SimpleGraph.IsBridge.{u1} V G e))
-but is expected to have type
-  forall {V : Type.{u1}} {G : SimpleGraph.{u1} V}, Iff (SimpleGraph.IsAcyclic.{u1} V G) (forall {{e : Sym2.{u1} V}}, (Membership.mem.{u1, u1} (Sym2.{u1} V) (Set.{u1} (Sym2.{u1} V)) (Set.instMembershipSet.{u1} (Sym2.{u1} V)) e (SimpleGraph.edgeSet.{u1} V G)) -> (SimpleGraph.IsBridge.{u1} V G e))
-Case conversion may be inaccurate. Consider using '#align simple_graph.is_acyclic_iff_forall_edge_is_bridge SimpleGraph.isAcyclic_iff_forall_edge_isBridgeₓ'. -/
 theorem isAcyclic_iff_forall_edge_isBridge :
     G.IsAcyclic ↔ ∀ ⦃e⦄, e ∈ G.edgeSetEmbedding → G.IsBridge e := by
   simp [is_acyclic_iff_forall_adj_is_bridge, Sym2.forall]

832f7b91

bump to nightly-2023-03-03-22

mathlib commit https://github.com/leanprover-community/mathlib/commit/62e8311c791f02c47451bf14aa2501048e7c2f33

7fe4dd24

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kyle Miller
 
 ! This file was ported from Lean 3 source module combinatorics.simple_graph.acyclic
-! leanprover-community/mathlib commit b07688016d62f81d14508ff339ea3415558d6353
+! leanprover-community/mathlib commit 832f7b9162039c28b9361289c8681f155cae758f
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -14,6 +14,9 @@ import Mathbin.Combinatorics.SimpleGraph.Connectivity
 
 # Acyclic graphs and trees
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 This module introduces *acyclic graphs* (a.k.a. *forests*) and *trees*.
 
 ## Main definitions

b0768801

bump to nightly-2023-03-02-10

mathlib commit https://github.com/leanprover-community/mathlib/commit/195fcd60ff2bfe392543bceb0ec2adcdb472db4c

01978261

Diff

@@ -89,7 +89,7 @@ theorem isAcyclic_iff_forall_adj_isBridge :
 lean 3 declaration is
   forall {V : Type.{u1}} {G : SimpleGraph.{u1} V}, Iff (SimpleGraph.IsAcyclic.{u1} V G) (forall {{e : Sym2.{u1} V}}, (Membership.Mem.{u1, u1} (Sym2.{u1} V) (Set.{u1} (Sym2.{u1} V)) (Set.hasMem.{u1} (Sym2.{u1} V)) e (coeFn.{succ u1, succ u1} (OrderEmbedding.{u1, u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)) (SimpleGraph.hasLe.{u1} V) (Set.hasLe.{u1} (Sym2.{u1} V))) (fun (_x : RelEmbedding.{u1, u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)) (LE.le.{u1} (SimpleGraph.{u1} V) (SimpleGraph.hasLe.{u1} V)) (LE.le.{u1} (Set.{u1} (Sym2.{u1} V)) (Set.hasLe.{u1} (Sym2.{u1} V)))) => (SimpleGraph.{u1} V) -> (Set.{u1} (Sym2.{u1} V))) (RelEmbedding.hasCoeToFun.{u1, u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)) (LE.le.{u1} (SimpleGraph.{u1} V) (SimpleGraph.hasLe.{u1} V)) (LE.le.{u1} (Set.{u1} (Sym2.{u1} V)) (Set.hasLe.{u1} (Sym2.{u1} V)))) (SimpleGraph.edgeSetEmbedding.{u1} V) G)) -> (SimpleGraph.IsBridge.{u1} V G e))
 but is expected to have type
-  forall {V : Type.{u1}} {G : SimpleGraph.{u1} V}, Iff (SimpleGraph.IsAcyclic.{u1} V G) (forall {{e : Sym2.{u1} V}}, (Membership.mem.{u1, u1} (Sym2.{u1} V) ((fun (x._@.Mathlib.Data.FunLike.Embedding._hyg.19 : SimpleGraph.{u1} V) => Set.{u1} (Sym2.{u1} V)) G) (Set.instMembershipSet.{u1} (Sym2.{u1} V)) e (FunLike.coe.{succ u1, succ u1, succ u1} (Function.Embedding.{succ u1, succ u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V))) (SimpleGraph.{u1} V) (fun (_x : SimpleGraph.{u1} V) => (fun (x._@.Mathlib.Data.FunLike.Embedding._hyg.19 : SimpleGraph.{u1} V) => Set.{u1} (Sym2.{u1} V)) _x) (EmbeddingLike.toFunLike.{succ u1, succ u1, succ u1} (Function.Embedding.{succ u1, succ u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V))) (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)) (Function.instEmbeddingLikeEmbedding.{succ u1, succ u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)))) (RelEmbedding.toEmbedding.{u1, u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)) (fun (x._@.Mathlib.Order.Hom.Basic._hyg.680 : SimpleGraph.{u1} V) (x._@.Mathlib.Order.Hom.Basic._hyg.682 : SimpleGraph.{u1} V) => LE.le.{u1} (SimpleGraph.{u1} V) (SimpleGraph.instLESimpleGraph.{u1} V) x._@.Mathlib.Order.Hom.Basic._hyg.680 x._@.Mathlib.Order.Hom.Basic._hyg.682) (fun (x._@.Mathlib.Order.Hom.Basic._hyg.695 : Set.{u1} (Sym2.{u1} V)) (x._@.Mathlib.Order.Hom.Basic._hyg.697 : Set.{u1} (Sym2.{u1} V)) => LE.le.{u1} (Set.{u1} (Sym2.{u1} V)) (Set.instLESet.{u1} (Sym2.{u1} V)) x._@.Mathlib.Order.Hom.Basic._hyg.695 x._@.Mathlib.Order.Hom.Basic._hyg.697) (SimpleGraph.edgeSetEmbedding.{u1} V)) G)) -> (SimpleGraph.IsBridge.{u1} V G e))
+  forall {V : Type.{u1}} {G : SimpleGraph.{u1} V}, Iff (SimpleGraph.IsAcyclic.{u1} V G) (forall {{e : Sym2.{u1} V}}, (Membership.mem.{u1, u1} (Sym2.{u1} V) (Set.{u1} (Sym2.{u1} V)) (Set.instMembershipSet.{u1} (Sym2.{u1} V)) e (SimpleGraph.edgeSet.{u1} V G)) -> (SimpleGraph.IsBridge.{u1} V G e))
 Case conversion may be inaccurate. Consider using '#align simple_graph.is_acyclic_iff_forall_edge_is_bridge SimpleGraph.isAcyclic_iff_forall_edge_isBridgeₓ'. -/
 theorem isAcyclic_iff_forall_edge_isBridge :
     G.IsAcyclic ↔ ∀ ⦃e⦄, e ∈ G.edgeSetEmbedding → G.IsBridge e := by

b0768801

bump to nightly-2023-03-01-20

mathlib commit https://github.com/leanprover-community/mathlib/commit/4c586d291f189eecb9d00581aeb3dd998ac34442

20cadee0

Diff

@@ -48,20 +48,25 @@ namespace SimpleGraph
 
 variable {V : Type u} (G : SimpleGraph V)
 
+#print SimpleGraph.IsAcyclic /-
 /-- A graph is *acyclic* (or a *forest*) if it has no cycles. -/
 def IsAcyclic : Prop :=
   ∀ (v : V) (c : G.Walk v v), ¬c.IsCycle
 #align simple_graph.is_acyclic SimpleGraph.IsAcyclic
+-/
 
+#print SimpleGraph.IsTree /-
 /-- A *tree* is a connected acyclic graph. -/
 @[mk_iff, protect_proj]
 structure IsTree : Prop where
   is_connected : G.Connected
   IsAcyclic : G.IsAcyclic
 #align simple_graph.is_tree SimpleGraph.IsTree
+-/
 
 variable {G}
 
+#print SimpleGraph.isAcyclic_iff_forall_adj_isBridge /-
 theorem isAcyclic_iff_forall_adj_isBridge :
     G.IsAcyclic ↔ ∀ ⦃v w : V⦄, G.Adj v w → G.IsBridge ⟦(v, w)⟧ :=
   by
@@ -78,12 +83,20 @@ theorem isAcyclic_iff_forall_adj_isBridge :
       rw [walk.edges_cons]
       apply List.mem_cons_self
 #align simple_graph.is_acyclic_iff_forall_adj_is_bridge SimpleGraph.isAcyclic_iff_forall_adj_isBridge
+-/
 
+/- warning: simple_graph.is_acyclic_iff_forall_edge_is_bridge -> SimpleGraph.isAcyclic_iff_forall_edge_isBridge is a dubious translation:
+lean 3 declaration is
+  forall {V : Type.{u1}} {G : SimpleGraph.{u1} V}, Iff (SimpleGraph.IsAcyclic.{u1} V G) (forall {{e : Sym2.{u1} V}}, (Membership.Mem.{u1, u1} (Sym2.{u1} V) (Set.{u1} (Sym2.{u1} V)) (Set.hasMem.{u1} (Sym2.{u1} V)) e (coeFn.{succ u1, succ u1} (OrderEmbedding.{u1, u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)) (SimpleGraph.hasLe.{u1} V) (Set.hasLe.{u1} (Sym2.{u1} V))) (fun (_x : RelEmbedding.{u1, u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)) (LE.le.{u1} (SimpleGraph.{u1} V) (SimpleGraph.hasLe.{u1} V)) (LE.le.{u1} (Set.{u1} (Sym2.{u1} V)) (Set.hasLe.{u1} (Sym2.{u1} V)))) => (SimpleGraph.{u1} V) -> (Set.{u1} (Sym2.{u1} V))) (RelEmbedding.hasCoeToFun.{u1, u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)) (LE.le.{u1} (SimpleGraph.{u1} V) (SimpleGraph.hasLe.{u1} V)) (LE.le.{u1} (Set.{u1} (Sym2.{u1} V)) (Set.hasLe.{u1} (Sym2.{u1} V)))) (SimpleGraph.edgeSetEmbedding.{u1} V) G)) -> (SimpleGraph.IsBridge.{u1} V G e))
+but is expected to have type
+  forall {V : Type.{u1}} {G : SimpleGraph.{u1} V}, Iff (SimpleGraph.IsAcyclic.{u1} V G) (forall {{e : Sym2.{u1} V}}, (Membership.mem.{u1, u1} (Sym2.{u1} V) ((fun (x._@.Mathlib.Data.FunLike.Embedding._hyg.19 : SimpleGraph.{u1} V) => Set.{u1} (Sym2.{u1} V)) G) (Set.instMembershipSet.{u1} (Sym2.{u1} V)) e (FunLike.coe.{succ u1, succ u1, succ u1} (Function.Embedding.{succ u1, succ u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V))) (SimpleGraph.{u1} V) (fun (_x : SimpleGraph.{u1} V) => (fun (x._@.Mathlib.Data.FunLike.Embedding._hyg.19 : SimpleGraph.{u1} V) => Set.{u1} (Sym2.{u1} V)) _x) (EmbeddingLike.toFunLike.{succ u1, succ u1, succ u1} (Function.Embedding.{succ u1, succ u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V))) (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)) (Function.instEmbeddingLikeEmbedding.{succ u1, succ u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)))) (RelEmbedding.toEmbedding.{u1, u1} (SimpleGraph.{u1} V) (Set.{u1} (Sym2.{u1} V)) (fun (x._@.Mathlib.Order.Hom.Basic._hyg.680 : SimpleGraph.{u1} V) (x._@.Mathlib.Order.Hom.Basic._hyg.682 : SimpleGraph.{u1} V) => LE.le.{u1} (SimpleGraph.{u1} V) (SimpleGraph.instLESimpleGraph.{u1} V) x._@.Mathlib.Order.Hom.Basic._hyg.680 x._@.Mathlib.Order.Hom.Basic._hyg.682) (fun (x._@.Mathlib.Order.Hom.Basic._hyg.695 : Set.{u1} (Sym2.{u1} V)) (x._@.Mathlib.Order.Hom.Basic._hyg.697 : Set.{u1} (Sym2.{u1} V)) => LE.le.{u1} (Set.{u1} (Sym2.{u1} V)) (Set.instLESet.{u1} (Sym2.{u1} V)) x._@.Mathlib.Order.Hom.Basic._hyg.695 x._@.Mathlib.Order.Hom.Basic._hyg.697) (SimpleGraph.edgeSetEmbedding.{u1} V)) G)) -> (SimpleGraph.IsBridge.{u1} V G e))
+Case conversion may be inaccurate. Consider using '#align simple_graph.is_acyclic_iff_forall_edge_is_bridge SimpleGraph.isAcyclic_iff_forall_edge_isBridgeₓ'. -/
 theorem isAcyclic_iff_forall_edge_isBridge :
     G.IsAcyclic ↔ ∀ ⦃e⦄, e ∈ G.edgeSetEmbedding → G.IsBridge e := by
   simp [is_acyclic_iff_forall_adj_is_bridge, Sym2.forall]
 #align simple_graph.is_acyclic_iff_forall_edge_is_bridge SimpleGraph.isAcyclic_iff_forall_edge_isBridge
 
+#print SimpleGraph.IsAcyclic.path_unique /-
 theorem IsAcyclic.path_unique {G : SimpleGraph V} (h : G.IsAcyclic) {v w : V} (p q : G.Path v w) :
     p = q := by
   obtain ⟨p, hp⟩ := p
@@ -109,7 +122,9 @@ theorem IsAcyclic.path_unique {G : SimpleGraph V} (h : G.IsAcyclic) {v w : V} (p
     · rw [walk.cons_is_path_iff] at hp
       exact absurd (walk.fst_mem_support_of_mem_edges _ h) hp.2
 #align simple_graph.is_acyclic.path_unique SimpleGraph.IsAcyclic.path_unique
+-/
 
+#print SimpleGraph.isAcyclic_of_path_unique /-
 theorem isAcyclic_of_path_unique (h : ∀ (v w : V) (p q : G.Path v w), p = q) : G.IsAcyclic :=
   by
   intro v c hc
@@ -122,11 +137,15 @@ theorem isAcyclic_of_path_unique (h : ∀ (v w : V) (p q : G.Path v w), p = q) :
     simp only [path.singleton] at h
     simpa [-Quotient.eq', Sym2.eq_swap, h] using hc
 #align simple_graph.is_acyclic_of_path_unique SimpleGraph.isAcyclic_of_path_unique
+-/
 
+#print SimpleGraph.isAcyclic_iff_path_unique /-
 theorem isAcyclic_iff_path_unique : G.IsAcyclic ↔ ∀ ⦃v w : V⦄ (p q : G.Path v w), p = q :=
   ⟨IsAcyclic.path_unique, isAcyclic_of_path_unique⟩
 #align simple_graph.is_acyclic_iff_path_unique SimpleGraph.isAcyclic_iff_path_unique
+-/
 
+#print SimpleGraph.isTree_iff_existsUnique_path /-
 theorem isTree_iff_existsUnique_path :
     G.IsTree ↔ Nonempty V ∧ ∀ v w : V, ∃! p : G.Walk v w, p.IsPath := by
   classical
@@ -149,6 +168,7 @@ theorem isTree_iff_existsUnique_path :
       · rintro v w ⟨p, hp⟩ ⟨q, hq⟩
         simp only [ExistsUnique.unique (h v w) hp hq]
 #align simple_graph.is_tree_iff_exists_unique_path SimpleGraph.isTree_iff_existsUnique_path
+-/
 
 end SimpleGraph

b0768801

bump to nightly-2023-02-25-00

mathlib commit https://github.com/leanprover-community/mathlib/commit/22131150f88a2d125713ffa0f4693e3355b1eb49

aca219f8

Diff

@@ -79,7 +79,8 @@ theorem isAcyclic_iff_forall_adj_isBridge :
       apply List.mem_cons_self
 #align simple_graph.is_acyclic_iff_forall_adj_is_bridge SimpleGraph.isAcyclic_iff_forall_adj_isBridge
 
-theorem isAcyclic_iff_forall_edge_isBridge : G.IsAcyclic ↔ ∀ ⦃e⦄, e ∈ G.edgeSet → G.IsBridge e := by
+theorem isAcyclic_iff_forall_edge_isBridge :
+    G.IsAcyclic ↔ ∀ ⦃e⦄, e ∈ G.edgeSetEmbedding → G.IsBridge e := by
   simp [is_acyclic_iff_forall_adj_is_bridge, Sym2.forall]
 #align simple_graph.is_acyclic_iff_forall_edge_is_bridge SimpleGraph.isAcyclic_iff_forall_edge_isBridge

b0768801

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

b0768801

chore: adapt to multiple goal linter 1 (#12338)

A PR accompanying #12339.

Zulip discussion

45f93f3f

Diff

@@ -181,8 +181,8 @@ lemma IsTree.card_edgeFinset [Fintype V] [Fintype G.edgeSet] (hG : G.IsTree) :
     · have h1 : ((f a).firstDart <| not_nil_of_ne (by simpa using ha)).snd = b :=
         congrArg (·.snd) h
       have h3 := congrArg length (hf' _ (((f _).tail _).copy h1 rfl) ?_)
-      rw [length_copy, ← add_left_inj 1, length_tail_add_one] at h3
-      · omega
+      · rw [length_copy, ← add_left_inj 1, length_tail_add_one] at h3
+        omega
       · simp only [ne_eq, eq_mp_eq_cast, id_eq, isPath_copy]
         exact (hf _).tail _
   case surj =>
@@ -198,7 +198,7 @@ lemma IsTree.card_edgeFinset [Fintype V] [Fintype G.edgeSet] (hG : G.IsTree) :
           length_cons, length_nil] at h'
       simp [Nat.le_zero, Nat.one_ne_zero] at h'
     rw [← hf' _ (.cons h.symm (f x)) ((cons_isPath_iff _ _).2 ⟨hf _, fun hy => ?contra⟩)]
-    rfl
+    · rfl
     case contra =>
       suffices (f x).takeUntil y hy = .cons h .nil by
         rw [← take_spec _ hy] at h'

b0768801

chore: avoid Ne.def (adaptation for nightly-2024-03-27) (#11801)

1b40c7bc

Diff

@@ -117,7 +117,7 @@ theorem IsAcyclic.path_unique {G : SimpleGraph V} (h : G.IsAcyclic) {v w : V} (p
 
 theorem isAcyclic_of_path_unique (h : ∀ (v w : V) (p q : G.Path v w), p = q) : G.IsAcyclic := by
   intro v c hc
-  simp only [Walk.isCycle_def, Ne.def] at hc
+  simp only [Walk.isCycle_def, Ne] at hc
   cases c with
   | nil => cases hc.2.1 rfl
   | cons ha c' =>

b0768801

chore: Reduce scope of LinearOrderedCommGroupWithZero (#11716)

Reconstitute the file Algebra.Order.Monoid.WithZero from three files:

Algebra.Order.Monoid.WithZero.Defs
Algebra.Order.Monoid.WithZero.Basic
Algebra.Order.WithZero

Avoid importing it in many files. Most uses were just to get le_zero_iff to work on Nat.

Before pre_11716

After post_11716

bb349f30

Diff

@@ -196,7 +196,7 @@ lemma IsTree.card_edgeFinset [Fintype V] [Fintype G.edgeSet] (hG : G.IsTree) :
       rw [← hf' _ nil IsPath.nil, length_nil,
           ← hf' _ (.cons h .nil) (IsPath.nil.cons <| by simpa using h.ne),
           length_cons, length_nil] at h'
-      simp [le_zero_iff, Nat.one_ne_zero] at h'
+      simp [Nat.le_zero, Nat.one_ne_zero] at h'
     rw [← hf' _ (.cons h.symm (f x)) ((cons_isPath_iff _ _).2 ⟨hf _, fun hy => ?contra⟩)]
     rfl
     case contra =>

b0768801

chore: replace λ by fun (#11301)

Per the style guidelines, λ is disallowed in mathlib. This is close to exhaustive; I left some tactic code alone when it seemed to me that tactic could be upstreamed soon.

Notes

In lines I was modifying anyway, I also converted => to ↦.
Also contains some mild in-passing indentation fixes in Mathlib/Order/SupClosed.
Some doc comments still contained Lean 3 syntax λ x, , which I also replaced.

af0f54a9

Diff

@@ -63,7 +63,7 @@ structure IsTree : Prop where
 
 variable {G}
 
-@[simp] lemma isAcyclic_bot : IsAcyclic (⊥ : SimpleGraph V) := λ _a _w hw ↦ hw.ne_bot rfl
+@[simp] lemma isAcyclic_bot : IsAcyclic (⊥ : SimpleGraph V) := fun _a _w hw ↦ hw.ne_bot rfl
 
 theorem isAcyclic_iff_forall_adj_isBridge :
     G.IsAcyclic ↔ ∀ ⦃v w : V⦄, G.Adj v w → G.IsBridge s(v, w) := by

b0768801

refactor: optimize proofs with omega (#11093)

I ran tryAtEachStep on all files under Mathlib to find all locations where omega succeeds. For each that was a linarith without an only, I tried replacing it with omega, and I verified that elaboration time got smaller. (In almost all cases, there was a noticeable speedup.) I also replaced some slow aesops along the way.

37bc4aba

Diff

@@ -182,8 +182,7 @@ lemma IsTree.card_edgeFinset [Fintype V] [Fintype G.edgeSet] (hG : G.IsTree) :
         congrArg (·.snd) h
       have h3 := congrArg length (hf' _ (((f _).tail _).copy h1 rfl) ?_)
       rw [length_copy, ← add_left_inj 1, length_tail_add_one] at h3
-      · exfalso
-        linarith
+      · omega
       · simp only [ne_eq, eq_mp_eq_cast, id_eq, isPath_copy]
         exact (hf _).tail _
   case surj =>

b0768801

chore: remove stream-of-consciousness uses of have, replace and suffices (#10640)

No changes to tactic file, it's just boring fixes throughout the library.

This follows on from #6964.

Co-authored-by: sgouezel <sebastien.gouezel@univ-rennes1.fr> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

a13e8040

Diff

@@ -201,8 +201,8 @@ lemma IsTree.card_edgeFinset [Fintype V] [Fintype G.edgeSet] (hG : G.IsTree) :
     rw [← hf' _ (.cons h.symm (f x)) ((cons_isPath_iff _ _).2 ⟨hf _, fun hy => ?contra⟩)]
     rfl
     case contra =>
-      suffices : (f x).takeUntil y hy = .cons h .nil
-      · rw [← take_spec _ hy] at h'
+      suffices (f x).takeUntil y hy = .cons h .nil by
+        rw [← take_spec _ hy] at h'
         simp [this, hf' _ _ ((hf _).dropUntil hy)] at h'
       refine (hG.existsUnique_path _ _).unique ((hf _).takeUntil _) ?_
       simp [h.ne]

b0768801

refactor: decapitalize names in @[mk_iff] (#9378)

@[mk_iff] class MyPred now generates myPred_iff, not MyPred_iff
add Lean.Name.decapitalize
fix indentation and a few typos in the docs/comments.

Partially addresses issue #9129

5192777c

Diff

@@ -134,7 +134,7 @@ theorem isAcyclic_iff_path_unique : G.IsAcyclic ↔ ∀ ⦃v w : V⦄ (p q : G.P
 theorem isTree_iff_existsUnique_path :
     G.IsTree ↔ Nonempty V ∧ ∀ v w : V, ∃! p : G.Walk v w, p.IsPath := by
   classical
-  rw [IsTree_iff, isAcyclic_iff_path_unique]
+  rw [isTree_iff, isAcyclic_iff_path_unique]
   constructor
   · rintro ⟨hc, hu⟩
     refine ⟨hc.nonempty, ?_⟩

b0768801

refactor: remove Sym2's global Prod setoid instance, use s(x, y) notation for unordered pairs (#8729)

The Sym2 type used a global setoid instance on α × α so that ⟦(x, y)⟧ could stand for an unordered pair using standard Quotient syntax. This commit refactors Sym2 to not use Quotient and instead use its own s(x, y) notation. One benefit to this is that this notation produces a term with type Sym2 rather than Quotient.

The Fintype instance for Sym2 is in Mathlib.Data.Finset.Sym. We switch from using the one for Quotient because it does not require DecidableEq.

9ed6b90f

Diff

@@ -66,7 +66,7 @@ variable {G}
 @[simp] lemma isAcyclic_bot : IsAcyclic (⊥ : SimpleGraph V) := λ _a _w hw ↦ hw.ne_bot rfl
 
 theorem isAcyclic_iff_forall_adj_isBridge :
-    G.IsAcyclic ↔ ∀ ⦃v w : V⦄, G.Adj v w → G.IsBridge ⟦(v, w)⟧ := by
+    G.IsAcyclic ↔ ∀ ⦃v w : V⦄, G.Adj v w → G.IsBridge s(v, w) := by
   simp_rw [isBridge_iff_adj_and_forall_cycle_not_mem]
   constructor
   · intro ha v w hvw

b0768801

feat: Girth of a simple graph (#6948)

Define the girth of a simple graph as a ℕ∞.

02e140cb

Diff

@@ -63,6 +63,8 @@ structure IsTree : Prop where
 
 variable {G}
 
+@[simp] lemma isAcyclic_bot : IsAcyclic (⊥ : SimpleGraph V) := λ _a _w hw ↦ hw.ne_bot rfl
+
 theorem isAcyclic_iff_forall_adj_isBridge :
     G.IsAcyclic ↔ ∀ ⦃v w : V⦄, G.Adj v w → G.IsBridge ⟦(v, w)⟧ := by
   simp_rw [isBridge_iff_adj_and_forall_cycle_not_mem]

b0768801

feat: Number of edges of a tree (#5918)

Port/review of [mathlib#18638](https://github.com/leanprover-community/mathlib/pull/18638) directly to Mathlib4.

Co-authored-by: Yaël Dillies <yael.dillies@gmail.com> Co-authored-by: Bhavik Mehta <bhavikmehta8@gmail.com>

4d415323

Diff

@@ -4,6 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kyle Miller
 -/
 import Mathlib.Combinatorics.SimpleGraph.Connectivity
+import Mathlib.Tactic.Linarith
 
 #align_import combinatorics.simple_graph.acyclic from "leanprover-community/mathlib"@"b07688016d62f81d14508ff339ea3415558d6353"
 
@@ -43,6 +44,8 @@ universe u v
 
 namespace SimpleGraph
 
+open Walk
+
 variable {V : Type u} (G : SimpleGraph V)
 
 /-- A graph is *acyclic* (or a *forest*) if it has no cycles. -/
@@ -149,4 +152,57 @@ theorem isTree_iff_existsUnique_path :
       simp only [ExistsUnique.unique (h v w) hp hq]
 #align simple_graph.is_tree_iff_exists_unique_path SimpleGraph.isTree_iff_existsUnique_path
 
+lemma IsTree.existsUnique_path (hG : G.IsTree) : ∀ v w, ∃! p : G.Walk v w, p.IsPath :=
+  (isTree_iff_existsUnique_path.1 hG).2
+
+lemma IsTree.card_edgeFinset [Fintype V] [Fintype G.edgeSet] (hG : G.IsTree) :
+    Finset.card G.edgeFinset + 1 = Fintype.card V := by
+  have := hG.isConnected.nonempty
+  inhabit V
+  classical
+  have : Finset.card ({default} : Finset V)ᶜ + 1 = Fintype.card V := by
+    rw [Finset.card_compl, Finset.card_singleton, Nat.sub_add_cancel Fintype.card_pos]
+  rw [← this, add_left_inj]
+  choose f hf hf' using (hG.existsUnique_path · default)
+  refine Eq.symm <| Finset.card_congr
+          (fun w hw => ((f w).firstDart <| ?notNil).edge)
+          (fun a ha => ?memEdges) ?inj ?surj
+  case notNil => exact not_nil_of_ne (by simpa using hw)
+  case memEdges => simp
+  case inj =>
+    intros a b ha hb h
+    wlog h' : (f a).length ≤ (f b).length generalizing a b
+    · exact Eq.symm (this _ _ hb ha h.symm (le_of_not_le h'))
+    rw [dart_edge_eq_iff] at h
+    obtain (h | h) := h
+    · exact (congrArg (·.fst) h)
+    · have h1 : ((f a).firstDart <| not_nil_of_ne (by simpa using ha)).snd = b :=
+        congrArg (·.snd) h
+      have h3 := congrArg length (hf' _ (((f _).tail _).copy h1 rfl) ?_)
+      rw [length_copy, ← add_left_inj 1, length_tail_add_one] at h3
+      · exfalso
+        linarith
+      · simp only [ne_eq, eq_mp_eq_cast, id_eq, isPath_copy]
+        exact (hf _).tail _
+  case surj =>
+    simp only [mem_edgeFinset, Finset.mem_compl, Finset.mem_singleton, Sym2.forall, mem_edgeSet]
+    intros x y h
+    wlog h' : (f x).length ≤ (f y).length generalizing x y
+    · rw [Sym2.eq_swap]
+      exact this y x h.symm (le_of_not_le h')
+    refine ⟨y, ?_, dart_edge_eq_mk'_iff.2 <| Or.inr ?_⟩
+    · rintro rfl
+      rw [← hf' _ nil IsPath.nil, length_nil,
+          ← hf' _ (.cons h .nil) (IsPath.nil.cons <| by simpa using h.ne),
+          length_cons, length_nil] at h'
+      simp [le_zero_iff, Nat.one_ne_zero] at h'
+    rw [← hf' _ (.cons h.symm (f x)) ((cons_isPath_iff _ _).2 ⟨hf _, fun hy => ?contra⟩)]
+    rfl
+    case contra =>
+      suffices : (f x).takeUntil y hy = .cons h .nil
+      · rw [← take_spec _ hy] at h'
+        simp [this, hf' _ _ ((hf _).dropUntil hy)] at h'
+      refine (hG.existsUnique_path _ _).unique ((hf _).takeUntil _) ?_
+      simp [h.ne]
+
 end SimpleGraph

b0768801

chore: bump to nightly-2023-07-15 (#5992)

Various adaptations to changes when Fin API was moved to Std. One notable change is that many lemmas are now stated in terms of i ≠ 0 (for i : Fin n) rather then i.1 ≠ 0, and as a consequence many Fin.vne_of_ne applications have been added or removed, mostly removed.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Wojciech Nawrocki <wjnawrocki@protonmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

24924f96

Diff

@@ -94,7 +94,7 @@ theorem IsAcyclic.path_unique {G : SimpleGraph V} (h : G.IsAcyclic) {v w : V} (p
     specialize h ph
     rw [isBridge_iff_adj_and_forall_walk_mem_edges] at h
     replace h := h.2 (q.append p.reverse)
-    simp only [Walk.edges_append, Walk.edges_reverse, List.mem_append, List.mem_reverse'] at h
+    simp only [Walk.edges_append, Walk.edges_reverse, List.mem_append, List.mem_reverse] at h
     cases' h with h h
     · cases q with
       | nil => simp [Walk.isPath_def] at hp

b0768801

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,14 +2,11 @@
 Copyright (c) 2022 Kyle Miller. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kyle Miller
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.acyclic
-! leanprover-community/mathlib commit b07688016d62f81d14508ff339ea3415558d6353
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Combinatorics.SimpleGraph.Connectivity
 
+#align_import combinatorics.simple_graph.acyclic from "leanprover-community/mathlib"@"b07688016d62f81d14508ff339ea3415558d6353"
+
 /-!
 
 # Acyclic graphs and trees

b0768801

chore: some cleanup of Combinatorics.SimpleGraph.Acyclic (#2585)

9c02edae

Diff

@@ -49,19 +49,16 @@ namespace SimpleGraph
 variable {V : Type u} (G : SimpleGraph V)
 
 /-- A graph is *acyclic* (or a *forest*) if it has no cycles. -/
-def IsAcyclic : Prop :=
-  ∀ (v : V) (c : G.Walk v v), ¬c.IsCycle
+def IsAcyclic : Prop := ∀ ⦃v : V⦄ (c : G.Walk v v), ¬c.IsCycle
 #align simple_graph.is_acyclic SimpleGraph.IsAcyclic
 
 /-- A *tree* is a connected acyclic graph. -/
--- porting note: `protect_proj` not (yet) implemented. -/
--- @[mk_iff, protect_proj]
 @[mk_iff]
 structure IsTree : Prop where
   /-- Graph is connected. -/
-  isConnected : G.Connected
+  protected isConnected : G.Connected
   /-- Graph is acyclic. -/
-  IsAcyclic : G.IsAcyclic
+  protected IsAcyclic : G.IsAcyclic
 #align simple_graph.is_tree SimpleGraph.IsTree
 
 variable {G}
@@ -73,11 +70,10 @@ theorem isAcyclic_iff_forall_adj_isBridge :
   · intro ha v w hvw
     apply And.intro hvw
     intro u p hp
-    exact absurd hp (ha _ p)
-  · rintro hb v (_ | @⟨_, _, _, ha, p⟩) hp
+    cases ha p hp
+  · rintro hb v (_ | ⟨ha, p⟩) hp
     · exact hp.not_of_nil
-    · specialize hb ha
-      apply hb.2 _ hp
+    · apply (hb ha).2 _ hp
       rw [Walk.edges_cons]
       apply List.mem_cons_self
 #align simple_graph.is_acyclic_iff_forall_adj_is_bridge SimpleGraph.isAcyclic_iff_forall_adj_isBridge
@@ -87,32 +83,31 @@ theorem isAcyclic_iff_forall_edge_isBridge :
   simp [isAcyclic_iff_forall_adj_isBridge, Sym2.forall]
 #align simple_graph.is_acyclic_iff_forall_edge_is_bridge SimpleGraph.isAcyclic_iff_forall_edge_isBridge
 
--- porting note: `simpa` seems necessary here
-set_option linter.unnecessarySimpa false in
 theorem IsAcyclic.path_unique {G : SimpleGraph V} (h : G.IsAcyclic) {v w : V} (p q : G.Path v w) :
     p = q := by
   obtain ⟨p, hp⟩ := p
   obtain ⟨q, hq⟩ := q
-  simp only
-  induction' p with u pu pv pw ph p ih
-  · rw [Walk.isPath_iff_eq_nil] at hq
-    simp only [hq.symm]
-  · rw [isAcyclic_iff_forall_adj_isBridge] at h
+  rw [Subtype.mk.injEq]
+  induction p with
+  | nil =>
+    cases (Walk.isPath_iff_eq_nil _).mp hq
+    rfl
+  | cons ph p ih =>
+    rw [isAcyclic_iff_forall_adj_isBridge] at h
     specialize h ph
     rw [isBridge_iff_adj_and_forall_walk_mem_edges] at h
     replace h := h.2 (q.append p.reverse)
     simp only [Walk.edges_append, Walk.edges_reverse, List.mem_append, List.mem_reverse'] at h
     cases' h with h h
-    · cases' q with _ _ _ _ _ q
-      · simp [Walk.isPath_def] at hp
-      · rw [Walk.cons_isPath_iff] at hp hq
-        simp only [Walk.edges_cons, List.mem_cons, Sym2.eq_iff] at h
-        simp at h
-        rcases h with  (⟨h, rfl⟩ | ⟨rfl, rfl⟩) | h
-        · have := ih hp.1 q hq.1
-          simp at this
-          simp only [this]
-        · simpa using hq
+    · cases q with
+      | nil => simp [Walk.isPath_def] at hp
+      | cons _ q =>
+        rw [Walk.cons_isPath_iff] at hp hq
+        simp only [Walk.edges_cons, List.mem_cons, Sym2.eq_iff, true_and] at h
+        rcases h with (⟨h, rfl⟩ | ⟨rfl, rfl⟩) | h
+        · cases ih hp.1 q hq.1
+          rfl
+        · simp at hq
         · exact absurd (Walk.fst_mem_support_of_mem_edges _ h) hq.2
     · rw [Walk.cons_isPath_iff] at hp
       exact absurd (Walk.fst_mem_support_of_mem_edges _ h) hp.2
@@ -121,13 +116,12 @@ theorem IsAcyclic.path_unique {G : SimpleGraph V} (h : G.IsAcyclic) {v w : V} (p
 theorem isAcyclic_of_path_unique (h : ∀ (v w : V) (p q : G.Path v w), p = q) : G.IsAcyclic := by
   intro v c hc
   simp only [Walk.isCycle_def, Ne.def] at hc
-  cases' c with _ _ c_v _ c_h c_p
-  · exact absurd rfl hc.2.1
-  · simp only [Walk.cons_isTrail_iff, Walk.support_cons, List.tail_cons,
-      true_and_iff] at hc
-    specialize h _ _ ⟨c_p, by simp only [Walk.isPath_def, hc.2]⟩ (Path.singleton (G.symm c_h))
-    simp only [Path.singleton] at h
-    simp at h
+  cases c with
+  | nil => cases hc.2.1 rfl
+  | cons ha c' =>
+    simp only [Walk.cons_isTrail_iff, Walk.support_cons, List.tail_cons, true_and_iff] at hc
+    specialize h _ _ ⟨c', by simp only [Walk.isPath_def, hc.2]⟩ (Path.singleton ha.symm)
+    rw [Path.singleton, Subtype.mk.injEq] at h
     simp [h] at hc
 #align simple_graph.is_acyclic_of_path_unique SimpleGraph.isAcyclic_of_path_unique
 
@@ -138,24 +132,24 @@ theorem isAcyclic_iff_path_unique : G.IsAcyclic ↔ ∀ ⦃v w : V⦄ (p q : G.P
 theorem isTree_iff_existsUnique_path :
     G.IsTree ↔ Nonempty V ∧ ∀ v w : V, ∃! p : G.Walk v w, p.IsPath := by
   classical
-    rw [IsTree_iff, isAcyclic_iff_path_unique]
-    constructor
-    · rintro ⟨hc, hu⟩
-      refine' ⟨hc.nonempty, _⟩
-      intro v w
-      let q := (hc v w).some.toPath
-      use q
-      simp only [true_and_iff, Path.isPath]
-      intro p hp
-      specialize hu ⟨p, hp⟩ q
-      exact Subtype.ext_iff.mp hu
-    · rintro ⟨hV, h⟩
-      refine' ⟨Connected.mk _, _⟩
-      · intro v w
-        obtain ⟨p, _⟩ := h v w
-        exact p.reachable
-      · rintro v w ⟨p, hp⟩ ⟨q, hq⟩
-        simp only [ExistsUnique.unique (h v w) hp hq]
+  rw [IsTree_iff, isAcyclic_iff_path_unique]
+  constructor
+  · rintro ⟨hc, hu⟩
+    refine ⟨hc.nonempty, ?_⟩
+    intro v w
+    let q := (hc v w).some.toPath
+    use q
+    simp only [true_and_iff, Path.isPath]
+    intro p hp
+    specialize hu ⟨p, hp⟩ q
+    exact Subtype.ext_iff.mp hu
+  · rintro ⟨hV, h⟩
+    refine ⟨Connected.mk ?_, ?_⟩
+    · intro v w
+      obtain ⟨p, _⟩ := h v w
+      exact p.reachable
+    · rintro v w ⟨p, hp⟩ ⟨q, hq⟩
+      simp only [ExistsUnique.unique (h v w) hp hq]
 #align simple_graph.is_tree_iff_exists_unique_path SimpleGraph.isTree_iff_existsUnique_path
 
 end SimpleGraph

b0768801

fix: use edgeSet instead of edgeSetEmbedding (#2576)

Change all occurances of edgeSetEmbedding using the abbreviation and dot notation to edgeSet. The non-use of the abbreviation has been introduced with the port, which we fix here.

Co-authored-by: Moritz Firsching <firsching@google.com>

9844349d

Diff

@@ -83,7 +83,7 @@ theorem isAcyclic_iff_forall_adj_isBridge :
 #align simple_graph.is_acyclic_iff_forall_adj_is_bridge SimpleGraph.isAcyclic_iff_forall_adj_isBridge
 
 theorem isAcyclic_iff_forall_edge_isBridge :
-    G.IsAcyclic ↔ ∀ ⦃e⦄, e ∈ (edgeSetEmbedding V G) → G.IsBridge e := by
+    G.IsAcyclic ↔ ∀ ⦃e⦄, e ∈ (G.edgeSet) → G.IsBridge e := by
   simp [isAcyclic_iff_forall_adj_isBridge, Sym2.forall]
 #align simple_graph.is_acyclic_iff_forall_edge_is_bridge SimpleGraph.isAcyclic_iff_forall_edge_isBridge

b0768801

feat: port Combinatorics.SimpleGraph.Acyclic (#2559)

Co-authored-by: Moritz Firsching <firsching@google.com>

c17b9637

`combinatorics.simple_graph.acyclic` ⟷ `Mathlib.Combinatorics.SimpleGraph.Acyclic`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 6 + 219

combinatorics.simple_graph.acyclic ⟷ Mathlib.Combinatorics.SimpleGraph.Acyclic

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 6 + 219

`combinatorics.simple_graph.acyclic` ⟷ `Mathlib.Combinatorics.SimpleGraph.Acyclic`