Theorem: Digraph.Walk.concat_inj (GraphProjects/DigraphConnectivity.lean)

State before:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ : V
h : G.Adj u✝ w
p' : Walk G u✝ v'
he : concat nil h = concat p' h'
⊢ ∃ hv, Walk.copy nil (_ : u✝ = u✝) hv = p'
Tactic:
cases p'
State after:
case nil.nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' h : G.Adj v' w
he : concat nil h = concat nil h'
⊢ ∃ hv, Walk.copy nil (_ : v' = v') hv = nil

case nil.cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ : V
h : G.Adj u✝ w
v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : concat nil h = concat (cons h✝ p✝) h'
⊢ ∃ hv, Walk.copy nil (_ : u✝ = u✝) hv = cons h✝ p✝

State before:
case nil.nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' h : G.Adj v' w
he : concat nil h = concat nil h'
⊢ ∃ hv, Walk.copy nil (_ : v' = v') hv = nil
Tactic:
exact ⟨rfl, rfl⟩
State after:
no goals

State before:
case nil.cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ : V
h : G.Adj u✝ w
v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : concat nil h = concat (cons h✝ p✝) h'
⊢ ∃ hv, Walk.copy nil (_ : u✝ = u✝) hv = cons h✝ p✝
Tactic:
exfalso
State after:
case nil.cons.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ : V
h : G.Adj u✝ w
v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : concat nil h = concat (cons h✝ p✝) h'
⊢ False

