internlm/Lean-Github huggingface dataset:
Theorem: Digraph.Walk.edges_bypass_subset
Proof state before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : edges (bypass p✝) ⊆ edges p✝
⊢ edges (if hs : u✝ ∈ support (bypass p✝) then dropUntil (bypass p✝) u✝ hs else cons h✝ (bypass p✝)) ⊆
    (u✝, v✝) :: edges p✝
Tactic:
split_ifs
Proof state after:
case cons.inl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : edges (bypass p✝) ⊆ edges p✝
h✝ : u✝ ∈ support (bypass p✝)
⊢ edges (dropUntil (bypass p✝) u✝ h✝) ⊆ (u✝, v✝) :: edges p✝

case cons.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : edges (bypass p✝) ⊆ edges p✝
h✝ : ¬u✝ ∈ support (bypass p✝)
⊢ edges (cons h✝¹ (bypass p✝)) ⊆ (u✝, v✝) :: edges p✝
Theorem: Digraph.Walk.edges_bypass_subset
Proof state before:
case cons.inl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : edges (bypass p✝) ⊆ edges p✝
h✝ : u✝ ∈ support (bypass p✝)
⊢ edges (dropUntil (bypass p✝) u✝ h✝) ⊆ (u✝, v✝) :: edges p✝
Tactic:
apply List.Subset.trans (edges_dropUntil_subset _ _)
Proof state after:
case cons.inl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : edges (bypass p✝) ⊆ edges p✝
h✝ : u✝ ∈ support (bypass p✝)
⊢ edges (bypass p✝) ⊆ (u✝, v✝) :: edges p✝
Theorem: Digraph.Walk.edges_bypass_subset
Proof state before:
case cons.inl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : edges (bypass p✝) ⊆ edges p✝
h✝ : u✝ ∈ support (bypass p✝)
⊢ edges (bypass p✝) ⊆ (u✝, v✝) :: edges p✝
Tactic:
apply List.subset_cons_of_subset _ ih
Proof state after:
no goals
Theorem: Digraph.Walk.edges_bypass_subset
Proof state before:
case cons.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : edges (bypass p✝) ⊆ edges p✝
h✝ : ¬u✝ ∈ support (bypass p✝)
⊢ edges (cons h✝¹ (bypass p✝)) ⊆ (u✝, v✝) :: edges p✝
Tactic:
rw [edges_cons]
Proof state after:
case cons.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : edges (bypass p✝) ⊆ edges p✝
h✝ : ¬u✝ ∈ support (bypass p✝)
⊢ (u✝, v✝) :: edges (bypass p✝) ⊆ (u✝, v✝) :: edges p✝
Theorem: Digraph.Walk.edges_bypass_subset
Proof state before:
case cons.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : edges (bypass p✝) ⊆ edges p✝
h✝ : ¬u✝ ∈ support (bypass p✝)
⊢ (u✝, v✝) :: edges (bypass p✝) ⊆ (u✝, v✝) :: edges p✝
Tactic:
exact List.cons_subset_cons _ ih
Proof state after:
no goals
Theorem: Digraph.Walk.map_copy
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hu : u = u'
hv : v = v'
⊢ Walk.map f (Walk.copy p hu hv) = Walk.copy (Walk.map f p) (_ : ↑f u = ↑f u') (_ : ↑f v = ↑f v')
Tactic:
subst_vars
Proof state after:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u' v' : V
p : Walk G u' v'
⊢ Walk.map f (Walk.copy p (_ : u' = u') (_ : v' = v')) =
    Walk.copy (Walk.map f p) (_ : ↑f u' = ↑f u') (_ : ↑f v' = ↑f v')
Theorem: Digraph.Walk.map_copy
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u' v' : V
p : Walk G u' v'
⊢ Walk.map f (Walk.copy p (_ : u' = u') (_ : v' = v')) =
    Walk.copy (Walk.map f p) (_ : ↑f u' = ↑f u') (_ : ↑f v' = ↑f v')
