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

Theorem wspthsnwspthsnon 27806
 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 27739 . 2 (𝑊 ∈ (𝑁 WSPathsN 𝐺) ↔ (𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊))
2 wwlksnwwlksnon.v . . . . 5 𝑉 = (Vtx‘𝐺)
32wwlksnwwlksnon 27805 . . . 4 (𝑊 ∈ (𝑁 WWalksN 𝐺) ↔ ∃𝑎𝑉𝑏𝑉 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏))
43anbi1i 626 . . 3 ((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊) ↔ (∃𝑎𝑉𝑏𝑉 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊))
5 r19.41vv 3267 . . 3 (∃𝑎𝑉𝑏𝑉 (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊) ↔ (∃𝑎𝑉𝑏𝑉 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊))
64, 5bitr4i 281 . 2 ((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊) ↔ ∃𝑎𝑉𝑏𝑉 (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊))
7 3anass 1092 . . . . . . . 8 ((𝑓(SPaths‘𝐺)𝑊 ∧ (𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏) ↔ (𝑓(SPaths‘𝐺)𝑊 ∧ ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
87a1i 11 . . . . . . 7 (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → ((𝑓(SPaths‘𝐺)𝑊 ∧ (𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏) ↔ (𝑓(SPaths‘𝐺)𝑊 ∧ ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏))))
9 vex 3413 . . . . . . . 8 𝑓 ∈ V
102isspthonpth 27642 . . . . . . . 8 (((𝑎𝑉𝑏𝑉) ∧ (𝑓 ∈ V ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏))) → (𝑓(𝑎(SPathsOn‘𝐺)𝑏)𝑊 ↔ (𝑓(SPaths‘𝐺)𝑊 ∧ (𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
119, 10mpanr1 702 . . . . . . 7 (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → (𝑓(𝑎(SPathsOn‘𝐺)𝑏)𝑊 ↔ (𝑓(SPaths‘𝐺)𝑊 ∧ (𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
12 spthiswlk 27621 . . . . . . . . . 10 (𝑓(SPaths‘𝐺)𝑊𝑓(Walks‘𝐺)𝑊)
13 wlklenvm1 27515 . . . . . . . . . 10 (𝑓(Walks‘𝐺)𝑊 → (♯‘𝑓) = ((♯‘𝑊) − 1))
14 wwlknon 27747 . . . . . . . . . . . . 13 (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ↔ (𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏))
15 simpl2 1189 . . . . . . . . . . . . . . 15 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → (𝑊‘0) = 𝑎)
16 simpr 488 . . . . . . . . . . . . . . . . . 18 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → (♯‘𝑓) = ((♯‘𝑊) − 1))
17 wwlknbp1 27734 . . . . . . . . . . . . . . . . . . . . 21 (𝑊 ∈ (𝑁 WWalksN 𝐺) → (𝑁 ∈ ℕ0𝑊 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑊) = (𝑁 + 1)))
18 oveq1 7162 . . . . . . . . . . . . . . . . . . . . . . 23 ((♯‘𝑊) = (𝑁 + 1) → ((♯‘𝑊) − 1) = ((𝑁 + 1) − 1))
19183ad2ant3 1132 . . . . . . . . . . . . . . . . . . . . . 22 ((𝑁 ∈ ℕ0𝑊 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑊) = (𝑁 + 1)) → ((♯‘𝑊) − 1) = ((𝑁 + 1) − 1))
20 nn0cn 11949 . . . . . . . . . . . . . . . . . . . . . . . 24 (𝑁 ∈ ℕ0𝑁 ∈ ℂ)
21 pncan1 11107 . . . . . . . . . . . . . . . . . . . . . . . 24 (𝑁 ∈ ℂ → ((𝑁 + 1) − 1) = 𝑁)
2220, 21syl 17 . . . . . . . . . . . . . . . . . . . . . . 23 (𝑁 ∈ ℕ0 → ((𝑁 + 1) − 1) = 𝑁)
23223ad2ant1 1130 . . . . . . . . . . . . . . . . . . . . . 22 ((𝑁 ∈ ℕ0𝑊 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑊) = (𝑁 + 1)) → ((𝑁 + 1) − 1) = 𝑁)
2419, 23eqtrd 2793 . . . . . . . . . . . . . . . . . . . . 21 ((𝑁 ∈ ℕ0𝑊 ∈ Word (Vtx‘𝐺) ∧ (♯‘𝑊) = (𝑁 + 1)) → ((♯‘𝑊) − 1) = 𝑁)
2517, 24syl 17 . . . . . . . . . . . . . . . . . . . 20 (𝑊 ∈ (𝑁 WWalksN 𝐺) → ((♯‘𝑊) − 1) = 𝑁)
26253ad2ant1 1130 . . . . . . . . . . . . . . . . . . 19 ((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) → ((♯‘𝑊) − 1) = 𝑁)
2726adantr 484 . . . . . . . . . . . . . . . . . 18 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → ((♯‘𝑊) − 1) = 𝑁)
2816, 27eqtrd 2793 . . . . . . . . . . . . . . . . 17 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → (♯‘𝑓) = 𝑁)
2928fveq2d 6666 . . . . . . . . . . . . . . . 16 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → (𝑊‘(♯‘𝑓)) = (𝑊𝑁))
30 simpl3 1190 . . . . . . . . . . . . . . . 16 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → (𝑊𝑁) = 𝑏)
3129, 30eqtrd 2793 . . . . . . . . . . . . . . 15 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → (𝑊‘(♯‘𝑓)) = 𝑏)
3215, 31jca 515 . . . . . . . . . . . . . 14 (((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) ∧ (♯‘𝑓) = ((♯‘𝑊) − 1)) → ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏))
3332ex 416 . . . . . . . . . . . . 13 ((𝑊 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑊‘0) = 𝑎 ∧ (𝑊𝑁) = 𝑏) → ((♯‘𝑓) = ((♯‘𝑊) − 1) → ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
3414, 33sylbi 220 . . . . . . . . . . . 12 (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) → ((♯‘𝑓) = ((♯‘𝑊) − 1) → ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏)))
3534adantl 485 . . . . . . . . . . 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 565 . . . . . . 7 (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → (𝑓(SPaths‘𝐺)𝑊 ↔ (𝑓(SPaths‘𝐺)𝑊 ∧ ((𝑊‘0) = 𝑎 ∧ (𝑊‘(♯‘𝑓)) = 𝑏))))
408, 11, 393bitr4rd 315 . . . . . 6 (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → (𝑓(SPaths‘𝐺)𝑊𝑓(𝑎(SPathsOn‘𝐺)𝑏)𝑊))
4140exbidv 1922 . . . . 5 (((𝑎𝑉𝑏𝑉) ∧ 𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏)) → (∃𝑓 𝑓(SPaths‘𝐺)𝑊 ↔ ∃𝑓 𝑓(𝑎(SPathsOn‘𝐺)𝑏)𝑊))
4241pm5.32da 582 . . . 4 ((𝑎𝑉𝑏𝑉) → ((𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊) ↔ (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(𝑎(SPathsOn‘𝐺)𝑏)𝑊)))
43 wspthnon 27748 . . . 4 (𝑊 ∈ (𝑎(𝑁 WSPathsNOn 𝐺)𝑏) ↔ (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(𝑎(SPathsOn‘𝐺)𝑏)𝑊))
4442, 43bitr4di 292 . . 3 ((𝑎𝑉𝑏𝑉) → ((𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊) ↔ 𝑊 ∈ (𝑎(𝑁 WSPathsNOn 𝐺)𝑏)))
45442rexbiia 3222 . 2 (∃𝑎𝑉𝑏𝑉 (𝑊 ∈ (𝑎(𝑁 WWalksNOn 𝐺)𝑏) ∧ ∃𝑓 𝑓(SPaths‘𝐺)𝑊) ↔ ∃𝑎𝑉𝑏𝑉 𝑊 ∈ (𝑎(𝑁 WSPathsNOn 𝐺)𝑏))
461, 6, 453bitri 300 1 (𝑊 ∈ (𝑁 WSPathsN 𝐺) ↔ ∃𝑎𝑉𝑏𝑉 𝑊 ∈ (𝑎(𝑁 WSPathsNOn 𝐺)𝑏))
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ↔ wb 209   ∧ wa 399   ∧ w3a 1084   = wceq 1538  ∃wex 1781   ∈ wcel 2111  ∃wrex 3071  Vcvv 3409   class class class wbr 5035  ‘cfv 6339  (class class class)co 7155  ℂcc 10578  0cc0 10580  1c1 10581   + caddc 10583   − cmin 10913  ℕ0cn0 11939  ♯chash 13745  Word cword 13918  Vtxcvtx 26893  Walkscwlks 27490  SPathscspths 27606  SPathsOncspthson 27608   WWalksN cwwlksn 27716   WWalksNOn cwwlksnon 27717   WSPathsN cwwspthsn 27718   WSPathsNOn cwwspthsnon 27719 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1911  ax-6 1970  ax-7 2015  ax-8 2113  ax-9 2121  ax-10 2142  ax-11 2158  ax-12 2175  ax-ext 2729  ax-rep 5159  ax-sep 5172  ax-nul 5179  ax-pow 5237  ax-pr 5301  ax-un 7464  ax-cnex 10636  ax-resscn 10637  ax-1cn 10638  ax-icn 10639  ax-addcl 10640  ax-addrcl 10641  ax-mulcl 10642  ax-mulrcl 10643  ax-mulcom 10644  ax-addass 10645  ax-mulass 10646  ax-distr 10647  ax-i2m1 10648  ax-1ne0 10649  ax-1rid 10650  ax-rnegex 10651  ax-rrecex 10652  ax-cnre 10653  ax-pre-lttri 10654  ax-pre-lttrn 10655  ax-pre-ltadd 10656  ax-pre-mulgt0 10657 This theorem depends on definitions:  df-bi 210  df-an 400  df-or 845  df-ifp 1059  df-3or 1085  df-3an 1086  df-tru 1541  df-fal 1551  df-ex 1782  df-nf 1786  df-sb 2070  df-mo 2557  df-eu 2588  df-clab 2736  df-cleq 2750  df-clel 2830  df-nfc 2901  df-ne 2952  df-nel 3056  df-ral 3075  df-rex 3076  df-reu 3077  df-rab 3079  df-v 3411  df-sbc 3699  df-csb 3808  df-dif 3863  df-un 3865  df-in 3867  df-ss 3877  df-pss 3879  df-nul 4228  df-if 4424  df-pw 4499  df-sn 4526  df-pr 4528  df-tp 4530  df-op 4532  df-uni 4802  df-int 4842  df-iun 4888  df-br 5036  df-opab 5098  df-mpt 5116  df-tr 5142  df-id 5433  df-eprel 5438  df-po 5446  df-so 5447  df-fr 5486  df-we 5488  df-xp 5533  df-rel 5534  df-cnv 5535  df-co 5536  df-dm 5537  df-rn 5538  df-res 5539  df-ima 5540  df-pred 6130  df-ord 6176  df-on 6177  df-lim 6178  df-suc 6179  df-iota 6298  df-fun 6341  df-fn 6342  df-f 6343  df-f1 6344  df-fo 6345  df-f1o 6346  df-fv 6347  df-riota 7113  df-ov 7158  df-oprab 7159  df-mpo 7160  df-om 7585  df-1st 7698  df-2nd 7699  df-wrecs 7962  df-recs 8023  df-rdg 8061  df-1o 8117  df-er 8304  df-map 8423  df-en 8533  df-dom 8534  df-sdom 8535  df-fin 8536  df-card 9406  df-pnf 10720  df-mnf 10721  df-xr 10722  df-ltxr 10723  df-le 10724  df-sub 10915  df-neg 10916  df-nn 11680  df-n0 11940  df-z 12026  df-uz 12288  df-fz 12945  df-fzo 13088  df-hash 13746  df-word 13919  df-wlks 27493  df-wlkson 27494  df-trls 27586  df-trlson 27587  df-pths 27609  df-spths 27610  df-spthson 27612  df-wwlks 27720  df-wwlksn 27721  df-wwlksnon 27722  df-wspthsn 27723  df-wspthsnon 27724 This theorem is referenced by:  wspniunwspnon  27813  elwspths2spth  27857  fusgr2wsp2nb  28223
 Copyright terms: Public domain W3C validator