Theorem: Graph.cancelling_steps_redCons (GroupComp/Graph/ReducedPaths.lean)

State before:
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
⊢ redCons (EdgeBetween.bar e) (redCons e p) = p
Tactic:
cases prepend_cases e p with
| inl h =>
    rw [h]
    apply redCons_cons_edge_eq
    simp [bar_bar]
| inr h =>
    let ⟨t, h₁, h₂⟩ := h
    rw[h₂, h₁]
    cases prepend_cases e.bar t with
    | inl h' =>
      assumption
    | inr h' =>
      let ⟨t', h₁', h₂'⟩ := h'
      rw [h₂', h₁']
      rw [h₁, h₁'] at hyp
      simp [bar_bar] at *
      have split :
                cons e.bar (cons e t') =
                  (nil v : EdgePath G v v) ++
                    cons e.bar (cons e.bar.bar t') := by
                  simp [nil_append]
      have :¬ reduced (cons e.bar (cons e t')) := by
        apply not_reduced_of_split split
      contradiction
State after:
no goals

State before:
case inl
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : redCons e p = cons e p
⊢ redCons (EdgeBetween.bar e) (redCons e p) = p
Tactic:
rw [h]
State after:
case inl
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : redCons e p = cons e p
⊢ redCons (EdgeBetween.bar e) (cons e p) = p

State before:
case inl
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : redCons e p = cons e p
⊢ redCons (EdgeBetween.bar e) (cons e p) = p
Tactic:
apply redCons_cons_edge_eq
State after:
case inl.h
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : redCons e p = cons e p
⊢ e = EdgeBetween.bar (EdgeBetween.bar e)

State before:
case inl.h
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : redCons e p = cons e p
⊢ e = EdgeBetween.bar (EdgeBetween.bar e)
Tactic:
simp [bar_bar]
State after:
no goals

State before:
case inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : ∃ t, p = cons (EdgeBetween.bar e) t ∧ redCons e p = t
⊢ redCons (EdgeBetween.bar e) (redCons e p) = p
Tactic:
let ⟨t, h₁, h₂⟩ := h
State after:
case inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : ∃ t, p = cons (EdgeBetween.bar e) t ∧ redCons e p = t
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
⊢ redCons (EdgeBetween.bar e) (redCons e p) = p

State before:
case inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : ∃ t, p = cons (EdgeBetween.bar e) t ∧ redCons e p = t
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
⊢ redCons (EdgeBetween.bar e) (redCons e p) = p
Tactic:
rw[h₂, h₁]
State after:
case inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : ∃ t, p = cons (EdgeBetween.bar e) t ∧ redCons e p = t
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
⊢ redCons (EdgeBetween.bar e) t = cons (EdgeBetween.bar e) t

State before:
case inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : ∃ t, p = cons (EdgeBetween.bar e) t ∧ redCons e p = t
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
⊢ redCons (EdgeBetween.bar e) t = cons (EdgeBetween.bar e) t
Tactic:
cases prepend_cases e.bar t with
| inl h' =>
  assumption
| inr h' =>
  let ⟨t', h₁', h₂'⟩ := h'
  rw [h₂', h₁']
  rw [h₁, h₁'] at hyp
  simp [bar_bar] at *
  have split :
            cons e.bar (cons e t') =
              (nil v : EdgePath G v v) ++
                cons e.bar (cons e.bar.bar t') := by
              simp [nil_append]
  have :¬ reduced (cons e.bar (cons e t')) := by
    apply not_reduced_of_split split
  contradiction
State after:
no goals

State before:
case inr.inl
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : ∃ t, p = cons (EdgeBetween.bar e) t ∧ redCons e p = t
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
h' : redCons (EdgeBetween.bar e) t = cons (EdgeBetween.bar e) t
⊢ redCons (EdgeBetween.bar e) t = cons (EdgeBetween.bar e) t
Tactic:
assumption
State after:
no goals

State before:
case inr.inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : ∃ t, p = cons (EdgeBetween.bar e) t ∧ redCons e p = t
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
h' : ∃ t_1, t = cons (EdgeBetween.bar (EdgeBetween.bar e)) t_1 ∧ redCons (EdgeBetween.bar e) t = t_1
⊢ redCons (EdgeBetween.bar e) t = cons (EdgeBetween.bar e) t
Tactic:
let ⟨t', h₁', h₂'⟩ := h'
State after:
case inr.inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : ∃ t, p = cons (EdgeBetween.bar e) t ∧ redCons e p = t
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
h' : ∃ t_1, t = cons (EdgeBetween.bar (EdgeBetween.bar e)) t_1 ∧ redCons (EdgeBetween.bar e) t = t_1
t' : EdgePath G v w
h₁' : t = cons (EdgeBetween.bar (EdgeBetween.bar e)) t'
h₂' : redCons (EdgeBetween.bar e) t = t'
⊢ redCons (EdgeBetween.bar e) t = cons (EdgeBetween.bar e) t

State before:
case inr.inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : ∃ t, p = cons (EdgeBetween.bar e) t ∧ redCons e p = t
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
h' : ∃ t_1, t = cons (EdgeBetween.bar (EdgeBetween.bar e)) t_1 ∧ redCons (EdgeBetween.bar e) t = t_1
t' : EdgePath G v w
h₁' : t = cons (EdgeBetween.bar (EdgeBetween.bar e)) t'
h₂' : redCons (EdgeBetween.bar e) t = t'
⊢ redCons (EdgeBetween.bar e) t = cons (EdgeBetween.bar e) t
Tactic:
rw [h₂', h₁']
State after:
case inr.inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : ∃ t, p = cons (EdgeBetween.bar e) t ∧ redCons e p = t
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
h' : ∃ t_1, t = cons (EdgeBetween.bar (EdgeBetween.bar e)) t_1 ∧ redCons (EdgeBetween.bar e) t = t_1
t' : EdgePath G v w
h₁' : t = cons (EdgeBetween.bar (EdgeBetween.bar e)) t'
h₂' : redCons (EdgeBetween.bar e) t = t'
⊢ t' = cons (EdgeBetween.bar e) (cons (EdgeBetween.bar (EdgeBetween.bar e)) t')

State before:
case inr.inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
hyp : reduced p
h : ∃ t, p = cons (EdgeBetween.bar e) t ∧ redCons e p = t
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
h' : ∃ t_1, t = cons (EdgeBetween.bar (EdgeBetween.bar e)) t_1 ∧ redCons (EdgeBetween.bar e) t = t_1
t' : EdgePath G v w
h₁' : t = cons (EdgeBetween.bar (EdgeBetween.bar e)) t'
h₂' : redCons (EdgeBetween.bar e) t = t'
⊢ t' = cons (EdgeBetween.bar e) (cons (EdgeBetween.bar (EdgeBetween.bar e)) t')
Tactic:
rw [h₁, h₁'] at hyp
State after:
case inr.inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
h : ∃ t, p = cons (EdgeBetween.bar e) t ∧ redCons e p = t
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
h' : ∃ t_1, t = cons (EdgeBetween.bar (EdgeBetween.bar e)) t_1 ∧ redCons (EdgeBetween.bar e) t = t_1
t' : EdgePath G v w
hyp : reduced (cons (EdgeBetween.bar e) (cons (EdgeBetween.bar (EdgeBetween.bar e)) t'))
h₁' : t = cons (EdgeBetween.bar (EdgeBetween.bar e)) t'
h₂' : redCons (EdgeBetween.bar e) t = t'
⊢ t' = cons (EdgeBetween.bar e) (cons (EdgeBetween.bar (EdgeBetween.bar e)) t')

State before:
case inr.inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
h : ∃ t, p = cons (EdgeBetween.bar e) t ∧ redCons e p = t
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
h' : ∃ t_1, t = cons (EdgeBetween.bar (EdgeBetween.bar e)) t_1 ∧ redCons (EdgeBetween.bar e) t = t_1
t' : EdgePath G v w
hyp : reduced (cons (EdgeBetween.bar e) (cons (EdgeBetween.bar (EdgeBetween.bar e)) t'))
h₁' : t = cons (EdgeBetween.bar (EdgeBetween.bar e)) t'
h₂' : redCons (EdgeBetween.bar e) t = t'
⊢ t' = cons (EdgeBetween.bar e) (cons (EdgeBetween.bar (EdgeBetween.bar e)) t')
Tactic:
simp [bar_bar] at *
State after:
case inr.inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
t' : EdgePath G v w
h₂' : redCons (EdgeBetween.bar e) t = t'
h : p = cons (EdgeBetween.bar e) (redCons e p)
h' : t = cons e (redCons (EdgeBetween.bar e) t)
hyp : reduced (cons (EdgeBetween.bar e) (cons e t'))
h₁' : t = cons e t'
⊢ t' = cons (EdgeBetween.bar e) (cons e t')

State before:
case inr.inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
t' : EdgePath G v w
h₂' : redCons (EdgeBetween.bar e) t = t'
h : p = cons (EdgeBetween.bar e) (redCons e p)
h' : t = cons e (redCons (EdgeBetween.bar e) t)
hyp : reduced (cons (EdgeBetween.bar e) (cons e t'))
h₁' : t = cons e t'
⊢ t' = cons (EdgeBetween.bar e) (cons e t')
Tactic:
have split :
          cons e.bar (cons e t') =
            (nil v : EdgePath G v v) ++
              cons e.bar (cons e.bar.bar t') := by
            simp [nil_append]
State after:
case inr.inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
t' : EdgePath G v w
h₂' : redCons (EdgeBetween.bar e) t = t'
h : p = cons (EdgeBetween.bar e) (redCons e p)
h' : t = cons e (redCons (EdgeBetween.bar e) t)
hyp : reduced (cons (EdgeBetween.bar e) (cons e t'))
h₁' : t = cons e t'
split :
  cons (EdgeBetween.bar e) (cons e t') =
    nil v ++ cons (EdgeBetween.bar e) (cons (EdgeBetween.bar (EdgeBetween.bar e)) t')
⊢ t' = cons (EdgeBetween.bar e) (cons e t')

State before:
case inr.inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
t' : EdgePath G v w
h₂' : redCons (EdgeBetween.bar e) t = t'
h : p = cons (EdgeBetween.bar e) (redCons e p)
h' : t = cons e (redCons (EdgeBetween.bar e) t)
hyp : reduced (cons (EdgeBetween.bar e) (cons e t'))
h₁' : t = cons e t'
split :
  cons (EdgeBetween.bar e) (cons e t') =
    nil v ++ cons (EdgeBetween.bar e) (cons (EdgeBetween.bar (EdgeBetween.bar e)) t')
⊢ t' = cons (EdgeBetween.bar e) (cons e t')
Tactic:
have :¬ reduced (cons e.bar (cons e t')) := by
  apply not_reduced_of_split split
State after:
case inr.inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
t' : EdgePath G v w
h₂' : redCons (EdgeBetween.bar e) t = t'
h : p = cons (EdgeBetween.bar e) (redCons e p)
h' : t = cons e (redCons (EdgeBetween.bar e) t)
hyp : reduced (cons (EdgeBetween.bar e) (cons e t'))
h₁' : t = cons e t'
split :
  cons (EdgeBetween.bar e) (cons e t') =
    nil v ++ cons (EdgeBetween.bar e) (cons (EdgeBetween.bar (EdgeBetween.bar e)) t')
this : ¬reduced (cons (EdgeBetween.bar e) (cons e t'))
⊢ t' = cons (EdgeBetween.bar e) (cons e t')

State before:
case inr.inr
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
t' : EdgePath G v w
h₂' : redCons (EdgeBetween.bar e) t = t'
h : p = cons (EdgeBetween.bar e) (redCons e p)
h' : t = cons e (redCons (EdgeBetween.bar e) t)
hyp : reduced (cons (EdgeBetween.bar e) (cons e t'))
h₁' : t = cons e t'
split :
  cons (EdgeBetween.bar e) (cons e t') =
    nil v ++ cons (EdgeBetween.bar e) (cons (EdgeBetween.bar (EdgeBetween.bar e)) t')
this : ¬reduced (cons (EdgeBetween.bar e) (cons e t'))
⊢ t' = cons (EdgeBetween.bar e) (cons e t')
Tactic:
contradiction
State after:
no goals

State before:
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
t' : EdgePath G v w
h₂' : redCons (EdgeBetween.bar e) t = t'
h : p = cons (EdgeBetween.bar e) (redCons e p)
h' : t = cons e (redCons (EdgeBetween.bar e) t)
hyp : reduced (cons (EdgeBetween.bar e) (cons e t'))
h₁' : t = cons e t'
⊢ cons (EdgeBetween.bar e) (cons e t') =
    nil v ++ cons (EdgeBetween.bar e) (cons (EdgeBetween.bar (EdgeBetween.bar e)) t')
Tactic:
simp [nil_append]
State after:
no goals

State before:
V : Type u
E : Type v
inst✝¹ : DecidableEq V
inst✝ : DecidableEq E
G : Graph V E
u v w : V
e : EdgeBetween G u v
p : EdgePath G v w
t : EdgePath G u w
h₁ : p = cons (EdgeBetween.bar e) t
h₂ : redCons e p = t
t' : EdgePath G v w
h₂' : redCons (EdgeBetween.bar e) t = t'
h : p = cons (EdgeBetween.bar e) (redCons e p)
h' : t = cons e (redCons (EdgeBetween.bar e) t)
hyp : reduced (cons (EdgeBetween.bar e) (cons e t'))
h₁' : t = cons e t'
split :
  cons (EdgeBetween.bar e) (cons e t') =
    nil v ++ cons (EdgeBetween.bar e) (cons (EdgeBetween.bar (EdgeBetween.bar e)) t')
⊢ ¬reduced (cons (EdgeBetween.bar e) (cons e t'))
Tactic:
apply not_reduced_of_split split
State after:
no goals