Tactic:
rfl
Proof state after:
no goals
Theorem: Digraph.Walk.map_id
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p✝ p : Walk G u v
⊢ Walk.map Hom.id p = p
Tactic:
induction p with
| nil => rfl
| cons _ p' ih => simp [ih p']
Proof state after:
no goals
Theorem: Digraph.Walk.map_id
Proof state before:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' u✝ : V
p : Walk G u✝ u✝
⊢ Walk.map Hom.id nil = nil
Tactic:
rfl
Proof state after:
no goals
Theorem: Digraph.Walk.map_id
Proof state before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p' : Walk G v✝ w✝
ih : Walk G v✝ w✝ → Walk.map Hom.id p' = p'
p : Walk G u✝ w✝
⊢ Walk.map Hom.id (cons h✝ p') = cons h✝ p'
Tactic:
simp [ih p']
Proof state after:
no goals
Theorem: Digraph.Walk.map_map
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
⊢ Walk.map f' (Walk.map f p) = Walk.map (Hom.comp f' f) p
Tactic:
induction p with
| nil => rfl
| cons _ _ ih => simp [ih]
Proof state after:
no goals
Theorem: Digraph.Walk.map_map
Proof state before:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
u✝ : V
⊢ Walk.map f' (Walk.map f nil) = Walk.map (Hom.comp f' f) nil
Tactic:
rfl
Proof state after:
no goals
Theorem: Digraph.Walk.map_map
Proof state before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : Walk.map f' (Walk.map f p✝) = Walk.map (Hom.comp f' f) p✝
⊢ Walk.map f' (Walk.map f (cons h✝ p✝)) = Walk.map (Hom.comp f' f) (cons h✝ p✝)
Tactic:
simp [ih]
Proof state after:
no goals
Theorem: Digraph.Walk.map_eq_of_eq
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f'✝ : G' →g G''
u v u' v' : V
p : Walk G u v
f f' : G →g G'
h : f = f'
⊢ Walk.map f p = Walk.copy (Walk.map f' p) (_ : ↑f' u = ↑f u) (_ : ↑f' v = ↑f v)
Tactic:
subst_vars
Proof state after:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f'✝ : G' →g G''
u v u' v' : V
p : Walk G u v
f' : G →g G'
⊢ Walk.map f' p = Walk.copy (Walk.map f' p) (_ : ↑f' u = ↑f' u) (_ : ↑f' v = ↑f' v)
Theorem: Digraph.Walk.map_eq_of_eq
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f'✝ : G' →g G''
u v u' v' : V
p : Walk G u v
f' : G →g G'
⊢ Walk.map f' p = Walk.copy (Walk.map f' p) (_ : ↑f' u = ↑f' u) (_ : ↑f' v = ↑f' v)
Tactic:
rfl
Proof state after:
no goals
Theorem: Digraph.Walk.map_eq_nil_iff
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p✝ : Walk G u v
p : Walk G u u
⊢ Walk.map f p = nil ↔ p = nil
Tactic:
cases p <;> simp
Proof state after:
no goals
Theorem: Digraph.Walk.length_map
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
⊢ length (Walk.map f p) = length p
Tactic:
induction p <;> simp [*]
Proof state after:
no goals
Theorem: Digraph.Walk.map_append
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u✝ v✝ u' v' : V
p✝ : Walk G u✝ v✝
u v w : V
p : Walk G u v
q : Walk G v w
⊢ Walk.map f (append p q) = append (Walk.map f p) (Walk.map f q)
Tactic:
induction p <;> simp [*]
Proof state after:
no goals
Theorem: Digraph.Walk.support_map
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
⊢ support (Walk.map f p) = List.map (↑f) (support p)
Tactic:
induction p <;> simp [*]
Proof state after:
no goals
Theorem: Digraph.Walk.edges_map
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
⊢ edges (Walk.map f p) = List.map (Prod.map ↑f ↑f) (edges p)
Tactic:
induction p <;> simp [*]
Proof state after:
no goals
Theorem: Digraph.Walk.map_isPath_of_injective
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
hp : IsPath p
⊢ IsPath (Walk.map f p)
Tactic:
induction p with
| nil => simp
| cons _ _ ih =>
  rw [Walk.cons_isPath_iff] at hp
  simp [ih hp.1]
  intro x hx hf
  cases hinj hf
  exact hp.2 hx
