Metamath Proof Explorer

Theorem trlsegvdeg

Description: The effect on vertex degree of adding one edge to a trail.. In the following, a subgraph induced by a segment of a trail is called a "subtrail": For any subtrail Z of a trail <. F , P >. in a pseudograph G which is composed of subtrails X and Y , where Y consists of a single edge, the vertex degree of any vertex U within Z is the sum of the vertex degree of U within X and the vertex degree of U within Y . Note that this theorem would not hold for arbitrary walks (if the last edge was identical with a previous edge, the degree of the vertices incident with this edge would not be increased because of this edge). (Contributed by Mario Carneiro, 8-Apr-2015) Formerly part of proof of eupth2lem3 . (Revised by AV, 20-Feb-2021)

Ref Expression
Hypotheses trlsegvdeg.v ⊢ 𝑉 = ( Vtx ‘ 𝐺 )
trlsegvdeg.i ⊢ 𝐼 = ( iEdg ‘ 𝐺 )
trlsegvdeg.f ⊢ ( 𝜑 → Fun 𝐼 )
trlsegvdeg.n ⊢ ( 𝜑 → 𝑁 ∈ ( 0 ..^ ( ♯ ‘ 𝐹 ) ) )
trlsegvdeg.u ⊢ ( 𝜑 → 𝑈 ∈ 𝑉 )
trlsegvdeg.w ⊢ ( 𝜑 → 𝐹 ( Trails ‘ 𝐺 ) 𝑃 )
trlsegvdeg.vx ⊢ ( 𝜑 → ( Vtx ‘ 𝑋 ) = 𝑉 )
trlsegvdeg.vy ⊢ ( 𝜑 → ( Vtx ‘ 𝑌 ) = 𝑉 )
trlsegvdeg.vz ⊢ ( 𝜑 → ( Vtx ‘ 𝑍 ) = 𝑉 )
trlsegvdeg.ix ⊢ ( 𝜑 → ( iEdg ‘ 𝑋 ) = ( 𝐼 ↾ ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ) )
trlsegvdeg.iy ⊢ ( 𝜑 → ( iEdg ‘ 𝑌 ) = { ⟨ ( 𝐹 ‘ 𝑁 ) , ( 𝐼 ‘ ( 𝐹 ‘ 𝑁 ) ) ⟩ } )
trlsegvdeg.iz ⊢ ( 𝜑 → ( iEdg ‘ 𝑍 ) = ( 𝐼 ↾ ( 𝐹 “ ( 0 ... 𝑁 ) ) ) )
Assertion trlsegvdeg ( 𝜑 → ( ( VtxDeg ‘ 𝑍 ) ‘ 𝑈 ) = ( ( ( VtxDeg ‘ 𝑋 ) ‘ 𝑈 ) + ( ( VtxDeg ‘ 𝑌 ) ‘ 𝑈 ) ) )

Proof

