Metamath Proof Explorer

Theorem eupthp1

Description: Append one path segment to an Eulerian path <. F , P >. to become an Eulerian path <. H , Q >. of the supergraph S obtained by adding the new edge to the graph G . (Contributed by Mario Carneiro, 7-Apr-2015) (Revised by AV, 7-Mar-2021) (Proof shortened by AV, 30-Oct-2021) (Revised by AV, 8-Apr-2024)

Ref Expression
Hypotheses eupthp1.v ⊢ 𝑉 = ( Vtx ‘ 𝐺 )
eupthp1.i ⊢ 𝐼 = ( iEdg ‘ 𝐺 )
eupthp1.f ⊢ ( 𝜑 → Fun 𝐼 )
eupthp1.a ⊢ ( 𝜑 → 𝐼 ∈ Fin )
eupthp1.b ⊢ ( 𝜑 → 𝐵 ∈ 𝑊 )
eupthp1.c ⊢ ( 𝜑 → 𝐶 ∈ 𝑉 )
eupthp1.d ⊢ ( 𝜑 → ¬ 𝐵 ∈ dom 𝐼 )
eupthp1.p ⊢ ( 𝜑 → 𝐹 ( EulerPaths ‘ 𝐺 ) 𝑃 )
eupthp1.n ⊢ 𝑁 = ( ♯ ‘ 𝐹 )
eupthp1.e ⊢ ( 𝜑 → 𝐸 ∈ ( Edg ‘ 𝐺 ) )
eupthp1.x ⊢ ( 𝜑 → { ( 𝑃 ‘ 𝑁 ) , 𝐶 } ⊆ 𝐸 )
eupthp1.u ⊢ ( iEdg ‘ 𝑆 ) = ( 𝐼 ∪ { ⟨ 𝐵 , 𝐸 ⟩ } )
eupthp1.h ⊢ 𝐻 = ( 𝐹 ∪ { ⟨ 𝑁 , 𝐵 ⟩ } )
eupthp1.q ⊢ 𝑄 = ( 𝑃 ∪ { ⟨ ( 𝑁 + 1 ) , 𝐶 ⟩ } )
eupthp1.s ⊢ ( Vtx ‘ 𝑆 ) = 𝑉
eupthp1.l ⊢ ( ( 𝜑 ∧ 𝐶 = ( 𝑃 ‘ 𝑁 ) ) → 𝐸 = { 𝐶 } )
Assertion eupthp1 ( 𝜑 → 𝐻 ( EulerPaths ‘ 𝑆 ) 𝑄 )

Proof

