Metamath Proof Explorer

Theorem 3pthd

Description: A path of length 3 from one vertex to another vertex via a third vertex. (Contributed by Alexander van der Vekens, 6-Dec-2017) (Revised by AV, 10-Feb-2021) (Revised by AV, 24-Mar-2021)

Ref Expression
Hypotheses 3wlkd.p ⊢ P = ⟨“ ABCD ”⟩
3wlkd.f ⊢ F = ⟨“ JKL ”⟩
3wlkd.s ⊢ φ → A ∈ V ∧ B ∈ V ∧ C ∈ V ∧ D ∈ V
3wlkd.n ⊢ φ → A ≠ B ∧ A ≠ C ∧ B ≠ C ∧ B ≠ D ∧ C ≠ D
3wlkd.e ⊢ φ → A B ⊆ I ⁡ J ∧ B C ⊆ I ⁡ K ∧ C D ⊆ I ⁡ L
3wlkd.v ⊢ V = Vtx ⁡ G
3wlkd.i ⊢ I = iEdg ⁡ G
3trld.n ⊢ φ → J ≠ K ∧ J ≠ L ∧ K ≠ L
Assertion 3pthd ⊢ φ → F Paths ⁡ G P

Proof

Step Hyp Ref Expression
1 3wlkd.p ⊢ P = ⟨“ ABCD ”⟩
2 3wlkd.f ⊢ F = ⟨“ JKL ”⟩
3 3wlkd.s ⊢ φ → A ∈ V ∧ B ∈ V ∧ C ∈ V ∧ D ∈ V
4 3wlkd.n ⊢ φ → A ≠ B ∧ A ≠ C ∧ B ≠ C ∧ B ≠ D ∧ C ≠ D
5 3wlkd.e ⊢ φ → A B ⊆ I ⁡ J ∧ B C ⊆ I ⁡ K ∧ C D ⊆ I ⁡ L
6 3wlkd.v ⊢ V = Vtx ⁡ G
7 3wlkd.i ⊢ I = iEdg ⁡ G
8 3trld.n ⊢ φ → J ≠ K ∧ J ≠ L ∧ K ≠ L
9 s4cli ⊢ ⟨“ ABCD ”⟩ ∈ Word V
10 1 9 eqeltri ⊢ P ∈ Word V
11 10 a1i ⊢ φ → P ∈ Word V
12 2 fveq2i ⊢ F = ⟨“ JKL ”⟩
13 s3len ⊢ ⟨“ JKL ”⟩ = 3
14 12 13 eqtri ⊢ F = 3
15 4m1e3 ⊢ 4 − 1 = 3
16 1 fveq2i ⊢ P = ⟨“ ABCD ”⟩
17 s4len ⊢ ⟨“ ABCD ”⟩ = 4
18 16 17 eqtr2i ⊢ 4 = P
19 18 oveq1i ⊢ 4 − 1 = P − 1
20 14 15 19 3eqtr2i ⊢ F = P − 1
21 1 2 3 4 3pthdlem1 ⊢ φ → ∀ k ∈ 0 ..^ P ∀ j ∈ 1 ..^ F k ≠ j → P ⁡ k ≠ P ⁡ j
22 eqid ⊢ F = F
23 1 2 3 4 5 6 7 8 3trld ⊢ φ → F Trails ⁡ G P
24 11 20 21 22 23 pthd ⊢ φ → F Paths ⁡ G P