Step Hyp Ref Expression
1 trlsegvdeg.v ⊢ 𝑉 = ( Vtx ‘ 𝐺 )
2 trlsegvdeg.i ⊢ 𝐼 = ( iEdg ‘ 𝐺 )
3 trlsegvdeg.f ⊢ ( 𝜑 → Fun 𝐼 )
4 trlsegvdeg.n ⊢ ( 𝜑 → 𝑁 ∈ ( 0 ..^ ( ♯ ‘ 𝐹 ) ) )
5 trlsegvdeg.u ⊢ ( 𝜑 → 𝑈 ∈ 𝑉 )
6 trlsegvdeg.w ⊢ ( 𝜑 → 𝐹 ( Trails ‘ 𝐺 ) 𝑃 )
7 trlsegvdeg.vx ⊢ ( 𝜑 → ( Vtx ‘ 𝑋 ) = 𝑉 )
8 trlsegvdeg.vy ⊢ ( 𝜑 → ( Vtx ‘ 𝑌 ) = 𝑉 )
9 trlsegvdeg.vz ⊢ ( 𝜑 → ( Vtx ‘ 𝑍 ) = 𝑉 )
10 trlsegvdeg.ix ⊢ ( 𝜑 → ( iEdg ‘ 𝑋 ) = ( 𝐼 ↾ ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ) )
11 trlsegvdeg.iy ⊢ ( 𝜑 → ( iEdg ‘ 𝑌 ) = { ⟨ ( 𝐹 ‘ 𝑁 ) , ( 𝐼 ‘ ( 𝐹 ‘ 𝑁 ) ) ⟩ } )
12 trlsegvdeg.iz ⊢ ( 𝜑 → ( iEdg ‘ 𝑍 ) = ( 𝐼 ↾ ( 𝐹 “ ( 0 ... 𝑁 ) ) ) )
13 eqid ⊢ ( iEdg ‘ 𝑋 ) = ( iEdg ‘ 𝑋 )
14 eqid ⊢ ( iEdg ‘ 𝑌 ) = ( iEdg ‘ 𝑌 )
15 eqid ⊢ ( Vtx ‘ 𝑋 ) = ( Vtx ‘ 𝑋 )
16 8 7 eqtr4d ⊢ ( 𝜑 → ( Vtx ‘ 𝑌 ) = ( Vtx ‘ 𝑋 ) )
17 9 7 eqtr4d ⊢ ( 𝜑 → ( Vtx ‘ 𝑍 ) = ( Vtx ‘ 𝑋 ) )
18 1 2 3 4 5 6 7 8 9 10 11 12 trlsegvdeglem4 ⊢ ( 𝜑 → dom ( iEdg ‘ 𝑋 ) = ( ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ∩ dom 𝐼 ) )
19 1 2 3 4 5 6 7 8 9 10 11 12 trlsegvdeglem5 ⊢ ( 𝜑 → dom ( iEdg ‘ 𝑌 ) = { ( 𝐹 ‘ 𝑁 ) } )
20 18 19 ineq12d ⊢ ( 𝜑 → ( dom ( iEdg ‘ 𝑋 ) ∩ dom ( iEdg ‘ 𝑌 ) ) = ( ( ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ∩ dom 𝐼 ) ∩ { ( 𝐹 ‘ 𝑁 ) } ) )
21 fzonel ⊢ ¬ 𝑁 ∈ ( 0 ..^ 𝑁 )
22 2 trlf1 ⊢ ( 𝐹 ( Trails ‘ 𝐺 ) 𝑃 → 𝐹 : ( 0 ..^ ( ♯ ‘ 𝐹 ) ) –1-1→ dom 𝐼 )
23 6 22 syl ⊢ ( 𝜑 → 𝐹 : ( 0 ..^ ( ♯ ‘ 𝐹 ) ) –1-1→ dom 𝐼 )
24 elfzouz2 ⊢ ( 𝑁 ∈ ( 0 ..^ ( ♯ ‘ 𝐹 ) ) → ( ♯ ‘ 𝐹 ) ∈ ( ℤ≥ ‘ 𝑁 ) )
25 fzoss2 ⊢ ( ( ♯ ‘ 𝐹 ) ∈ ( ℤ≥ ‘ 𝑁 ) → ( 0 ..^ 𝑁 ) ⊆ ( 0 ..^ ( ♯ ‘ 𝐹 ) ) )
26 4 24 25 3syl ⊢ ( 𝜑 → ( 0 ..^ 𝑁 ) ⊆ ( 0 ..^ ( ♯ ‘ 𝐹 ) ) )
27 f1elima ⊢ ( ( 𝐹 : ( 0 ..^ ( ♯ ‘ 𝐹 ) ) –1-1→ dom 𝐼 ∧ 𝑁 ∈ ( 0 ..^ ( ♯ ‘ 𝐹 ) ) ∧ ( 0 ..^ 𝑁 ) ⊆ ( 0 ..^ ( ♯ ‘ 𝐹 ) ) ) → ( ( 𝐹 ‘ 𝑁 ) ∈ ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ↔ 𝑁 ∈ ( 0 ..^ 𝑁 ) ) )
28 23 4 26 27 syl3anc ⊢ ( 𝜑 → ( ( 𝐹 ‘ 𝑁 ) ∈ ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ↔ 𝑁 ∈ ( 0 ..^ 𝑁 ) ) )
29 21 28 mtbiri ⊢ ( 𝜑 → ¬ ( 𝐹 ‘ 𝑁 ) ∈ ( 𝐹 “ ( 0 ..^ 𝑁 ) ) )
30 29 orcd ⊢ ( 𝜑 → ( ¬ ( 𝐹 ‘ 𝑁 ) ∈ ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ∨ ¬ ( 𝐹 ‘ 𝑁 ) ∈ dom 𝐼 ) )
31 ianor ⊢ ( ¬ ( ( 𝐹 ‘ 𝑁 ) ∈ ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ∧ ( 𝐹 ‘ 𝑁 ) ∈ dom 𝐼 ) ↔ ( ¬ ( 𝐹 ‘ 𝑁 ) ∈ ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ∨ ¬ ( 𝐹 ‘ 𝑁 ) ∈ dom 𝐼 ) )
32 elin ⊢ ( ( 𝐹 ‘ 𝑁 ) ∈ ( ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ∩ dom 𝐼 ) ↔ ( ( 𝐹 ‘ 𝑁 ) ∈ ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ∧ ( 𝐹 ‘ 𝑁 ) ∈ dom 𝐼 ) )
33 31 32 xchnxbir ⊢ ( ¬ ( 𝐹 ‘ 𝑁 ) ∈ ( ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ∩ dom 𝐼 ) ↔ ( ¬ ( 𝐹 ‘ 𝑁 ) ∈ ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ∨ ¬ ( 𝐹 ‘ 𝑁 ) ∈ dom 𝐼 ) )
34 30 33 sylibr ⊢ ( 𝜑 → ¬ ( 𝐹 ‘ 𝑁 ) ∈ ( ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ∩ dom 𝐼 ) )
35 disjsn ⊢ ( ( ( ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ∩ dom 𝐼 ) ∩ { ( 𝐹 ‘ 𝑁 ) } ) = ∅ ↔ ¬ ( 𝐹 ‘ 𝑁 ) ∈ ( ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ∩ dom 𝐼 ) )
36 34 35 sylibr ⊢ ( 𝜑 → ( ( ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ∩ dom 𝐼 ) ∩ { ( 𝐹 ‘ 𝑁 ) } ) = ∅ )
37 20 36 eqtrd ⊢ ( 𝜑 → ( dom ( iEdg ‘ 𝑋 ) ∩ dom ( iEdg ‘ 𝑌 ) ) = ∅ )
38 1 2 3 4 5 6 7 8 9 10 11 12 trlsegvdeglem2 ⊢ ( 𝜑 → Fun ( iEdg ‘ 𝑋 ) )
39 1 2 3 4 5 6 7 8 9 10 11 12 trlsegvdeglem3 ⊢ ( 𝜑 → Fun ( iEdg ‘ 𝑌 ) )
40 5 7 eleqtrrd ⊢ ( 𝜑 → 𝑈 ∈ ( Vtx ‘ 𝑋 ) )
41 f1f ⊢ ( 𝐹 : ( 0 ..^ ( ♯ ‘ 𝐹 ) ) –1-1→ dom 𝐼 → 𝐹 : ( 0 ..^ ( ♯ ‘ 𝐹 ) ) ⟶ dom 𝐼 )
42 6 22 41 3syl ⊢ ( 𝜑 → 𝐹 : ( 0 ..^ ( ♯ ‘ 𝐹 ) ) ⟶ dom 𝐼 )
43 3 42 4 resunimafz0 ⊢ ( 𝜑 → ( 𝐼 ↾ ( 𝐹 “ ( 0 ... 𝑁 ) ) ) = ( ( 𝐼 ↾ ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ) ∪ { ⟨ ( 𝐹 ‘ 𝑁 ) , ( 𝐼 ‘ ( 𝐹 ‘ 𝑁 ) ) ⟩ } ) )
44 10 11 uneq12d ⊢ ( 𝜑 → ( ( iEdg ‘ 𝑋 ) ∪ ( iEdg ‘ 𝑌 ) ) = ( ( 𝐼 ↾ ( 𝐹 “ ( 0 ..^ 𝑁 ) ) ) ∪ { ⟨ ( 𝐹 ‘ 𝑁 ) , ( 𝐼 ‘ ( 𝐹 ‘ 𝑁 ) ) ⟩ } ) )
45 43 12 44 3eqtr4d ⊢ ( 𝜑 → ( iEdg ‘ 𝑍 ) = ( ( iEdg ‘ 𝑋 ) ∪ ( iEdg ‘ 𝑌 ) ) )
46 1 2 3 4 5 6 7 8 9 10 11 12 trlsegvdeglem6 ⊢ ( 𝜑 → dom ( iEdg ‘ 𝑋 ) ∈ Fin )
47 1 2 3 4 5 6 7 8 9 10 11 12 trlsegvdeglem7 ⊢ ( 𝜑 → dom ( iEdg ‘ 𝑌 ) ∈ Fin )
48 13 14 15 16 17 37 38 39 40 45 46 47 vtxdfiun ⊢ ( 𝜑 → ( ( VtxDeg ‘ 𝑍 ) ‘ 𝑈 ) = ( ( ( VtxDeg ‘ 𝑋 ) ‘ 𝑈 ) + ( ( VtxDeg ‘ 𝑌 ) ‘ 𝑈 ) ) )