Metamath Proof Explorer


Theorem 3wlkd

Description: Construction of a walk from two given edges in a graph. (Contributed by AV, 7-Feb-2021) (Revised by AV, 24-Mar-2021)

Ref Expression
Hypotheses 3wlkd.p 𝑃 = ⟨“ 𝐴 𝐵 𝐶 𝐷 ”⟩
3wlkd.f 𝐹 = ⟨“ 𝐽 𝐾 𝐿 ”⟩
3wlkd.s ( 𝜑 → ( ( 𝐴𝑉𝐵𝑉 ) ∧ ( 𝐶𝑉𝐷𝑉 ) ) )
3wlkd.n ( 𝜑 → ( ( 𝐴𝐵𝐴𝐶 ) ∧ ( 𝐵𝐶𝐵𝐷 ) ∧ 𝐶𝐷 ) )
3wlkd.e ( 𝜑 → ( { 𝐴 , 𝐵 } ⊆ ( 𝐼𝐽 ) ∧ { 𝐵 , 𝐶 } ⊆ ( 𝐼𝐾 ) ∧ { 𝐶 , 𝐷 } ⊆ ( 𝐼𝐿 ) ) )
3wlkd.v 𝑉 = ( Vtx ‘ 𝐺 )
3wlkd.i 𝐼 = ( iEdg ‘ 𝐺 )
Assertion 3wlkd ( 𝜑𝐹 ( Walks ‘ 𝐺 ) 𝑃 )

Proof

Step Hyp Ref Expression
1 3wlkd.p 𝑃 = ⟨“ 𝐴 𝐵 𝐶 𝐷 ”⟩
2 3wlkd.f 𝐹 = ⟨“ 𝐽 𝐾 𝐿 ”⟩
3 3wlkd.s ( 𝜑 → ( ( 𝐴𝑉𝐵𝑉 ) ∧ ( 𝐶𝑉𝐷𝑉 ) ) )
4 3wlkd.n ( 𝜑 → ( ( 𝐴𝐵𝐴𝐶 ) ∧ ( 𝐵𝐶𝐵𝐷 ) ∧ 𝐶𝐷 ) )
5 3wlkd.e ( 𝜑 → ( { 𝐴 , 𝐵 } ⊆ ( 𝐼𝐽 ) ∧ { 𝐵 , 𝐶 } ⊆ ( 𝐼𝐾 ) ∧ { 𝐶 , 𝐷 } ⊆ ( 𝐼𝐿 ) ) )
6 3wlkd.v 𝑉 = ( Vtx ‘ 𝐺 )
7 3wlkd.i 𝐼 = ( iEdg ‘ 𝐺 )
8 s4cli ⟨“ 𝐴 𝐵 𝐶 𝐷 ”⟩ ∈ Word V
9 1 8 eqeltri 𝑃 ∈ Word V
10 9 a1i ( 𝜑𝑃 ∈ Word V )
11 s3cli ⟨“ 𝐽 𝐾 𝐿 ”⟩ ∈ Word V
12 2 11 eqeltri 𝐹 ∈ Word V
13 12 a1i ( 𝜑𝐹 ∈ Word V )
14 1 2 3wlkdlem1 ( ♯ ‘ 𝑃 ) = ( ( ♯ ‘ 𝐹 ) + 1 )
15 14 a1i ( 𝜑 → ( ♯ ‘ 𝑃 ) = ( ( ♯ ‘ 𝐹 ) + 1 ) )
16 1 2 3 4 5 3wlkdlem10 ( 𝜑 → ∀ 𝑘 ∈ ( 0 ..^ ( ♯ ‘ 𝐹 ) ) { ( 𝑃𝑘 ) , ( 𝑃 ‘ ( 𝑘 + 1 ) ) } ⊆ ( 𝐼 ‘ ( 𝐹𝑘 ) ) )
17 1 2 3 4 3wlkdlem5 ( 𝜑 → ∀ 𝑘 ∈ ( 0 ..^ ( ♯ ‘ 𝐹 ) ) ( 𝑃𝑘 ) ≠ ( 𝑃 ‘ ( 𝑘 + 1 ) ) )
18 6 1vgrex ( 𝐴𝑉𝐺 ∈ V )
19 18 ad2antrr ( ( ( 𝐴𝑉𝐵𝑉 ) ∧ ( 𝐶𝑉𝐷𝑉 ) ) → 𝐺 ∈ V )
20 3 19 syl ( 𝜑𝐺 ∈ V )
21 1 2 3 3wlkdlem4 ( 𝜑 → ∀ 𝑘 ∈ ( 0 ... ( ♯ ‘ 𝐹 ) ) ( 𝑃𝑘 ) ∈ 𝑉 )
22 10 13 15 16 17 20 6 7 21 wlkd ( 𝜑𝐹 ( Walks ‘ 𝐺 ) 𝑃 )