Theorem eupth2lem3fi 16458

Description: Lemma for eupth2fi 16461. (Contributed by Mario Carneiro, 8-Apr-2015.) (Revised by AV, 26-Feb-2021.)

Hypotheses

Ref	Expression
eupth2.v	⊢ 𝑉 = (Vtx‘𝐺)
eupth2.i	⊢ 𝐼 = (iEdg‘𝐺)
eupth2fi.g	⊢ (𝜑 → 𝐺 ∈ UMGraph)
eupth2.f	⊢ (𝜑 → Fun 𝐼)
eupth2.p	⊢ (𝜑 → 𝐹(EulerPaths‘𝐺)𝑃)
eupth2fi.fi	⊢ (𝜑 → 𝑉 ∈ Fin)
eupth2.h	⊢ 𝐻 = ⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑁)))⟩
eupth2.x	⊢ 𝑋 = ⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1))))⟩
eupth2.n	⊢ (𝜑 → 𝑁 ∈ ℕ0)
eupth2.l	⊢ (𝜑 → (𝑁 + 1) ≤ (♯‘𝐹))
eupth2.u	⊢ (𝜑 → 𝑈 ∈ 𝑉)
eupth2.o	⊢ (𝜑 → {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘𝐻)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑁), ∅, {(𝑃‘0), (𝑃‘𝑁)}))

Assertion

Ref	Expression
eupth2lem3fi	⊢ (𝜑 → (¬ 2 ∥ ((VtxDeg‘𝑋)‘𝑈) ↔ 𝑈 ∈ if((𝑃‘0) = (𝑃‘(𝑁 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑁 + 1))})))

Distinct variable groups:   𝑥,𝐻   𝑥,𝑈   𝑥,𝑉

Allowed substitution hints:   𝜑(𝑥)   𝑃(𝑥)   𝐹(𝑥)   𝐺(𝑥)   𝐼(𝑥)   𝑁(𝑥)   𝑋(𝑥)

Proof of Theorem eupth2lem3fi