Step Hyp Ref Expression
1 eupthp1.v ⊢ 𝑉 = ( Vtx ‘ 𝐺 )
2 eupthp1.i ⊢ 𝐼 = ( iEdg ‘ 𝐺 )
3 eupthp1.f ⊢ ( 𝜑 → Fun 𝐼 )
4 eupthp1.a ⊢ ( 𝜑 → 𝐼 ∈ Fin )
5 eupthp1.b ⊢ ( 𝜑 → 𝐵 ∈ 𝑊 )
6 eupthp1.c ⊢ ( 𝜑 → 𝐶 ∈ 𝑉 )
7 eupthp1.d ⊢ ( 𝜑 → ¬ 𝐵 ∈ dom 𝐼 )
8 eupthp1.p ⊢ ( 𝜑 → 𝐹 ( EulerPaths ‘ 𝐺 ) 𝑃 )
9 eupthp1.n ⊢ 𝑁 = ( ♯ ‘ 𝐹 )
10 eupthp1.e ⊢ ( 𝜑 → 𝐸 ∈ ( Edg ‘ 𝐺 ) )
11 eupthp1.x ⊢ ( 𝜑 → { ( 𝑃 ‘ 𝑁 ) , 𝐶 } ⊆ 𝐸 )
12 eupthp1.u ⊢ ( iEdg ‘ 𝑆 ) = ( 𝐼 ∪ { ⟨ 𝐵 , 𝐸 ⟩ } )
13 eupthp1.h ⊢ 𝐻 = ( 𝐹 ∪ { ⟨ 𝑁 , 𝐵 ⟩ } )
14 eupthp1.q ⊢ 𝑄 = ( 𝑃 ∪ { ⟨ ( 𝑁 + 1 ) , 𝐶 ⟩ } )
15 eupthp1.s ⊢ ( Vtx ‘ 𝑆 ) = 𝑉
16 eupthp1.l ⊢ ( ( 𝜑 ∧ 𝐶 = ( 𝑃 ‘ 𝑁 ) ) → 𝐸 = { 𝐶 } )
17 eupthiswlk ⊢ ( 𝐹 ( EulerPaths ‘ 𝐺 ) 𝑃 → 𝐹 ( Walks ‘ 𝐺 ) 𝑃 )
18 8 17 syl ⊢ ( 𝜑 → 𝐹 ( Walks ‘ 𝐺 ) 𝑃 )
19 12 a1i ⊢ ( 𝜑 → ( iEdg ‘ 𝑆 ) = ( 𝐼 ∪ { ⟨ 𝐵 , 𝐸 ⟩ } ) )
20 15 a1i ⊢ ( 𝜑 → ( Vtx ‘ 𝑆 ) = 𝑉 )
21 1 2 3 4 5 6 7 18 9 10 11 19 13 14 20 16 wlkp1 ⊢ ( 𝜑 → 𝐻 ( Walks ‘ 𝑆 ) 𝑄 )
22 2 eupthi ⊢ ( 𝐹 ( EulerPaths ‘ 𝐺 ) 𝑃 → ( 𝐹 ( Walks ‘ 𝐺 ) 𝑃 ∧ 𝐹 : ( 0 ..^ ( ♯ ‘ 𝐹 ) ) –1-1-onto→ dom 𝐼 ) )
23 9 eqcomi ⊢ ( ♯ ‘ 𝐹 ) = 𝑁
24 23 oveq2i ⊢ ( 0 ..^ ( ♯ ‘ 𝐹 ) ) = ( 0 ..^ 𝑁 )
25 f1oeq2 ⊢ ( ( 0 ..^ ( ♯ ‘ 𝐹 ) ) = ( 0 ..^ 𝑁 ) → ( 𝐹 : ( 0 ..^ ( ♯ ‘ 𝐹 ) ) –1-1-onto→ dom 𝐼 ↔ 𝐹 : ( 0 ..^ 𝑁 ) –1-1-onto→ dom 𝐼 ) )
26 24 25 ax-mp ⊢ ( 𝐹 : ( 0 ..^ ( ♯ ‘ 𝐹 ) ) –1-1-onto→ dom 𝐼 ↔ 𝐹 : ( 0 ..^ 𝑁 ) –1-1-onto→ dom 𝐼 )
27 26 bilani ⊢ ( ( 𝐹 ( Walks ‘ 𝐺 ) 𝑃 ∧ 𝐹 : ( 0 ..^ ( ♯ ‘ 𝐹 ) ) –1-1-onto→ dom 𝐼 ) → 𝐹 : ( 0 ..^ 𝑁 ) –1-1-onto→ dom 𝐼 )
28 8 22 27 3syl ⊢ ( 𝜑 → 𝐹 : ( 0 ..^ 𝑁 ) –1-1-onto→ dom 𝐼 )
29 9 fvexi ⊢ 𝑁 ∈ V
30 f1osng ⊢ ( ( 𝑁 ∈ V ∧ 𝐵 ∈ 𝑊 ) → { ⟨ 𝑁 , 𝐵 ⟩ } : { 𝑁 } –1-1-onto→ { 𝐵 } )
31 29 5 30 sylancr ⊢ ( 𝜑 → { ⟨ 𝑁 , 𝐵 ⟩ } : { 𝑁 } –1-1-onto→ { 𝐵 } )
32 dmsnopg ⊢ ( 𝐸 ∈ ( Edg ‘ 𝐺 ) → dom { ⟨ 𝐵 , 𝐸 ⟩ } = { 𝐵 } )
33 10 32 syl ⊢ ( 𝜑 → dom { ⟨ 𝐵 , 𝐸 ⟩ } = { 𝐵 } )
34 33 f1oeq3d ⊢ ( 𝜑 → ( { ⟨ 𝑁 , 𝐵 ⟩ } : { 𝑁 } –1-1-onto→ dom { ⟨ 𝐵 , 𝐸 ⟩ } ↔ { ⟨ 𝑁 , 𝐵 ⟩ } : { 𝑁 } –1-1-onto→ { 𝐵 } ) )
35 31 34 mpbird ⊢ ( 𝜑 → { ⟨ 𝑁 , 𝐵 ⟩ } : { 𝑁 } –1-1-onto→ dom { ⟨ 𝐵 , 𝐸 ⟩ } )
36 fzodisjsn ⊢ ( ( 0 ..^ 𝑁 ) ∩ { 𝑁 } ) = ∅
37 36 a1i ⊢ ( 𝜑 → ( ( 0 ..^ 𝑁 ) ∩ { 𝑁 } ) = ∅ )
38 33 ineq2d ⊢ ( 𝜑 → ( dom 𝐼 ∩ dom { ⟨ 𝐵 , 𝐸 ⟩ } ) = ( dom 𝐼 ∩ { 𝐵 } ) )
39 disjsn ⊢ ( ( dom 𝐼 ∩ { 𝐵 } ) = ∅ ↔ ¬ 𝐵 ∈ dom 𝐼 )
40 7 39 sylibr ⊢ ( 𝜑 → ( dom 𝐼 ∩ { 𝐵 } ) = ∅ )
41 38 40 eqtrd ⊢ ( 𝜑 → ( dom 𝐼 ∩ dom { ⟨ 𝐵 , 𝐸 ⟩ } ) = ∅ )
42 f1oun ⊢ ( ( ( 𝐹 : ( 0 ..^ 𝑁 ) –1-1-onto→ dom 𝐼 ∧ { ⟨ 𝑁 , 𝐵 ⟩ } : { 𝑁 } –1-1-onto→ dom { ⟨ 𝐵 , 𝐸 ⟩ } ) ∧ ( ( ( 0 ..^ 𝑁 ) ∩ { 𝑁 } ) = ∅ ∧ ( dom 𝐼 ∩ dom { ⟨ 𝐵 , 𝐸 ⟩ } ) = ∅ ) ) → ( 𝐹 ∪ { ⟨ 𝑁 , 𝐵 ⟩ } ) : ( ( 0 ..^ 𝑁 ) ∪ { 𝑁 } ) –1-1-onto→ ( dom 𝐼 ∪ dom { ⟨ 𝐵 , 𝐸 ⟩ } ) )
43 28 35 37 41 42 syl22anc ⊢ ( 𝜑 → ( 𝐹 ∪ { ⟨ 𝑁 , 𝐵 ⟩ } ) : ( ( 0 ..^ 𝑁 ) ∪ { 𝑁 } ) –1-1-onto→ ( dom 𝐼 ∪ dom { ⟨ 𝐵 , 𝐸 ⟩ } ) )
44 13 a1i ⊢ ( 𝜑 → 𝐻 = ( 𝐹 ∪ { ⟨ 𝑁 , 𝐵 ⟩ } ) )
45 1 2 3 4 5 6 7 18 9 10 11 19 13 wlkp1lem2 ⊢ ( 𝜑 → ( ♯ ‘ 𝐻 ) = ( 𝑁 + 1 ) )
46 45 oveq2d ⊢ ( 𝜑 → ( 0 ..^ ( ♯ ‘ 𝐻 ) ) = ( 0 ..^ ( 𝑁 + 1 ) ) )
47 wlkcl ⊢ ( 𝐹 ( Walks ‘ 𝐺 ) 𝑃 → ( ♯ ‘ 𝐹 ) ∈ ℕ0 )
48 9 eleq1i ⊢ ( 𝑁 ∈ ℕ0 ↔ ( ♯ ‘ 𝐹 ) ∈ ℕ0 )
49 elnn0uz ⊢ ( 𝑁 ∈ ℕ0 ↔ 𝑁 ∈ ( ℤ≥ ‘ 0 ) )
50 48 49 sylbb1 ⊢ ( ( ♯ ‘ 𝐹 ) ∈ ℕ0 → 𝑁 ∈ ( ℤ≥ ‘ 0 ) )
51 47 50 syl ⊢ ( 𝐹 ( Walks ‘ 𝐺 ) 𝑃 → 𝑁 ∈ ( ℤ≥ ‘ 0 ) )
52 8 17 51 3syl ⊢ ( 𝜑 → 𝑁 ∈ ( ℤ≥ ‘ 0 ) )
53 fzosplitsn ⊢ ( 𝑁 ∈ ( ℤ≥ ‘ 0 ) → ( 0 ..^ ( 𝑁 + 1 ) ) = ( ( 0 ..^ 𝑁 ) ∪ { 𝑁 } ) )
54 52 53 syl ⊢ ( 𝜑 → ( 0 ..^ ( 𝑁 + 1 ) ) = ( ( 0 ..^ 𝑁 ) ∪ { 𝑁 } ) )
55 46 54 eqtrd ⊢ ( 𝜑 → ( 0 ..^ ( ♯ ‘ 𝐻 ) ) = ( ( 0 ..^ 𝑁 ) ∪ { 𝑁 } ) )
56 dmun ⊢ dom ( 𝐼 ∪ { ⟨ 𝐵 , 𝐸 ⟩ } ) = ( dom 𝐼 ∪ dom { ⟨ 𝐵 , 𝐸 ⟩ } )
57 56 a1i ⊢ ( 𝜑 → dom ( 𝐼 ∪ { ⟨ 𝐵 , 𝐸 ⟩ } ) = ( dom 𝐼 ∪ dom { ⟨ 𝐵 , 𝐸 ⟩ } ) )
58 44 55 57 f1oeq123d ⊢ ( 𝜑 → ( 𝐻 : ( 0 ..^ ( ♯ ‘ 𝐻 ) ) –1-1-onto→ dom ( 𝐼 ∪ { ⟨ 𝐵 , 𝐸 ⟩ } ) ↔ ( 𝐹 ∪ { ⟨ 𝑁 , 𝐵 ⟩ } ) : ( ( 0 ..^ 𝑁 ) ∪ { 𝑁 } ) –1-1-onto→ ( dom 𝐼 ∪ dom { ⟨ 𝐵 , 𝐸 ⟩ } ) ) )
59 43 58 mpbird ⊢ ( 𝜑 → 𝐻 : ( 0 ..^ ( ♯ ‘ 𝐻 ) ) –1-1-onto→ dom ( 𝐼 ∪ { ⟨ 𝐵 , 𝐸 ⟩ } ) )
60 12 eqcomi ⊢ ( 𝐼 ∪ { ⟨ 𝐵 , 𝐸 ⟩ } ) = ( iEdg ‘ 𝑆 )
61 60 iseupthf1o ⊢ ( 𝐻 ( EulerPaths ‘ 𝑆 ) 𝑄 ↔ ( 𝐻 ( Walks ‘ 𝑆 ) 𝑄 ∧ 𝐻 : ( 0 ..^ ( ♯ ‘ 𝐻 ) ) –1-1-onto→ dom ( 𝐼 ∪ { ⟨ 𝐵 , 𝐸 ⟩ } ) ) )
62 21 59 61 sylanbrc ⊢ ( 𝜑 → 𝐻 ( EulerPaths ‘ 𝑆 ) 𝑄 )