State before:
case nil.cons.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ : V
h : G.Adj u✝ w
v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : concat nil h = concat (cons h✝ p✝) h'
⊢ False
Tactic:
simp only [concat_nil, concat_cons, cons.injEq] at he
State after:
case nil.cons.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ : V
h : G.Adj u✝ w
v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : w = v✝ ∧ HEq nil (concat p✝ h')
⊢ False

State before:
case nil.cons.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ : V
h : G.Adj u✝ w
v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : w = v✝ ∧ HEq nil (concat p✝ h')
⊢ False
Tactic:
obtain ⟨rfl, he⟩ := he
State after:
case nil.cons.h.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ : V
h h✝ : G.Adj u✝ w
p✝ : Walk G w v'
he : HEq nil (concat p✝ h')
⊢ False

State before:
case nil.cons.h.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ : V
h h✝ : G.Adj u✝ w
p✝ : Walk G w v'
he : HEq nil (concat p✝ h')
⊢ False
Tactic:
simp only [heq_iff_eq] at he
State after:
case nil.cons.h.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ : V
h h✝ : G.Adj u✝ w
p✝ : Walk G w v'
he : nil = concat p✝ h'
⊢ False

State before:
case nil.cons.h.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ : V
h h✝ : G.Adj u✝ w
p✝ : Walk G w v'
he : nil = concat p✝ h'
⊢ False
Tactic:
exact concat_ne_nil _ _ he.symm
State after:
no goals

State before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ v'}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ w
p' : Walk G u✝ v'
he : concat (cons h✝ p✝) h = concat p' h'
⊢ ∃ hv, Walk.copy (cons h✝ p✝) (_ : u✝ = u✝) hv = p'
Tactic:
rw [concat_cons] at he
State after:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ v'}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ w
p' : Walk G u✝ v'
he : cons h✝ (concat p✝ h) = concat p' h'
⊢ ∃ hv, Walk.copy (cons h✝ p✝) (_ : u✝ = u✝) hv = p'

State before:
case cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ v✝ w✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ v'}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ w
p' : Walk G u✝ v'
he : cons h✝ (concat p✝ h) = concat p' h'
⊢ ∃ hv, Walk.copy (cons h✝ p✝) (_ : u✝ = u✝) hv = p'
Tactic:
cases p'
State after:
case cons.nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
v✝ w✝ : V
p✝ : Walk G v✝ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ v'}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ w
h✝ : G.Adj v' v✝
he : cons h✝ (concat p✝ h) = concat nil h'
⊢ ∃ hv, Walk.copy (cons h✝ p✝) (_ : v' = v') hv = nil

case cons.cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ v✝¹ w✝ : V
h✝¹ : G.Adj u✝ v✝¹
p✝¹ : Walk G v✝¹ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝¹ v'}, concat p✝¹ h = concat p' h' → ∃ hv, Walk.copy p✝¹ (_ : v✝¹ = v✝¹) hv = p'
h : G.Adj w✝ w
v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : cons h✝¹ (concat p✝¹ h) = concat (cons h✝ p✝) h'
⊢ ∃ hv, Walk.copy (cons h✝¹ p✝¹) (_ : u✝ = u✝) hv = cons h✝ p✝

State before:
case cons.nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
v✝ w✝ : V
p✝ : Walk G v✝ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ v'}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ w
h✝ : G.Adj v' v✝
he : cons h✝ (concat p✝ h) = concat nil h'
⊢ ∃ hv, Walk.copy (cons h✝ p✝) (_ : v' = v') hv = nil
Tactic:
exfalso
State after:
case cons.nil.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
v✝ w✝ : V
p✝ : Walk G v✝ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ v'}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ w
h✝ : G.Adj v' v✝
he : cons h✝ (concat p✝ h) = concat nil h'
⊢ False

State before:
case cons.nil.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
v✝ w✝ : V
p✝ : Walk G v✝ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ v'}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ w
h✝ : G.Adj v' v✝
he : cons h✝ (concat p✝ h) = concat nil h'
⊢ False
Tactic:
simp only [concat_nil, cons.injEq] at he
State after:
case cons.nil.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
v✝ w✝ : V
p✝ : Walk G v✝ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ v'}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ w
h✝ : G.Adj v' v✝
he : v✝ = w ∧ HEq (concat p✝ h) nil
⊢ False

State before:
case cons.nil.h
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
v✝ w✝ : V
p✝ : Walk G v✝ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ v'}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ w
h✝ : G.Adj v' v✝
he : v✝ = w ∧ HEq (concat p✝ h) nil
⊢ False
Tactic:
obtain ⟨rfl, he⟩ := he
State after:
case cons.nil.h.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' v✝ w✝ : V
p✝ : Walk G v✝ w✝
h✝ h' : G.Adj v' v✝
ih : ∀ {h : G.Adj w✝ v✝} {p' : Walk G v✝ v'}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ v✝
he : HEq (concat p✝ h) nil
⊢ False

State before:
case cons.nil.h.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' v✝ w✝ : V
p✝ : Walk G v✝ w✝
h✝ h' : G.Adj v' v✝
ih : ∀ {h : G.Adj w✝ v✝} {p' : Walk G v✝ v'}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ v✝
he : HEq (concat p✝ h) nil
⊢ False
Tactic:
rw [heq_iff_eq] at he
State after:
case cons.nil.h.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' v✝ w✝ : V
p✝ : Walk G v✝ w✝
h✝ h' : G.Adj v' v✝
ih : ∀ {h : G.Adj w✝ v✝} {p' : Walk G v✝ v'}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ v✝
he : concat p✝ h = nil
⊢ False

State before:
case cons.nil.h.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' v✝ w✝ : V
p✝ : Walk G v✝ w✝
h✝ h' : G.Adj v' v✝
ih : ∀ {h : G.Adj w✝ v✝} {p' : Walk G v✝ v'}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ v✝
he : concat p✝ h = nil
⊢ False
Tactic:
exact concat_ne_nil _ _ he
State after:
no goals

State before:
case cons.cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ v✝¹ w✝ : V
h✝¹ : G.Adj u✝ v✝¹
p✝¹ : Walk G v✝¹ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝¹ v'}, concat p✝¹ h = concat p' h' → ∃ hv, Walk.copy p✝¹ (_ : v✝¹ = v✝¹) hv = p'
h : G.Adj w✝ w
v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : cons h✝¹ (concat p✝¹ h) = concat (cons h✝ p✝) h'
⊢ ∃ hv, Walk.copy (cons h✝¹ p✝¹) (_ : u✝ = u✝) hv = cons h✝ p✝
Tactic:
rw [concat_cons, cons.injEq] at he
State after:
case cons.cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ v✝¹ w✝ : V
h✝¹ : G.Adj u✝ v✝¹
p✝¹ : Walk G v✝¹ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝¹ v'}, concat p✝¹ h = concat p' h' → ∃ hv, Walk.copy p✝¹ (_ : v✝¹ = v✝¹) hv = p'
h : G.Adj w✝ w
v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : v✝¹ = v✝ ∧ HEq (concat p✝¹ h) (concat p✝ h')
⊢ ∃ hv, Walk.copy (cons h✝¹ p✝¹) (_ : u✝ = u✝) hv = cons h✝ p✝

State before:
case cons.cons
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ v✝¹ w✝ : V
h✝¹ : G.Adj u✝ v✝¹
p✝¹ : Walk G v✝¹ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝¹ v'}, concat p✝¹ h = concat p' h' → ∃ hv, Walk.copy p✝¹ (_ : v✝¹ = v✝¹) hv = p'
h : G.Adj w✝ w
v✝ : V
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : v✝¹ = v✝ ∧ HEq (concat p✝¹ h) (concat p✝ h')
⊢ ∃ hv, Walk.copy (cons h✝¹ p✝¹) (_ : u✝ = u✝) hv = cons h✝ p✝
Tactic:
obtain ⟨rfl, he⟩ := he
State after:
case cons.cons.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝¹ : Walk G v✝ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ v'}, concat p✝¹ h = concat p' h' → ∃ hv, Walk.copy p✝¹ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ w
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : HEq (concat p✝¹ h) (concat p✝ h')
⊢ ∃ hv, Walk.copy (cons h✝¹ p✝¹) (_ : u✝ = u✝) hv = cons h✝ p✝

State before:
case cons.cons.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝¹ : Walk G v✝ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ v'}, concat p✝¹ h = concat p' h' → ∃ hv, Walk.copy p✝¹ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ w
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : HEq (concat p✝¹ h) (concat p✝ h')
⊢ ∃ hv, Walk.copy (cons h✝¹ p✝¹) (_ : u✝ = u✝) hv = cons h✝ p✝
Tactic:
rw [heq_iff_eq] at he
State after:
case cons.cons.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝¹ : Walk G v✝ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ v'}, concat p✝¹ h = concat p' h' → ∃ hv, Walk.copy p✝¹ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ w
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : concat p✝¹ h = concat p✝ h'
⊢ ∃ hv, Walk.copy (cons h✝¹ p✝¹) (_ : u✝ = u✝) hv = cons h✝ p✝

State before:
case cons.cons.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v v' w : V
h' : G.Adj v' w
u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝¹ : Walk G v✝ w✝
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ v'}, concat p✝¹ h = concat p' h' → ∃ hv, Walk.copy p✝¹ (_ : v✝ = v✝) hv = p'
h : G.Adj w✝ w
h✝ : G.Adj u✝ v✝
p✝ : Walk G v✝ v'
he : concat p✝¹ h = concat p✝ h'
⊢ ∃ hv, Walk.copy (cons h✝¹ p✝¹) (_ : u✝ = u✝) hv = cons h✝ p✝
Tactic:
obtain ⟨rfl, rfl⟩ := ih he
State after:
case cons.cons.intro.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v w u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
h : G.Adj w✝ w
h✝ : G.Adj u✝ v✝
h' : G.Adj w✝ w
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ w✝}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
he : concat p✝ h = concat (Walk.copy p✝ (_ : v✝ = v✝) (_ : w✝ = w✝)) h'
⊢ ∃ hv, Walk.copy (cons h✝¹ p✝) (_ : u✝ = u✝) hv = cons h✝ (Walk.copy p✝ (_ : v✝ = v✝) (_ : w✝ = w✝))

State before:
case cons.cons.intro.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
u v w u✝ v✝ w✝ : V
h✝¹ : G.Adj u✝ v✝
p✝ : Walk G v✝ w✝
h : G.Adj w✝ w
h✝ : G.Adj u✝ v✝
h' : G.Adj w✝ w
ih : ∀ {h : G.Adj w✝ w} {p' : Walk G v✝ w✝}, concat p✝ h = concat p' h' → ∃ hv, Walk.copy p✝ (_ : v✝ = v✝) hv = p'
he : concat p✝ h = concat (Walk.copy p✝ (_ : v✝ = v✝) (_ : w✝ = w✝)) h'
⊢ ∃ hv, Walk.copy (cons h✝¹ p✝) (_ : u✝ = u✝) hv = cons h✝ (Walk.copy p✝ (_ : v✝ = v✝) (_ : w✝ = w✝))
Tactic:
exact ⟨rfl, rfl⟩
State after:
no goals