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

Theorem wspthsnwspthsnon 27005
 Description: A simple path of fixed length is a simple path of fixed length between two vertices. (Contributed by Alexander van der Vekens, 1-Mar-2018.) (Revised by AV, 16-May-2021.) (Revised by AV, 13-Mar-2022.)
Hypothesis
Ref Expression
wwlksnwwlksnon.v 𝑉 = (Vtx‘𝐺)
Assertion
Ref Expression
wspthsnwspthsnon (𝑊 ∈ (𝑁 WSPathsN 𝐺) ↔ ∃𝑎𝑉𝑏𝑉 𝑊 ∈ (𝑎(𝑁 WSPathsNOn 𝐺)𝑏))
Distinct variable groups:   𝐺,𝑎,𝑏   𝑁,𝑎,𝑏   𝑉,𝑎,𝑏   𝑊,𝑎,𝑏

Proof of Theorem wspthsnwspthsnon
Dummy variable 𝑓 is distinct from all other variables.
StepHypRef Expression
1 iswspthn 26924 . 2 (𝑊 ∈ (𝑁 WSPathsN 𝐺) ↔ (𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊))
2 wwlksnwwlksnon.v . . . . 5 𝑉 = (Vtx‘𝐺)
32wwlksnwwlksnon 27004 . . . 4 (𝑊 ∈ (𝑁 WWalksN 𝐺) ↔ ∃𝑎𝑉𝑏𝑉 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏))
43anbi1i 733 . . 3 ((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊) ↔ (∃𝑎𝑉𝑏𝑉 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊))
5 r19.41vv 3217 . . 3 (∃𝑎𝑉𝑏𝑉 (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊) ↔ (∃𝑎𝑉𝑏𝑉 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊))
64, 5bitr4i 267 . 2 ((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊) ↔ ∃𝑎𝑉𝑏𝑉 (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊))
7 3anass 1081 . . . . . . . 8 ((𝑓(SPaths‘𝐺)𝑊 ∧ (𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏) ↔ (𝑓(SPaths‘𝐺)𝑊 ∧ ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
87a1i 11 . . . . . . 7 (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → ((𝑓(SPaths‘𝐺)𝑊 ∧ (𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏) ↔ (𝑓(SPaths‘𝐺)𝑊 ∧ ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏))))
9 vex 3331 . . . . . . . 8 𝑓 ∈ V
102isspthonpth 26826 . . . . . . . 8 (((𝑎𝑉𝑏𝑉) ∧ (𝑓 ∈ V ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏))) → (𝑓(𝑎(SPathsOn‘𝐺)𝑏)𝑊 ↔ (𝑓(SPaths‘𝐺)𝑊 ∧ (𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
119, 10mpanr1 721 . . . . . . 7 (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → (𝑓(𝑎(SPathsOn‘𝐺)𝑏)𝑊 ↔ (𝑓(SPaths‘𝐺)𝑊 ∧ (𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
12 spthiswlk 26805 . . . . . . . . . 10 (𝑓(SPaths‘𝐺)𝑊𝑓(Walks‘𝐺)𝑊)
13 wlklenvm1 26698 . . . . . . . . . 10 (𝑓(Walks‘𝐺)𝑊 → (♯‘𝑓) = ((♯‘𝑊) − 1))
14 wwlknon 26934 . . . . . . . . . . . . 13 (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ↔ (𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏))
15 simpl2 1206 . . . . . . . . . . . . . . 15 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → (𝑊‘0) = 𝑎)
16 simpr 479 . . . . . . . . . . . . . . . . . 18 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → (♯‘𝑓) = ((♯‘𝑊) − 1))
17 wwlknbp1 26918 . . . . . . . . . . . . . . . . . . . . 21 (𝑊 ∈ (𝑁 WWalksN 𝐺) → (𝑁 ∈ ℕ0𝑊 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑊) = (𝑁 + 1)))
18 oveq1 6808 . . . . . . . . . . . . . . . . . . . . . . 23 ((♯‘𝑊) = (𝑁 + 1) → ((♯‘𝑊) − 1) = ((𝑁 + 1) − 1))
19183ad2ant3 1127 . . . . . . . . . . . . . . . . . . . . . 22 ((𝑁 ∈ ℕ0𝑊 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑊) = (𝑁 + 1)) → ((♯‘𝑊) − 1) = ((𝑁 + 1) − 1))
20 nn0cn 11465 . . . . . . . . . . . . . . . . . . . . . . . 24 (𝑁 ∈ ℕ0𝑁 ∈ ℂ)
21 pncan1 10617 . . . . . . . . . . . . . . . . . . . . . . . 24 (𝑁 ∈ ℂ → ((𝑁 + 1) − 1) = 𝑁)
2220, 21syl 17 . . . . . . . . . . . . . . . . . . . . . . 23 (𝑁 ∈ ℕ0 → ((𝑁 + 1) − 1) = 𝑁)
23223ad2ant1 1125 . . . . . . . . . . . . . . . . . . . . . 22 ((𝑁 ∈ ℕ0𝑊 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑊) = (𝑁 + 1)) → ((𝑁 + 1) − 1) = 𝑁)
2419, 23eqtrd 2782 . . . . . . . . . . . . . . . . . . . . 21 ((𝑁 ∈ ℕ0𝑊 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑊) = (𝑁 + 1)) → ((♯‘𝑊) − 1) = 𝑁)
2517, 24syl 17 . . . . . . . . . . . . . . . . . . . 20 (𝑊 ∈ (𝑁 WWalksN 𝐺) → ((♯‘𝑊) − 1) = 𝑁)
26253ad2ant1 1125 . . . . . . . . . . . . . . . . . . 19 ((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) → ((♯‘𝑊) − 1) = 𝑁)
2726adantr 472 . . . . . . . . . . . . . . . . . 18 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → ((♯‘𝑊) − 1) = 𝑁)
2816, 27eqtrd 2782 . . . . . . . . . . . . . . . . 17 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → (♯‘𝑓) = 𝑁)
2928fveq2d 6344 . . . . . . . . . . . . . . . 16 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → (𝑊‘(♯‘𝑓)) = (𝑊𝑁))
30 simpl3 1208 . . . . . . . . . . . . . . . 16 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → (𝑊𝑁) = 𝑏)
3129, 30eqtrd 2782 . . . . . . . . . . . . . . 15 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → (𝑊‘(♯‘𝑓)) = 𝑏)
3215, 31jca 555 . . . . . . . . . . . . . 14 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏))
3332ex 449 . . . . . . . . . . . . 13 ((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) → ((♯‘𝑓) = ((♯‘𝑊) − 1) → ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
3414, 33sylbi 207 . . . . . . . . . . . 12 (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) → ((♯‘𝑓) = ((♯‘𝑊) − 1) → ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
3534adantl 473 . . . . . . . . . . 11 (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → ((♯‘𝑓) = ((♯‘𝑊) − 1) → ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
3635com12 32 . . . . . . . . . 10 ((♯‘𝑓) = ((♯‘𝑊) − 1) → (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
3712, 13, 363syl 18 . . . . . . . . 9 (𝑓(SPaths‘𝐺)𝑊 → (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
3837com12 32 . . . . . . . 8 (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → (𝑓(SPaths‘𝐺)𝑊 → ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
3938pm4.71d 669 . . . . . . 7 (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → (𝑓(SPaths‘𝐺)𝑊 ↔ (𝑓(SPaths‘𝐺)𝑊 ∧ ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏))))
408, 11, 393bitr4rd 301 . . . . . 6 (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → (𝑓(SPaths‘𝐺)𝑊𝑓(𝑎(SPathsOn‘𝐺)𝑏)𝑊))
4140exbidv 1987 . . . . 5 (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → (∃𝑓 𝑓(SPaths‘𝐺)𝑊 ↔ ∃𝑓 𝑓(𝑎(SPathsOn‘𝐺)𝑏)𝑊))
4241pm5.32da 676 . . . 4 ((𝑎𝑉𝑏𝑉) → ((𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊) ↔ (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(𝑎(SPathsOn‘𝐺)𝑏)𝑊)))
43 wspthnon 26935 . . . 4 (𝑊 ∈ (𝑎(𝑁 WSPathsNOn 𝐺)𝑏) ↔ (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(𝑎(SPathsOn‘𝐺)𝑏)𝑊))
4442, 43syl6bbr 278 . . 3 ((𝑎𝑉𝑏𝑉) → ((𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊) ↔ 𝑊 ∈ (𝑎(𝑁 WSPathsNOn 𝐺)𝑏)))
45442rexbiia 3181 . 2 (∃𝑎𝑉𝑏𝑉 (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊) ↔ ∃𝑎𝑉𝑏𝑉 𝑊 ∈ (𝑎(𝑁 WSPathsNOn 𝐺)𝑏))
461, 6, 453bitri 286 1 (𝑊 ∈ (𝑁 WSPathsN 𝐺) ↔ ∃𝑎𝑉𝑏𝑉 𝑊 ∈ (𝑎(𝑁 WSPathsNOn 𝐺)𝑏))
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ↔ wb 196   ∧ wa 383   ∧ w3a 1072   = wceq 1620  ∃wex 1841   ∈ wcel 2127  ∃wrex 3039  Vcvv 3328   class class class wbr 4792  ‘cfv 6037  (class class class)co 6801  ℂcc 10097  0cc0 10099  1c1 10100   + caddc 10102   − cmin 10429  ℕ0cn0 11455  ♯chash 13282  Word cword 13448  Vtxcvtx 26044  Walkscwlks 26673  SPathscspths 26790  SPathsOncspthson 26792   WWalksN cwwlksn 26900   WWalksNOn cwwlksnon 26901   WSPathsN cwwspthsn 26902   WSPathsNOn cwwspthsnon 26903 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1859  ax-4 1874  ax-5 1976  ax-6 2042  ax-7 2078  ax-8 2129  ax-9 2136  ax-10 2156  ax-11 2171  ax-12 2184  ax-13 2379  ax-ext 2728  ax-rep 4911  ax-sep 4921  ax-nul 4929  ax-pow 4980  ax-pr 5043  ax-un 7102  ax-cnex 10155  ax-resscn 10156  ax-1cn 10157  ax-icn 10158  ax-addcl 10159  ax-addrcl 10160  ax-mulcl 10161  ax-mulrcl 10162  ax-mulcom 10163  ax-addass 10164  ax-mulass 10165  ax-distr 10166  ax-i2m1 10167  ax-1ne0 10168  ax-1rid 10169  ax-rnegex 10170  ax-rrecex 10171  ax-cnre 10172  ax-pre-lttri 10173  ax-pre-lttrn 10174  ax-pre-ltadd 10175  ax-pre-mulgt0 10176 This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-ifp 1051  df-3or 1073  df-3an 1074  df-tru 1623  df-fal 1626  df-ex 1842  df-nf 1847  df-sb 2035  df-eu 2599  df-mo 2600  df-clab 2735  df-cleq 2741  df-clel 2744  df-nfc 2879  df-ne 2921  df-nel 3024  df-ral 3043  df-rex 3044  df-reu 3045  df-rab 3047  df-v 3330  df-sbc 3565  df-csb 3663  df-dif 3706  df-un 3708  df-in 3710  df-ss 3717  df-pss 3719  df-nul 4047  df-if 4219  df-pw 4292  df-sn 4310  df-pr 4312  df-tp 4314  df-op 4316  df-uni 4577  df-int 4616  df-iun 4662  df-br 4793  df-opab 4853  df-mpt 4870  df-tr 4893  df-id 5162  df-eprel 5167  df-po 5175  df-so 5176  df-fr 5213  df-we 5215  df-xp 5260  df-rel 5261  df-cnv 5262  df-co 5263  df-dm 5264  df-rn 5265  df-res 5266  df-ima 5267  df-pred 5829  df-ord 5875  df-on 5876  df-lim 5877  df-suc 5878  df-iota 6000  df-fun 6039  df-fn 6040  df-f 6041  df-f1 6042  df-fo 6043  df-f1o 6044  df-fv 6045  df-riota 6762  df-ov 6804  df-oprab 6805  df-mpt2 6806  df-om 7219  df-1st 7321  df-2nd 7322  df-wrecs 7564  df-recs 7625  df-rdg 7663  df-1o 7717  df-oadd 7721  df-er 7899  df-map 8013  df-pm 8014  df-en 8110  df-dom 8111  df-sdom 8112  df-fin 8113  df-card 8926  df-pnf 10239  df-mnf 10240  df-xr 10241  df-ltxr 10242  df-le 10243  df-sub 10431  df-neg 10432  df-nn 11184  df-n0 11456  df-z 11541  df-uz 11851  df-fz 12491  df-fzo 12631  df-hash 13283  df-word 13456  df-wlks 26676  df-wlkson 26677  df-trls 26770  df-trlson 26771  df-pths 26793  df-spths 26794  df-spthson 26796  df-wwlks 26904  df-wwlksn 26905  df-wwlksnon 26906  df-wspthsn 26907  df-wspthsnon 26908 This theorem is referenced by:  wspniunwspnon  27014  elwspths2spth  27060  fusgr2wsp2nb  27459
 Copyright terms: Public domain W3C validator