Metamath Proof Explorer < Previous   Next > Nearby theorems Mirrors  >  Home  >  MPE Home  >  Th. List  >  1pthond Structured version   Visualization version   GIF version

Theorem 1pthond 27521
 Description: In a graph with two vertices and an edge connecting these two vertices, to go from one vertex to the other vertex via this edge is a path from one of these vertices to the other vertex. The two vertices need not be distinct (in the case of a loop) - in this case, however, the path is not a simple path. (Contributed by Alexander van der Vekens, 4-Dec-2017.) (Revised by AV, 22-Jan-2021.) (Revised by AV, 23-Mar-2021.)
Hypotheses
Ref Expression
1wlkd.p 𝑃 = ⟨“𝑋𝑌”⟩
1wlkd.f 𝐹 = ⟨“𝐽”⟩
1wlkd.x (𝜑𝑋𝑉)
1wlkd.y (𝜑𝑌𝑉)
1wlkd.l ((𝜑𝑋 = 𝑌) → (𝐼𝐽) = {𝑋})
1wlkd.j ((𝜑𝑋𝑌) → {𝑋, 𝑌} ⊆ (𝐼𝐽))
1wlkd.v 𝑉 = (Vtx‘𝐺)
1wlkd.i 𝐼 = (iEdg‘𝐺)
Assertion
Ref Expression
1pthond (𝜑𝐹(𝑋(PathsOn‘𝐺)𝑌)𝑃)