Dummy variable 𝑘 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		eupth2.v	. 2 ⊢ 𝑉 = (Vtx‘𝐺)
2		eupth2.i	. 2 ⊢ 𝐼 = (iEdg‘𝐺)
3		eupth2.f	. 2 ⊢ (𝜑 → Fun 𝐼)
4		eupth2.n	. . 3 ⊢ (𝜑 → 𝑁 ∈ ℕ0)
5		eupth2.p	. . . 4 ⊢ (𝜑 → 𝐹(EulerPaths‘𝐺)𝑃)
6		eupthiswlk 16437	. . . 4 ⊢ (𝐹(EulerPaths‘𝐺)𝑃 → 𝐹(Walks‘𝐺)𝑃)
7		wlkcl 16314	. . . 4 ⊢ (𝐹(Walks‘𝐺)𝑃 → (♯‘𝐹) ∈ ℕ0)
8	5, 6, 7	3syl 17	. . 3 ⊢ (𝜑 → (♯‘𝐹) ∈ ℕ0)
9		eupth2.l	. . 3 ⊢ (𝜑 → (𝑁 + 1) ≤ (♯‘𝐹))
10		nn0p1elfzo 10517	. . 3 ⊢ ((𝑁 ∈ ℕ0 ∧ (♯‘𝐹) ∈ ℕ0 ∧ (𝑁 + 1) ≤ (♯‘𝐹)) → 𝑁 ∈ (0..^(♯‘𝐹)))
11	4, 8, 9, 10	syl3anc 1274	. 2 ⊢ (𝜑 → 𝑁 ∈ (0..^(♯‘𝐹)))
12		eupth2.u	. 2 ⊢ (𝜑 → 𝑈 ∈ 𝑉)
13		eupthistrl 16436	. . 3 ⊢ (𝐹(EulerPaths‘𝐺)𝑃 → 𝐹(Trails‘𝐺)𝑃)
14	5, 13	syl 14	. 2 ⊢ (𝜑 → 𝐹(Trails‘𝐺)𝑃)
15		eupth2.h	. . . 4 ⊢ 𝐻 = ⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑁)))⟩
16	15	fveq2i 5672	. . 3 ⊢ (Vtx‘𝐻) = (Vtx‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑁)))⟩)
17		eupth2fi.fi	. . . . 5 ⊢ (𝜑 → 𝑉 ∈ Fin)
18	17	elexd 2826	. . . 4 ⊢ (𝜑 → 𝑉 ∈ V)
19		eupth2fi.g	. . . . . . 7 ⊢ (𝜑 → 𝐺 ∈ UMGraph)
20		iedgex 16001	. . . . . . 7 ⊢ (𝐺 ∈ UMGraph → (iEdg‘𝐺) ∈ V)
21	19, 20	syl 14	. . . . . 6 ⊢ (𝜑 → (iEdg‘𝐺) ∈ V)
22	2, 21	eqeltrid 2319	. . . . 5 ⊢ (𝜑 → 𝐼 ∈ V)
23		resexg 5077	. . . . 5 ⊢ (𝐼 ∈ V → (𝐼 ↾ (𝐹 “ (0..^𝑁))) ∈ V)
24	22, 23	syl 14	. . . 4 ⊢ (𝜑 → (𝐼 ↾ (𝐹 “ (0..^𝑁))) ∈ V)
25		opvtxfv 16004	. . . 4 ⊢ ((𝑉 ∈ V ∧ (𝐼 ↾ (𝐹 “ (0..^𝑁))) ∈ V) → (Vtx‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑁)))⟩) = 𝑉)
26	18, 24, 25	syl2anc 411	. . 3 ⊢ (𝜑 → (Vtx‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑁)))⟩) = 𝑉)
27	16, 26	eqtrid 2277	. 2 ⊢ (𝜑 → (Vtx‘𝐻) = 𝑉)
28		eupthv 16428	. . . . . . . 8 ⊢ (𝐹(EulerPaths‘𝐺)𝑃 → (𝐺 ∈ V ∧ 𝐹 ∈ V ∧ 𝑃 ∈ V))
29	5, 28	syl 14	. . . . . . 7 ⊢ (𝜑 → (𝐺 ∈ V ∧ 𝐹 ∈ V ∧ 𝑃 ∈ V))
30	29	simp2d 1037	. . . . . 6 ⊢ (𝜑 → 𝐹 ∈ V)
31		fvexg 5688	. . . . . 6 ⊢ ((𝐹 ∈ V ∧ 𝑁 ∈ ℕ0) → (𝐹‘𝑁) ∈ V)
32	30, 4, 31	syl2anc 411	. . . . 5 ⊢ (𝜑 → (𝐹‘𝑁) ∈ V)
33		fvexg 5688	. . . . . 6 ⊢ ((𝐼 ∈ V ∧ (𝐹‘𝑁) ∈ V) → (𝐼‘(𝐹‘𝑁)) ∈ V)
34	22, 32, 33	syl2anc 411	. . . . 5 ⊢ (𝜑 → (𝐼‘(𝐹‘𝑁)) ∈ V)
35		opexg 4343	. . . . 5 ⊢ (((𝐹‘𝑁) ∈ V ∧ (𝐼‘(𝐹‘𝑁)) ∈ V) → ⟨(𝐹‘𝑁), (𝐼‘(𝐹‘𝑁))⟩ ∈ V)
36	32, 34, 35	syl2anc 411	. . . 4 ⊢ (𝜑 → ⟨(𝐹‘𝑁), (𝐼‘(𝐹‘𝑁))⟩ ∈ V)
37		snexg 4296	. . . 4 ⊢ (⟨(𝐹‘𝑁), (𝐼‘(𝐹‘𝑁))⟩ ∈ V → {⟨(𝐹‘𝑁), (𝐼‘(𝐹‘𝑁))⟩} ∈ V)
38	36, 37	syl 14	. . 3 ⊢ (𝜑 → {⟨(𝐹‘𝑁), (𝐼‘(𝐹‘𝑁))⟩} ∈ V)
39		opvtxfv 16004	. . 3 ⊢ ((𝑉 ∈ V ∧ {⟨(𝐹‘𝑁), (𝐼‘(𝐹‘𝑁))⟩} ∈ V) → (Vtx‘⟨𝑉, {⟨(𝐹‘𝑁), (𝐼‘(𝐹‘𝑁))⟩}⟩) = 𝑉)
40	18, 38, 39	syl2anc 411	. 2 ⊢ (𝜑 → (Vtx‘⟨𝑉, {⟨(𝐹‘𝑁), (𝐼‘(𝐹‘𝑁))⟩}⟩) = 𝑉)
41		eupth2.x	. . . 4 ⊢ 𝑋 = ⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1))))⟩
42	41	fveq2i 5672	. . 3 ⊢ (Vtx‘𝑋) = (Vtx‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1))))⟩)
43		resexg 5077	. . . . 5 ⊢ (𝐼 ∈ V → (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1)))) ∈ V)
44	22, 43	syl 14	. . . 4 ⊢ (𝜑 → (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1)))) ∈ V)
45		opvtxfv 16004	. . . 4 ⊢ ((𝑉 ∈ V ∧ (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1)))) ∈ V) → (Vtx‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1))))⟩) = 𝑉)
46	18, 44, 45	syl2anc 411	. . 3 ⊢ (𝜑 → (Vtx‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1))))⟩) = 𝑉)
47	42, 46	eqtrid 2277	. 2 ⊢ (𝜑 → (Vtx‘𝑋) = 𝑉)
48	15	fveq2i 5672	. . 3 ⊢ (iEdg‘𝐻) = (iEdg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑁)))⟩)
49		opiedgfv 16007	. . . 4 ⊢ ((𝑉 ∈ V ∧ (𝐼 ↾ (𝐹 “ (0..^𝑁))) ∈ V) → (iEdg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑁)))⟩) = (𝐼 ↾ (𝐹 “ (0..^𝑁))))
50	18, 24, 49	syl2anc 411	. . 3 ⊢ (𝜑 → (iEdg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^𝑁)))⟩) = (𝐼 ↾ (𝐹 “ (0..^𝑁))))
51	48, 50	eqtrid 2277	. 2 ⊢ (𝜑 → (iEdg‘𝐻) = (𝐼 ↾ (𝐹 “ (0..^𝑁))))
52		opiedgfv 16007	. . 3 ⊢ ((𝑉 ∈ V ∧ {⟨(𝐹‘𝑁), (𝐼‘(𝐹‘𝑁))⟩} ∈ V) → (iEdg‘⟨𝑉, {⟨(𝐹‘𝑁), (𝐼‘(𝐹‘𝑁))⟩}⟩) = {⟨(𝐹‘𝑁), (𝐼‘(𝐹‘𝑁))⟩})
53	18, 38, 52	syl2anc 411	. 2 ⊢ (𝜑 → (iEdg‘⟨𝑉, {⟨(𝐹‘𝑁), (𝐼‘(𝐹‘𝑁))⟩}⟩) = {⟨(𝐹‘𝑁), (𝐼‘(𝐹‘𝑁))⟩})
54	41	fveq2i 5672	. . . 4 ⊢ (iEdg‘𝑋) = (iEdg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1))))⟩)
55		opiedgfv 16007	. . . . 5 ⊢ ((𝑉 ∈ V ∧ (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1)))) ∈ V) → (iEdg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1))))⟩) = (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1)))))
56	18, 44, 55	syl2anc 411	. . . 4 ⊢ (𝜑 → (iEdg‘⟨𝑉, (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1))))⟩) = (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1)))))
57	54, 56	eqtrid 2277	. . 3 ⊢ (𝜑 → (iEdg‘𝑋) = (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1)))))
58	4	nn0zd 9694	. . . . . 6 ⊢ (𝜑 → 𝑁 ∈ ℤ)
59		fzval3 10545	. . . . . . 7 ⊢ (𝑁 ∈ ℤ → (0...𝑁) = (0..^(𝑁 + 1)))
60	59	eqcomd 2238	. . . . . 6 ⊢ (𝑁 ∈ ℤ → (0..^(𝑁 + 1)) = (0...𝑁))
61	58, 60	syl 14	. . . . 5 ⊢ (𝜑 → (0..^(𝑁 + 1)) = (0...𝑁))
62	61	imaeq2d 5100	. . . 4 ⊢ (𝜑 → (𝐹 “ (0..^(𝑁 + 1))) = (𝐹 “ (0...𝑁)))
63	62	reseq2d 5037	. . 3 ⊢ (𝜑 → (𝐼 ↾ (𝐹 “ (0..^(𝑁 + 1)))) = (𝐼 ↾ (𝐹 “ (0...𝑁))))
64	57, 63	eqtrd 2265	. 2 ⊢ (𝜑 → (iEdg‘𝑋) = (𝐼 ↾ (𝐹 “ (0...𝑁))))
65		eupth2.o	. 2 ⊢ (𝜑 → {𝑥 ∈ 𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘𝐻)‘𝑥)} = if((𝑃‘0) = (𝑃‘𝑁), ∅, {(𝑃‘0), (𝑃‘𝑁)}))
66		2fveq3 5674	. . . 4 ⊢ (𝑘 = 𝑁 → (𝐼‘(𝐹‘𝑘)) = (𝐼‘(𝐹‘𝑁)))
67		fveq2 5669	. . . . 5 ⊢ (𝑘 = 𝑁 → (𝑃‘𝑘) = (𝑃‘𝑁))
68		fvoveq1 6072	. . . . 5 ⊢ (𝑘 = 𝑁 → (𝑃‘(𝑘 + 1)) = (𝑃‘(𝑁 + 1)))
69	67, 68	preq12d 3775	. . . 4 ⊢ (𝑘 = 𝑁 → {(𝑃‘𝑘), (𝑃‘(𝑘 + 1))} = {(𝑃‘𝑁), (𝑃‘(𝑁 + 1))})
70	66, 69	eqeq12d 2247	. . 3 ⊢ (𝑘 = 𝑁 → ((𝐼‘(𝐹‘𝑘)) = {(𝑃‘𝑘), (𝑃‘(𝑘 + 1))} ↔ (𝐼‘(𝐹‘𝑁)) = {(𝑃‘𝑁), (𝑃‘(𝑁 + 1))}))
71		umgrupgr 16094	. . . . 5 ⊢ (𝐺 ∈ UMGraph → 𝐺 ∈ UPGraph)
72	19, 71	syl 14	. . . 4 ⊢ (𝜑 → 𝐺 ∈ UPGraph)
73	5, 6	syl 14	. . . 4 ⊢ (𝜑 → 𝐹(Walks‘𝐺)𝑃)
74	2	upgrwlkedg 16343	. . . 4 ⊢ ((𝐺 ∈ UPGraph ∧ 𝐹(Walks‘𝐺)𝑃) → ∀𝑘 ∈ (0..^(♯‘𝐹))(𝐼‘(𝐹‘𝑘)) = {(𝑃‘𝑘), (𝑃‘(𝑘 + 1))})
75	72, 73, 74	syl2anc 411	. . 3 ⊢ (𝜑 → ∀𝑘 ∈ (0..^(♯‘𝐹))(𝐼‘(𝐹‘𝑘)) = {(𝑃‘𝑘), (𝑃‘(𝑘 + 1))})
76	70, 75, 11	rspcdva 2925	. 2 ⊢ (𝜑 → (𝐼‘(𝐹‘𝑁)) = {(𝑃‘𝑁), (𝑃‘(𝑁 + 1))})
77	1, 2, 3, 11, 12, 14, 27, 40, 47, 51, 53, 64, 19, 17, 65, 76	eupth2lem3lem7fi 16456	1 ⊢ (𝜑 → (¬ 2 ∥ ((VtxDeg‘𝑋)‘𝑈) ↔ 𝑈 ∈ if((𝑃‘0) = (𝑃‘(𝑁 + 1)), ∅, {(𝑃‘0), (𝑃‘(𝑁 + 1))})))

