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

State before:
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x : V
⊢ List.count (u, x) (edges (takeUntil p u h)) = 0
Tactic:
induction' p with u' u' v' w' ha p' ih
State after:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h✝ : u ∈ support p
x u' : V
h : u ∈ support nil
⊢ List.count (u, x) (edges (takeUntil nil u h)) = 0

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 w : V
p : Walk G v w
h✝ : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
h : u ∈ support (cons ha p')
⊢ List.count (u, x) (edges (takeUntil (cons ha p') u h)) = 0

State before:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h✝ : u ∈ support p
x u' : V
h : u ∈ support nil
⊢ List.count (u, x) (edges (takeUntil nil u h)) = 0
Tactic:
rw [mem_support_nil_iff] at h
State after:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h✝¹ : u ∈ support p
x u' : V
h✝ : u ∈ support nil
h : u = u'
⊢ List.count (u, x) (edges (takeUntil nil u h✝)) = 0

State before:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h✝¹ : u ∈ support p
x u' : V
h✝ : u ∈ support nil
h : u = u'
⊢ List.count (u, x) (edges (takeUntil nil u h✝)) = 0
Tactic:
subst u
State after:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
v w : V
p : Walk G v w
x u' : V
h✝ : u' ∈ support p
h : u' ∈ support nil
⊢ List.count (u', x) (edges (takeUntil nil u' h)) = 0

State before:
case nil
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
v w : V
p : Walk G v w
x u' : V
h✝ : u' ∈ support p
h : u' ∈ support nil
⊢ List.count (u', x) (edges (takeUntil nil u' h)) = 0
Tactic:
simp!
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''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h✝ : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
h : u ∈ support (cons ha p')
⊢ List.count (u, x) (edges (takeUntil (cons ha p') u h)) = 0
Tactic:
cases h
State after:
case cons.head
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x v' w' : V
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
ha : G.Adj u v'
⊢ List.count (u, x) (edges (takeUntil (cons ha p') u (_ : List.Mem u (u :: support p')))) = 0

case cons.tail
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
⊢ List.count (u, x) (edges (takeUntil (cons ha p') u (_ : List.Mem u (u' :: support p')))) = 0

State before:
case cons.head
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x v' w' : V
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
ha : G.Adj u v'
⊢ List.count (u, x) (edges (takeUntil (cons ha p') u (_ : List.Mem u (u :: support p')))) = 0
Tactic:
simp!
State after:
no goals

State before:
case cons.tail
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
⊢ List.count (u, x) (edges (takeUntil (cons ha p') u (_ : List.Mem u (u' :: support p')))) = 0
Tactic:
simp! only
State after:
case cons.tail
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
⊢ List.count (u, x)
      (edges
        (if h : u' = u then
          Eq.rec (motive := fun x x_1 => x ∈ u' :: support p' → Walk G u' x) (fun h => nil) (_ : u' = u)
            (_ : List.Mem u (u' :: support p'))
        else cons ha (takeUntil p' u (_ : u ∈ support p')))) =
    0

State before:
case cons.tail
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
⊢ List.count (u, x)
      (edges
        (if h : u' = u then
          Eq.rec (motive := fun x x_1 => x ∈ u' :: support p' → Walk G u' x) (fun h => nil) (_ : u' = u)
            (_ : List.Mem u (u' :: support p'))
        else cons ha (takeUntil p' u (_ : u ∈ support p')))) =
    0
Tactic:
split_ifs with h'
State after:
case cons.tail.inl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : u' = u
⊢ List.count (u, x)
      (edges
        (Eq.rec (motive := fun x x_1 => x ∈ u' :: support p' → Walk G u' x) (fun h => nil) (_ : u' = u)
          (_ : List.Mem u (u' :: support p')))) =
    0

case cons.tail.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : ¬u' = u
⊢ List.count (u, x) (edges (cons ha (takeUntil p' u (_ : u ∈ support p')))) = 0

State before:
case cons.tail.inl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : u' = u
⊢ List.count (u, x)
      (edges
        (Eq.rec (motive := fun x x_1 => x ∈ u' :: support p' → Walk G u' x) (fun h => nil) (_ : u' = u)
          (_ : List.Mem u (u' :: support p')))) =
    0
Tactic:
subst h'
State after:
case cons.tail.inl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
v w : V
p : Walk G v w
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
h : u' ∈ support p
ih : ∀ (h : u' ∈ support p'), List.count (u', x) (edges (takeUntil p' u' h)) = 0
a✝ : List.Mem u' (support p')
⊢ List.count (u', x)
      (edges
        (Eq.rec (motive := fun x x_1 => x ∈ u' :: support p' → Walk G u' x) (fun h => nil) (_ : u' = u')
          (_ : List.Mem u' (u' :: support p')))) =
    0

State before:
case cons.tail.inl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
v w : V
p : Walk G v w
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
h : u' ∈ support p
ih : ∀ (h : u' ∈ support p'), List.count (u', x) (edges (takeUntil p' u' h)) = 0
a✝ : List.Mem u' (support p')
⊢ List.count (u', x)
      (edges
        (Eq.rec (motive := fun x x_1 => x ∈ u' :: support p' → Walk G u' x) (fun h => nil) (_ : u' = u')
          (_ : List.Mem u' (u' :: support p')))) =
    0
Tactic:
simp
State after:
no goals

State before:
case cons.tail.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : ¬u' = u
⊢ List.count (u, x) (edges (cons ha (takeUntil p' u (_ : u ∈ support p')))) = 0
Tactic:
rw [edges_cons]
State after:
case cons.tail.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : ¬u' = u
⊢ List.count (u, x) ((u', v') :: edges (takeUntil p' u (_ : u ∈ support p'))) = 0

State before:
case cons.tail.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : ¬u' = u
⊢ List.count (u, x) ((u', v') :: edges (takeUntil p' u (_ : u ∈ support p'))) = 0
Tactic:
simp only [List.count_prod_eq, List.count_cons]
State after:
case cons.tail.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : ¬u' = u
⊢ (if (u, x) = (u', v') then Nat.succ (List.count (u, x) (edges (takeUntil p' u (_ : u ∈ support p'))))
    else List.count (u, x) (edges (takeUntil p' u (_ : u ∈ support p')))) =
    0

State before:
case cons.tail.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : ¬u' = u
⊢ (if (u, x) = (u', v') then Nat.succ (List.count (u, x) (edges (takeUntil p' u (_ : u ∈ support p'))))
    else List.count (u, x) (edges (takeUntil p' u (_ : u ∈ support p')))) =
    0
Tactic:
split_ifs with h''
State after:
case cons.tail.inr.inl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : ¬u' = u
h'' : (u, x) = (u', v')
⊢ False

case cons.tail.inr.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : ¬u' = u
h'' : ¬(u, x) = (u', v')
⊢ List.count (u, x) (edges (takeUntil p' u (_ : u ∈ support p'))) = 0

State before:
case cons.tail.inr.inl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : ¬u' = u
h'' : (u, x) = (u', v')
⊢ False
Tactic:
simp at h''
State after:
case cons.tail.inr.inl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : ¬u' = u
h'' : u = u' ∧ x = v'
⊢ False

State before:
case cons.tail.inr.inl
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : ¬u' = u
h'' : u = u' ∧ x = v'
⊢ False
Tactic:
obtain ⟨rfl, rfl⟩ := h''
State after:
case cons.tail.inr.inl.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x w' : V
h' : ¬u = u
p' : Walk G x w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
ha : G.Adj u x
⊢ False

State before:
case cons.tail.inr.inl.intro
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x w' : V
h' : ¬u = u
p' : Walk G x w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
ha : G.Adj u x
⊢ False
Tactic:
exact (h' rfl).elim
State after:
no goals

State before:
case cons.tail.inr.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
a✝ : List.Mem u (support p')
h' : ¬u' = u
h'' : ¬(u, x) = (u', v')
⊢ List.count (u, x) (edges (takeUntil p' u (_ : u ∈ support p'))) = 0
Tactic:
simp only [List.count_prod_eq] at ih
State after:
case cons.tail.inr.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
a✝ : List.Mem u (support p')
h' : ¬u' = u
h'' : ¬(u, x) = (u', v')
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
⊢ List.count (u, x) (edges (takeUntil p' u (_ : u ∈ support p'))) = 0

State before:
case cons.tail.inr.inr
V : Type u
V' : Type v
V'' : Type w
G : Digraph V
G' : Digraph V'
G'' : Digraph V''
inst✝ : DecidableEq V
u v w : V
p : Walk G v w
h : u ∈ support p
x u' v' w' : V
ha : G.Adj u' v'
p' : Walk G v' w'
a✝ : List.Mem u (support p')
h' : ¬u' = u
h'' : ¬(u, x) = (u', v')
ih : ∀ (h : u ∈ support p'), List.count (u, x) (edges (takeUntil p' u h)) = 0
⊢ List.count (u, x) (edges (takeUntil p' u (_ : u ∈ support p'))) = 0
Tactic:
apply ih
State after:
no goals