Proof state after:
no goals
Theorem: Digraph.Walk.map_isPath_of_injective
Proof state before:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ : V
hp : IsPath nil
⊢ IsPath (Walk.map f nil)
Tactic:
simp
Proof state after:
no goals
Theorem: Digraph.Walk.map_isPath_of_injective
Proof state before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath p✝ → IsPath (Walk.map f p✝)
hp : IsPath (cons h✝ p✝)
⊢ IsPath (Walk.map f (cons h✝ p✝))
Tactic:
rw [Walk.cons_isPath_iff] at hp
Proof state after:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath p✝ → IsPath (Walk.map f p✝)
hp : IsPath p✝ ∧ ¬u✝ ∈ support p✝
⊢ IsPath (Walk.map f (cons h✝ p✝))
Theorem: Digraph.Walk.map_isPath_of_injective
Proof state before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath p✝ → IsPath (Walk.map f p✝)
hp : IsPath p✝ ∧ ¬u✝ ∈ support p✝
⊢ IsPath (Walk.map f (cons h✝ p✝))
Tactic:
simp [ih hp.1]
Proof state after:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath p✝ → IsPath (Walk.map f p✝)
hp : IsPath p✝ ∧ ¬u✝ ∈ support p✝
⊢ ∀ (x : V), x ∈ support p✝ → ¬↑f x = ↑f u✝
Theorem: Digraph.Walk.map_isPath_of_injective
Proof state before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath p✝ → IsPath (Walk.map f p✝)
hp : IsPath p✝ ∧ ¬u✝ ∈ support p✝
⊢ ∀ (x : V), x ∈ support p✝ → ¬↑f x = ↑f u✝
Tactic:
intro x hx hf
Proof state after:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath p✝ → IsPath (Walk.map f p✝)
hp : IsPath p✝ ∧ ¬u✝ ∈ support p✝
x : V
hx : x ∈ support p✝
hf : ↑f x = ↑f u✝
⊢ False
Theorem: Digraph.Walk.map_isPath_of_injective
Proof state before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath p✝ → IsPath (Walk.map f p✝)
hp : IsPath p✝ ∧ ¬u✝ ∈ support p✝
x : V
hx : x ∈ support p✝
hf : ↑f x = ↑f u✝
⊢ False
Tactic:
cases hinj hf
Proof state after:
case cons.refl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath p✝ → IsPath (Walk.map f p✝)
hp : IsPath p✝ ∧ ¬u✝ ∈ support p✝
hx : u✝ ∈ support p✝
hf : ↑f u✝ = ↑f u✝
⊢ False
Theorem: Digraph.Walk.map_isPath_of_injective
Proof state before:
case cons.refl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath p✝ → IsPath (Walk.map f p✝)
hp : IsPath p✝ ∧ ¬u✝ ∈ support p✝
hx : u✝ ∈ support p✝
hf : ↑f u✝ = ↑f u✝
⊢ False
Tactic:
exact hp.2 hx
Proof state after:
no goals
Theorem: Digraph.Walk.IsPath.of_map
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
f : G →g G'
hp : IsPath (Walk.map f p)
⊢ IsPath p
Tactic:
induction p with
| nil => simp
| cons _ _ ih =>
  rw [map_cons, Walk.cons_isPath_iff, support_map] at hp
  rw [Walk.cons_isPath_iff]
  cases' hp with hp1 hp2
  refine' ⟨ih hp1, _⟩
  contrapose! hp2
  exact List.mem_map_of_mem f hp2