Proof of Theorem 1pthond
StepHypRef Expression
1 1wlkd.p . . . . 5 𝑃 = ⟨“𝑋𝑌”⟩
2 1wlkd.f . . . . 5 𝐹 = ⟨“𝐽”⟩
3 1wlkd.x . . . . 5 (𝜑𝑋𝑉)
4 1wlkd.y . . . . 5 (𝜑𝑌𝑉)
5 1wlkd.l . . . . 5 ((𝜑𝑋 = 𝑌) → (𝐼𝐽) = {𝑋})
6 1wlkd.j . . . . 5 ((𝜑𝑋𝑌) → {𝑋, 𝑌} ⊆ (𝐼𝐽))
7 1wlkd.v . . . . 5 𝑉 = (Vtx‘𝐺)
8 1wlkd.i . . . . 5 𝐼 = (iEdg‘𝐺)
91, 2, 3, 4, 5, 6, 7, 81wlkd 27518 . . . 4 (𝜑𝐹(Walks‘𝐺)𝑃)
101fveq1i 6435 . . . . . 6 (𝑃‘0) = (⟨“𝑋𝑌”⟩‘0)
11 s2fv0 14009 . . . . . 6 (𝑋𝑉 → (⟨“𝑋𝑌”⟩‘0) = 𝑋)
1210, 11syl5eq 2874 . . . . 5 (𝑋𝑉 → (𝑃‘0) = 𝑋)
133, 12syl 17 . . . 4 (𝜑 → (𝑃‘0) = 𝑋)
142fveq2i 6437 . . . . . . 7 (♯‘𝐹) = (♯‘⟨“𝐽”⟩)
15 s1len 13667 . . . . . . 7 (♯‘⟨“𝐽”⟩) = 1
1614, 15eqtri 2850 . . . . . 6 (♯‘𝐹) = 1
171, 16fveq12i 6440 . . . . 5 (𝑃‘(♯‘𝐹)) = (⟨“𝑋𝑌”⟩‘1)
18 s2fv1 14010 . . . . . 6 (𝑌𝑉 → (⟨“𝑋𝑌”⟩‘1) = 𝑌)
194, 18syl 17 . . . . 5 (𝜑 → (⟨“𝑋𝑌”⟩‘1) = 𝑌)
2017, 19syl5eq 2874 . . . 4 (𝜑 → (𝑃‘(♯‘𝐹)) = 𝑌)
21 wlkv 26911 . . . . . . 7 (𝐹(Walks‘𝐺)𝑃 → (𝐺 ∈ V ∧ 𝐹 ∈ V ∧ 𝑃 ∈ V))
22 3simpc 1188 . . . . . . 7 ((𝐺 ∈ V ∧ 𝐹 ∈ V ∧ 𝑃 ∈ V) → (𝐹 ∈ V ∧ 𝑃 ∈ V))
239, 21, 223syl 18 . . . . . 6 (𝜑 → (𝐹 ∈ V ∧ 𝑃 ∈ V))
243, 4, 23jca31 512 . . . . 5 (𝜑 → ((𝑋𝑉𝑌𝑉) ∧ (𝐹 ∈ V ∧ 𝑃 ∈ V)))
257iswlkon 26955 . . . . 5 (((𝑋𝑉𝑌𝑉) ∧ (𝐹 ∈ V ∧ 𝑃 ∈ V)) → (𝐹(𝑋(WalksOn‘𝐺)𝑌)𝑃 ↔ (𝐹(Walks‘𝐺)𝑃 ∧ (𝑃‘0) = 𝑋 ∧ (𝑃‘(♯‘𝐹)) = 𝑌)))
2624, 25syl 17 . . . 4 (𝜑 → (𝐹(𝑋(WalksOn‘𝐺)𝑌)𝑃 ↔ (𝐹(Walks‘𝐺)𝑃 ∧ (𝑃‘0) = 𝑋 ∧ (𝑃‘(♯‘𝐹)) = 𝑌)))
279, 13, 20, 26mpbir3and 1448 . . 3 (𝜑𝐹(𝑋(WalksOn‘𝐺)𝑌)𝑃)
281, 2, 3, 4, 5, 6, 7, 81trld 27519 . . 3 (𝜑𝐹(Trails‘𝐺)𝑃)
297istrlson 27010 . . . 4 (((𝑋𝑉𝑌𝑉) ∧ (𝐹 ∈ V ∧ 𝑃 ∈ V)) → (𝐹(𝑋(TrailsOn‘𝐺)𝑌)𝑃 ↔ (𝐹(𝑋(WalksOn‘𝐺)𝑌)𝑃𝐹(Trails‘𝐺)𝑃)))
3024, 29syl 17 . . 3 (𝜑 → (𝐹(𝑋(TrailsOn‘𝐺)𝑌)𝑃 ↔ (𝐹(𝑋(WalksOn‘𝐺)𝑌)𝑃𝐹(Trails‘𝐺)𝑃)))
3127, 28, 30mpbir2and 706 . 2 (𝜑𝐹(𝑋(TrailsOn‘𝐺)𝑌)𝑃)
321, 2, 3, 4, 5, 6, 7, 81pthd 27520 . 2 (𝜑𝐹(Paths‘𝐺)𝑃)
333adantl 475 . . . . . . 7 (((𝐹 ∈ V ∧ 𝑃 ∈ V) ∧ 𝜑) → 𝑋𝑉)
344adantl 475 . . . . . . 7 (((𝐹 ∈ V ∧ 𝑃 ∈ V) ∧ 𝜑) → 𝑌𝑉)
35 simpl 476 . . . . . . 7 (((𝐹 ∈ V ∧ 𝑃 ∈ V) ∧ 𝜑) → (𝐹 ∈ V ∧ 𝑃 ∈ V))
3633, 34, 35jca31 512 . . . . . 6 (((𝐹 ∈ V ∧ 𝑃 ∈ V) ∧ 𝜑) → ((𝑋𝑉𝑌𝑉) ∧ (𝐹 ∈ V ∧ 𝑃 ∈ V)))
3736ex 403 . . . . 5 ((𝐹 ∈ V ∧ 𝑃 ∈ V) → (𝜑 → ((𝑋𝑉𝑌𝑉) ∧ (𝐹 ∈ V ∧ 𝑃 ∈ V))))
3821, 22, 373syl 18 . . . 4 (𝐹(Walks‘𝐺)𝑃 → (𝜑 → ((𝑋𝑉𝑌𝑉) ∧ (𝐹 ∈ V ∧ 𝑃 ∈ V))))
399, 38mpcom 38 . . 3 (𝜑 → ((𝑋𝑉𝑌𝑉) ∧ (𝐹 ∈ V ∧ 𝑃 ∈ V)))
407ispthson 27045 . . 3 (((𝑋𝑉𝑌𝑉) ∧ (𝐹 ∈ V ∧ 𝑃 ∈ V)) → (𝐹(𝑋(PathsOn‘𝐺)𝑌)𝑃 ↔ (𝐹(𝑋(TrailsOn‘𝐺)𝑌)𝑃𝐹(Paths‘𝐺)𝑃)))
4139, 40syl 17 . 2 (𝜑 → (𝐹(𝑋(PathsOn‘𝐺)𝑌)𝑃 ↔ (𝐹(𝑋(TrailsOn‘𝐺)𝑌)𝑃𝐹(Paths‘𝐺)𝑃)))
4231, 32, 41mpbir2and 706 1 (𝜑𝐹(𝑋(PathsOn‘𝐺)𝑌)𝑃)
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ↔ wb 198   ∧ wa 386   ∧ w3a 1113   = wceq 1658   ∈ wcel 2166   ≠ wne 3000  Vcvv 3415   ⊆ wss 3799  {csn 4398  {cpr 4400   class class class wbr 4874  ‘cfv 6124  (class class class)co 6906  0cc0 10253  1c1 10254  ♯chash 13411  ⟨“cs1 13656  ⟨“cs2 13963  Vtxcvtx 26295  iEdgciedg 26296  Walkscwlks 26895  WalksOncwlkson 26896  Trailsctrls 26992  TrailsOnctrlson 26993  Pathscpths 27015  PathsOncpthson 27017 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1896  ax-4 1910  ax-5 2011  ax-6 2077  ax-7 2114  ax-8 2168  ax-9 2175  ax-10 2194  ax-11 2209  ax-12 2222  ax-13 2391  ax-ext 2804  ax-rep 4995  ax-sep 5006  ax-nul 5014  ax-pow 5066  ax-pr 5128  ax-un 7210  ax-cnex 10309  ax-resscn 10310  ax-1cn 10311  ax-icn 10312  ax-addcl 10313  ax-addrcl 10314  ax-mulcl 10315  ax-mulrcl 10316  ax-mulcom 10317  ax-addass 10318  ax-mulass 10319  ax-distr 10320  ax-i2m1 10321  ax-1ne0 10322  ax-1rid 10323  ax-rnegex 10324  ax-rrecex 10325  ax-cnre 10326  ax-pre-lttri 10327  ax-pre-lttrn 10328  ax-pre-ltadd 10329  ax-pre-mulgt0 10330 This theorem depends on definitions:  df-bi 199  df-an 387  df-or 881  df-ifp 1092  df-3or 1114  df-3an 1115  df-tru 1662  df-ex 1881  df-nf 1885  df-sb 2070  df-mo 2606  df-eu 2641  df-clab 2813  df-cleq 2819  df-clel 2822  df-nfc 2959  df-ne 3001  df-nel 3104  df-ral 3123  df-rex 3124  df-reu 3125  df-rab 3127  df-v 3417  df-sbc 3664  df-csb 3759  df-dif 3802  df-un 3804  df-in 3806  df-ss 3813  df-pss 3815  df-nul 4146  df-if 4308  df-pw 4381  df-sn 4399  df-pr 4401  df-tp 4403  df-op 4405  df-uni 4660  df-int 4699  df-iun 4743  df-br 4875  df-opab 4937  df-mpt 4954  df-tr 4977  df-id 5251  df-eprel 5256  df-po 5264  df-so 5265  df-fr 5302  df-we 5304  df-xp 5349  df-rel 5350  df-cnv 5351  df-co 5352  df-dm 5353  df-rn 5354  df-res 5355  df-ima 5356  df-pred 5921  df-ord 5967  df-on 5968  df-lim 5969  df-suc 5970  df-iota 6087  df-fun 6126  df-fn 6127  df-f 6128  df-f1 6129  df-fo 6130  df-f1o 6131  df-fv 6132  df-riota 6867  df-ov 6909  df-oprab 6910  df-mpt2 6911  df-om 7328  df-1st 7429  df-2nd 7430  df-wrecs 7673  df-recs 7735  df-rdg 7773  df-1o 7827  df-oadd 7831  df-er 8010  df-map 8125  df-pm 8126  df-en 8224  df-dom 8225  df-sdom 8226  df-fin 8227  df-card 9079  df-pnf 10394  df-mnf 10395  df-xr 10396  df-ltxr 10397  df-le 10398  df-sub 10588  df-neg 10589  df-nn 11352  df-2 11415  df-n0 11620  df-z 11706  df-uz 11970  df-fz 12621  df-fzo 12762  df-hash 13412  df-word 13576  df-concat 13632  df-s1 13657  df-s2 13970  df-wlks 26898  df-wlkson 26899  df-trls 26994  df-trlson 26995  df-pths 27019  df-pthson 27021 This theorem is referenced by:  upgr1pthond  27527  lppthon  27528  1pthon2v  27530
 Copyright terms: Public domain W3C validator