Syntax hints:  ¬ wn 3   → wi 4   ↔ wb 105   ∧ w3a 1005   = wceq 1398   ∈ wcel 2203  ∀wral 2520  {crab 2524  Vcvv 2812  ∅c0 3507  ifcif 3619  {csn 3688  {cpr 3689  ⟨cop 3691   class class class wbr 4108   ↾ cres 4750   “ cima 4751  Fun wfun 5345  ‘cfv 5351  (class class class)co 6049  Fincfn 6974  0cc0 8123  1c1 8124   + caddc 8126   ≤ cle 8305  2c2 9284  ℕ₀cn0 9492  ℤcz 9573  ...cfz 10338  ..^cfzo 10472  ♯chash 11133   ∥ cdvds 12466  Vtxcvtx 15994  iEdgciedg 15995  UPGraphcupgr 16073  UMGraphcumgr 16074  VtxDegcvtxdg 16268  Walkscwlks 16299  Trailsctrls 16362  EulerPathsceupth 16424

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 619  ax-in2 620  ax-io 717  ax-5 1496  ax-7 1497  ax-gen 1498  ax-ie1 1542  ax-ie2 1543  ax-8 1553  ax-10 1554  ax-11 1555  ax-i12 1556  ax-bndl 1558  ax-4 1559  ax-17 1575  ax-i9 1579  ax-ial 1583  ax-i5r 1584  ax-13 2205  ax-14 2206  ax-ext 2214  ax-coll 4224  ax-sep 4227  ax-nul 4235  ax-pow 4286  ax-pr 4321  ax-un 4553  ax-setind 4658  ax-iinf 4709  ax-cnex 8214  ax-resscn 8215  ax-1cn 8216  ax-1re 8217  ax-icn 8218  ax-addcl 8219  ax-addrcl 8220  ax-mulcl 8221  ax-mulrcl 8222  ax-addcom 8223  ax-mulcom 8224  ax-addass 8225  ax-mulass 8226  ax-distr 8227  ax-i2m1 8228  ax-0lt1 8229  ax-1rid 8230  ax-0id 8231  ax-rnegex 8232  ax-precex 8233  ax-cnre 8234  ax-pre-ltirr 8235  ax-pre-ltwlin 8236  ax-pre-lttrn 8237  ax-pre-apti 8238  ax-pre-ltadd 8239  ax-pre-mulgt0 8240  ax-pre-mulext 8241  ax-arch 8242

This theorem depends on definitions:  df-bi 117  df-stab 839  df-dc 843  df-ifp 987  df-3or 1006  df-3an 1007  df-tru 1401  df-fal 1404  df-xor 1421  df-nf 1510  df-sb 1812  df-eu 2083  df-mo 2084  df-clab 2219  df-cleq 2225  df-clel 2228  df-nfc 2373  df-ne 2413  df-nel 2508  df-ral 2525  df-rex 2526  df-reu 2527  df-rmo 2528  df-rab 2529  df-v 2814  df-sbc 3042  df-csb 3138  df-dif 3212  df-un 3214  df-in 3216  df-ss 3223  df-nul 3508  df-if 3620  df-pw 3670  df-sn 3694  df-pr 3695  df-op 3697  df-uni 3914  df-int 3949  df-iun 3992  df-br 4109  df-opab 4171  df-mpt 4172  df-tr 4208  df-id 4413  df-po 4416  df-iso 4417  df-iord 4486  df-on 4488  df-ilim 4489  df-suc 4491  df-iom 4712  df-xp 4754  df-rel 4755  df-cnv 4756  df-co 4757  df-dm 4758  df-rn 4759  df-res 4760  df-ima 4761  df-iota 5311  df-fun 5353  df-fn 5354  df-f 5355  df-f1 5356  df-fo 5357  df-f1o 5358  df-fv 5359  df-riota 6002  df-ov 6052  df-oprab 6053  df-mpo 6054  df-1st 6333  df-2nd 6334  df-recs 6535  df-irdg 6600  df-frec 6621  df-1o 6646  df-2o 6647  df-oadd 6650  df-er 6766  df-map 6883  df-en 6975  df-dom 6976  df-fin 6977  df-pnf 8306  df-mnf 8307  df-xr 8308  df-ltxr 8309  df-le 8310  df-sub 8442  df-neg 8443  df-reap 8845  df-ap 8852  df-div 8943  df-inn 9234  df-2 9292  df-3 9293  df-4 9294  df-5 9295  df-6 9296  df-7 9297  df-8 9298  df-9 9299  df-n0 9493  df-z 9574  df-dec 9706  df-uz 9850  df-q 9948  df-rp 9983  df-xadd 10102  df-fz 10339  df-fzo 10473  df-fl 10626  df-mod 10681  df-seqfrec 10806  df-exp 10897  df-ihash 11134  df-word 11218  df-cj 11520  df-re 11521  df-im 11522  df-rsqrt 11676  df-abs 11677  df-dvds 12467  df-ndx 13204  df-slot 13205  df-base 13207  df-edgf 15987  df-vtx 15996  df-iedg 15997  df-edg 16040  df-uhgrm 16051  df-ushgrm 16052  df-upgren 16075  df-umgren 16076  df-uspgren 16137  df-subgr 16236  df-vtxdg 16269  df-wlks 16300  df-trls 16363  df-eupth 16425

This theorem is referenced by:  eupth2lemsfi  16460