Proof state after:
no goals
Theorem: Digraph.Walk.IsPath.of_map
Proof state before:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
f : G →g G'
u✝ : V
hp : IsPath (Walk.map f Walk.nil)
⊢ IsPath Walk.nil
Tactic:
simp
Proof state after:
no goals
Theorem: Digraph.Walk.IsPath.of_map
Proof state before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
f : G →g G'
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath (Walk.map f p✝) → IsPath p✝
hp : IsPath (Walk.map f (cons h✝ p✝))
⊢ IsPath (cons h✝ p✝)
Tactic:
rw [map_cons, Walk.cons_isPath_iff, support_map] at hp
Proof state after:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
f : G →g G'
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath (Walk.map f p✝) → IsPath p✝
hp : IsPath (Walk.map f p✝) ∧ ¬↑f u✝ ∈ List.map (↑f) (support p✝)
⊢ IsPath (cons h✝ p✝)
Theorem: Digraph.Walk.IsPath.of_map
Proof state before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
f : G →g G'
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath (Walk.map f p✝) → IsPath p✝
hp : IsPath (Walk.map f p✝) ∧ ¬↑f u✝ ∈ List.map (↑f) (support p✝)
⊢ IsPath (cons h✝ p✝)
Tactic:
rw [Walk.cons_isPath_iff]
Proof state after:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
f : G →g G'
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath (Walk.map f p✝) → IsPath p✝
hp : IsPath (Walk.map f p✝) ∧ ¬↑f u✝ ∈ List.map (↑f) (support p✝)
⊢ IsPath p✝ ∧ ¬u✝ ∈ support p✝
Theorem: Digraph.Walk.IsPath.of_map
Proof state before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
f : G →g G'
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath (Walk.map f p✝) → IsPath p✝
hp : IsPath (Walk.map f p✝) ∧ ¬↑f u✝ ∈ List.map (↑f) (support p✝)
⊢ IsPath p✝ ∧ ¬u✝ ∈ support p✝
Tactic:
cases' hp with hp1 hp2
Proof state after:
case cons.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
f : G →g G'
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath (Walk.map f p✝) → IsPath p✝
hp1 : IsPath (Walk.map f p✝)
hp2 : ¬↑f u✝ ∈ List.map (↑f) (support p✝)
⊢ IsPath p✝ ∧ ¬u✝ ∈ support p✝
Theorem: Digraph.Walk.IsPath.of_map
Proof state before:
case cons.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
f : G →g G'
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath (Walk.map f p✝) → IsPath p✝
hp1 : IsPath (Walk.map f p✝)
hp2 : ¬↑f u✝ ∈ List.map (↑f) (support p✝)
⊢ IsPath p✝ ∧ ¬u✝ ∈ support p✝
Tactic:
refine' ⟨ih hp1, _⟩
Proof state after:
case cons.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
f : G →g G'
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath (Walk.map f p✝) → IsPath p✝
hp1 : IsPath (Walk.map f p✝)
hp2 : ¬↑f u✝ ∈ List.map (↑f) (support p✝)
⊢ ¬u✝ ∈ support p✝
Theorem: Digraph.Walk.IsPath.of_map
Proof state before:
case cons.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
f : G →g G'
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath (Walk.map f p✝) → IsPath p✝
hp1 : IsPath (Walk.map f p✝)
hp2 : ¬↑f u✝ ∈ List.map (↑f) (support p✝)
⊢ ¬u✝ ∈ support p✝
Tactic:
contrapose! hp2
Proof state after:
case cons.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
f : G →g G'
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath (Walk.map f p✝) → IsPath p✝
hp1 : IsPath (Walk.map f p✝)
hp2 : u✝ ∈ support p✝
⊢ ↑f u✝ ∈ List.map (↑f) (support p✝)
Theorem: Digraph.Walk.IsPath.of_map
Proof state before:
case cons.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
f : G →g G'
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsPath (Walk.map f p✝) → IsPath p✝
hp1 : IsPath (Walk.map f p✝)
hp2 : u✝ ∈ support p✝
⊢ ↑f u✝ ∈ List.map (↑f) (support p✝)
Tactic:
exact List.mem_map_of_mem f hp2
Proof state after:
no goals
Theorem: Digraph.Walk.map_isTrail_iff_of_injective
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
⊢ IsTrail (Walk.map f p) ↔ IsTrail p
Tactic:
induction p with
| nil => simp
| cons _ _ ih =>
  rw [map_cons, cons_isTrail_iff, ih, cons_isTrail_iff]
  apply and_congr_right'
  rw [edges_map, ← List.mem_map_of_injective (Injective.Prod_map hinj hinj)]
  exact Iff.rfl
Proof state after:
no goals
Theorem: Digraph.Walk.map_isTrail_iff_of_injective
Proof state before:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ : V
⊢ IsTrail (Walk.map f nil) ↔ IsTrail nil
Tactic:
simp
Proof state after:
no goals
Theorem: Digraph.Walk.map_isTrail_iff_of_injective
Proof state before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsTrail (Walk.map f p✝) ↔ IsTrail p✝
⊢ IsTrail (Walk.map f (cons h✝ p✝)) ↔ IsTrail (cons h✝ p✝)
Tactic:
rw [map_cons, cons_isTrail_iff, ih, cons_isTrail_iff]
Proof state after:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsTrail (Walk.map f p✝) ↔ IsTrail p✝
⊢ IsTrail p✝ ∧ ¬(↑f u✝, ↑f v✝) ∈ edges (Walk.map f p✝) ↔ IsTrail p✝ ∧ ¬(u✝, v✝) ∈ edges p✝
Theorem: Digraph.Walk.map_isTrail_iff_of_injective
Proof state before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsTrail (Walk.map f p✝) ↔ IsTrail p✝
⊢ IsTrail p✝ ∧ ¬(↑f u✝, ↑f v✝) ∈ edges (Walk.map f p✝) ↔ IsTrail p✝ ∧ ¬(u✝, v✝) ∈ edges p✝
Tactic:
apply and_congr_right'
Proof state after:
case cons.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsTrail (Walk.map f p✝) ↔ IsTrail p✝
⊢ ¬(↑f u✝, ↑f v✝) ∈ edges (Walk.map f p✝) ↔ ¬(u✝, v✝) ∈ edges p✝
Theorem: Digraph.Walk.map_isTrail_iff_of_injective
Proof state before:
case cons.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsTrail (Walk.map f p✝) ↔ IsTrail p✝
⊢ ¬(↑f u✝, ↑f v✝) ∈ edges (Walk.map f p✝) ↔ ¬(u✝, v✝) ∈ edges p✝
Tactic:
rw [edges_map, ← List.mem_map_of_injective (Injective.Prod_map hinj hinj)]
Proof state after:
case cons.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsTrail (Walk.map f p✝) ↔ IsTrail p✝
⊢ ¬(↑f u✝, ↑f v✝) ∈ List.map (Prod.map ↑f ↑f) (edges p✝) ↔
    ¬Prod.map ↑f ↑f (u✝, v✝) ∈ List.map (Prod.map ↑f ↑f) (edges p✝)
Theorem: Digraph.Walk.map_isTrail_iff_of_injective
Proof state before:
case cons.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p : Walk G u v
hinj : Injective ↑f
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : IsTrail (Walk.map f p✝) ↔ IsTrail p✝
⊢ ¬(↑f u✝, ↑f v✝) ∈ List.map (Prod.map ↑f ↑f) (edges p✝) ↔
    ¬Prod.map ↑f ↑f (u✝, v✝) ∈ List.map (Prod.map ↑f ↑f) (edges p✝)
Tactic:
exact Iff.rfl
Proof state after:
no goals
Theorem: Digraph.Walk.map_isCycle_iff_of_injective
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f : G →g G'
f' : G' →g G''
u v u' v' : V
p✝ : Walk G u v
p : Walk G u u
hinj : Injective ↑f
⊢ IsCycle (Walk.map f p) ↔ IsCycle p
Tactic:
rw [isCycle_def, isCycle_def, map_isTrail_iff_of_injective hinj, Ne.def, map_eq_nil_iff,
  support_map, ← List.map_tail, List.nodup_map_iff hinj]
Proof state after:
no goals
Theorem: Digraph.Walk.map_injective_of_injective
Proof state before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝ v✝ u' v' : V
p : Walk G u✝ v✝
f : G →g G'
hinj : Injective ↑f
u v : V
⊢ Injective (Walk.map f)
Tactic:
intro p p' h
Proof state after:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝ v✝ u' v' : V
p✝ : Walk G u✝ v✝
f : G →g G'
hinj : Injective ↑f
u v : V
p p' : Walk G u v
h : Walk.map f p = Walk.map f p'
⊢ p = p'
Theorem: Digraph.Walk.map_injective_of_injective
Proof state before:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝ u' v' : V
p : Walk G u✝¹ v✝
f : G →g G'
hinj : Injective ↑f
u v u✝ : V
p' : Walk G u✝ u✝
h : Walk.map f nil = Walk.map f p'
⊢ nil = p'
Tactic:
cases p'
Proof state after:
case nil.nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝ u' v' : V
p : Walk G u✝¹ v✝
f : G →g G'
hinj : Injective ↑f
u v u✝ : V
h : Walk.map f nil = Walk.map f nil
⊢ nil = nil

case nil.cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
f✝ : G →g G'
f' : G' →g G''
u✝¹ v✝¹ u' v' : V
p : Walk G u✝¹ v✝¹
f : G →g G'
hinj : Injective ↑f
u v u✝ v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ u✝
h : Walk.map f nil = Walk.map f (cons h✝ p✝)
⊢ nil = cons h✝ p✝