Mathbox for Alexander van der Vekens < Previous   Next > Nearby theorems Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  usgra2wlkspth Structured version   Unicode version

Theorem usgra2wlkspth 28370
 Description: In a undirected simple graph, any walk of length 2 between two different vertices is a simple path. (Contributed by Alexander van der Vekens, 2-Mar-2018.)
Assertion
Ref Expression
usgra2wlkspth USGrph WalkOn SPathOn

Proof of Theorem usgra2wlkspth
Dummy variable is distinct from all other variables.
StepHypRef Expression
1 wlkonprop 21563 . . . 4 WalkOn Walks
2 simplr 733 . . . . . 6 Walks WalkOn USGrph WalkOn
3 iswlk 21558 . . . . . . . . . . . . . . . 16 Walks Word ..^
433adant3 978 . . . . . . . . . . . . . . 15 Walks Word ..^
5 id 21 . . . . . . . . . . . . . . . . . . . . 21 Word Word
653ad2ant1 979 . . . . . . . . . . . . . . . . . . . 20 Word ..^ Word
76ad4antlr 715 . . . . . . . . . . . . . . . . . . 19 Word ..^ WalkOn USGrph Word
8 usgraf1 21414 . . . . . . . . . . . . . . . . . . . . . . 23 USGrph
983ad2ant1 979 . . . . . . . . . . . . . . . . . . . . . 22 USGrph
109adantl 454 . . . . . . . . . . . . . . . . . . . . 21 Word ..^ WalkOn USGrph
11 simp2 959 . . . . . . . . . . . . . . . . . . . . . 22 USGrph
1211adantl 454 . . . . . . . . . . . . . . . . . . . . 21 Word ..^ WalkOn USGrph
137, 10, 123jca 1135 . . . . . . . . . . . . . . . . . . . 20 Word ..^ WalkOn USGrph Word
14 simpl 445 . . . . . . . . . . . . . . . . . . . . . . 23
1514ad3antlr 713 . . . . . . . . . . . . . . . . . . . . . 22 Word ..^ WalkOn USGrph
16 simpr 449 . . . . . . . . . . . . . . . . . . . . . . 23
1716ad3antlr 713 . . . . . . . . . . . . . . . . . . . . . 22 Word ..^ WalkOn USGrph
18 simp3 960 . . . . . . . . . . . . . . . . . . . . . . 23 USGrph
1918adantl 454 . . . . . . . . . . . . . . . . . . . . . 22 Word ..^ WalkOn USGrph
2015, 17, 193jca 1135 . . . . . . . . . . . . . . . . . . . . 21 Word ..^ WalkOn USGrph
21 simp3 960 . . . . . . . . . . . . . . . . . . . . . 22 Word ..^ ..^
2221ad4antlr 715 . . . . . . . . . . . . . . . . . . . . 21 Word ..^ WalkOn USGrph ..^
2320, 22jca 520 . . . . . . . . . . . . . . . . . . . 20 Word ..^ WalkOn USGrph ..^
24 usgra2wlkspthlem1 28368 . . . . . . . . . . . . . . . . . . . 20 Word ..^
2513, 23, 24sylc 59 . . . . . . . . . . . . . . . . . . 19 Word ..^ WalkOn USGrph
267, 25jca 520 . . . . . . . . . . . . . . . . . 18 Word ..^ WalkOn USGrph Word
27 simp2 959 . . . . . . . . . . . . . . . . . . 19 Word ..^
2827ad4antlr 715 . . . . . . . . . . . . . . . . . 18 Word ..^ WalkOn USGrph
2926, 28, 223jca 1135 . . . . . . . . . . . . . . . . 17 Word ..^ WalkOn USGrph Word ..^
3029exp31 589 . . . . . . . . . . . . . . . 16 Word ..^ WalkOn USGrph Word ..^
3130exp31 589 . . . . . . . . . . . . . . 15 Word ..^ WalkOn USGrph Word ..^
324, 31sylbid 208 . . . . . . . . . . . . . 14 Walks WalkOn USGrph Word ..^
3332com13 77 . . . . . . . . . . . . 13 Walks WalkOn USGrph Word ..^
3433ex 425 . . . . . . . . . . . 12 Walks WalkOn USGrph Word ..^
3534com3r 76 . . . . . . . . . . 11 Walks WalkOn USGrph Word ..^
36353imp 1148 . . . . . . . . . 10 Walks WalkOn USGrph Word ..^
3736impcom 421 . . . . . . . . 9 Walks WalkOn USGrph Word ..^
3837imp31 423 . . . . . . . 8 Walks WalkOn USGrph Word ..^
39 id 21 . . . . . . . . . . 11
40393adant3 978 . . . . . . . . . 10
4140ad3antrrr 712 . . . . . . . . 9 Walks WalkOn USGrph
42 istrl 21568 . . . . . . . . 9 Trails Word ..^
4341, 42syl 16 . . . . . . . 8 Walks WalkOn USGrph Trails Word ..^
4438, 43mpbird 225 . . . . . . 7 Walks WalkOn USGrph Trails
45 2mwlk 21559 . . . . . . . . . . . . 13 Walks Word
46 simpl 445 . . . . . . . . . . . . 13 Word Word
4745, 46syl 16 . . . . . . . . . . . 12 Walks Word
48473ad2ant1 979 . . . . . . . . . . 11 Walks Word
4948ad3antlr 713 . . . . . . . . . 10 Walks WalkOn USGrph Word
5011adantl 454 . . . . . . . . . 10 Walks WalkOn USGrph
5149, 50jca 520 . . . . . . . . 9 Walks WalkOn USGrph Word
52 id 21 . . . . . . . . . . . 12 USGrph USGrph
53523ad2ant1 979 . . . . . . . . . . 11 USGrph USGrph
5453adantl 454 . . . . . . . . . 10 Walks WalkOn USGrph USGrph
55 simpr 449 . . . . . . . . . . . . 13 Word
5645, 55syl 16 . . . . . . . . . . . 12 Walks
57563ad2ant1 979 . . . . . . . . . . 11 Walks
5857ad3antlr 713 . . . . . . . . . 10 Walks WalkOn USGrph
5954, 58jca 520 . . . . . . . . 9 Walks WalkOn USGrph USGrph
6051, 59jca 520 . . . . . . . 8 Walks WalkOn USGrph Word USGrph
61 simp2 959 . . . . . . . . . . 11 Walks
6261ad3antlr 713 . . . . . . . . . 10 Walks WalkOn USGrph
63 simp3 960 . . . . . . . . . . 11 Walks
6463ad3antlr 713 . . . . . . . . . 10 Walks WalkOn USGrph
6518adantl 454 . . . . . . . . . 10 Walks WalkOn USGrph
6662, 64, 653jca 1135 . . . . . . . . 9 Walks WalkOn USGrph
674, 21syl6bi 221 . . . . . . . . . . . . 13 Walks ..^
6867com12 30 . . . . . . . . . . . 12 Walks ..^
69683ad2ant1 979 . . . . . . . . . . 11 Walks ..^
7069impcom 421 . . . . . . . . . 10 Walks ..^
7170ad2antrr 708 . . . . . . . . 9 Walks WalkOn USGrph ..^
7266, 71jca 520 . . . . . . . 8 Walks WalkOn USGrph ..^
73 usgra2wlkspthlem2 28369 . . . . . . . 8 Word USGrph ..^
7460, 72, 73sylc 59 . . . . . . 7 Walks WalkOn USGrph
75 isspth 21600 . . . . . . . 8 SPaths Trails
7641, 75syl 16 . . . . . . 7 Walks WalkOn USGrph SPaths Trails
7744, 74, 76mpbir2and 890 . . . . . 6 Walks WalkOn USGrph SPaths
78 isspthon 21614 . . . . . . 7 SPathOn WalkOn SPaths
7978ad3antrrr 712 . . . . . 6 Walks WalkOn USGrph SPathOn WalkOn SPaths
802, 77, 79mpbir2and 890 . . . . 5 Walks WalkOn USGrph SPathOn
8180exp31 589 . . . 4 Walks WalkOn USGrph SPathOn
821, 81mpcom 35 . . 3 WalkOn USGrph SPathOn
8382com12 30 . 2 USGrph WalkOn SPathOn
84 spthonprp 21616 . . 3 SPathOn WalkOn SPaths
85 simpl 445 . . . 4 WalkOn SPaths WalkOn
8685adantl 454 . . 3 WalkOn SPaths WalkOn
8784, 86syl 16 . 2 SPathOn WalkOn
8883, 87impbid1 196 1 USGrph WalkOn SPathOn
 Colors of variables: wff set class Syntax hints:   wi 4   wb 178   wa 360   w3a 937   wceq 1653   wcel 1727   wne 2605  wral 2711  cvv 2962  cpr 3839   class class class wbr 4237  ccnv 4906   cdm 4907   crn 4908   wfun 5477  wf 5479  wf1 5480  cfv 5483  (class class class)co 6110  cc0 9021  c1 9022   caddc 9024  c2 10080  cfz 11074  ..^cfzo 11166  chash 11649  Word cword 11748   USGrph cusg 21396   Walks cwalk 21537   Trails ctrail 21538   SPaths cspath 21540   WalkOn cwlkon 21541   SPathOn cspthon 21544 This theorem is referenced by:  2pthwlkonot  28441 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1556  ax-5 1567  ax-17 1627  ax-9 1668  ax-8 1689  ax-13 1729  ax-14 1731  ax-6 1746  ax-7 1751  ax-11 1763  ax-12 1953  ax-ext 2423  ax-rep 4345  ax-sep 4355  ax-nul 4363  ax-pow 4406  ax-pr 4432  ax-un 4730  ax-cnex 9077  ax-resscn 9078  ax-1cn 9079  ax-icn 9080  ax-addcl 9081  ax-addrcl 9082  ax-mulcl 9083  ax-mulrcl 9084  ax-mulcom 9085  ax-addass 9086  ax-mulass 9087  ax-distr 9088  ax-i2m1 9089  ax-1ne0 9090  ax-1rid 9091  ax-rnegex 9092  ax-rrecex 9093  ax-cnre 9094  ax-pre-lttri 9095  ax-pre-lttrn 9096  ax-pre-ltadd 9097  ax-pre-mulgt0 9098 This theorem depends on definitions:  df-bi 179  df-or 361  df-an 362  df-3or 938  df-3an 939  df-tru 1329  df-ex 1552  df-nf 1555  df-sb 1660  df-eu 2291  df-mo 2292  df-clab 2429  df-cleq 2435  df-clel 2438  df-nfc 2567  df-ne 2607  df-nel 2608  df-ral 2716  df-rex 2717  df-reu 2718  df-rmo 2719  df-rab 2720  df-v 2964  df-sbc 3168  df-csb 3268  df-dif 3309  df-un 3311  df-in 3313  df-ss 3320  df-pss 3322  df-nul 3614  df-if 3764  df-pw 3825  df-sn 3844  df-pr 3845  df-tp 3846  df-op 3847  df-uni 4040  df-int 4075  df-iun 4119  df-br 4238  df-opab 4292  df-mpt 4293  df-tr 4328  df-eprel 4523  df-id 4527  df-po 4532  df-so 4533  df-fr 4570  df-we 4572  df-ord 4613  df-on 4614  df-lim 4615  df-suc 4616  df-om 4875  df-xp 4913  df-rel 4914  df-cnv 4915  df-co 4916  df-dm 4917  df-rn 4918  df-res 4919  df-ima 4920  df-iota 5447  df-fun 5485  df-fn 5486  df-f 5487  df-f1 5488  df-fo 5489  df-f1o 5490  df-fv 5491  df-ov 6113  df-oprab 6114  df-mpt2 6115  df-1st 6378  df-2nd 6379  df-riota 6578  df-recs 6662  df-rdg 6697  df-1o 6753  df-oadd 6757  df-er 6934  df-map 7049  df-pm 7050  df-en 7139  df-dom 7140  df-sdom 7141  df-fin 7142  df-card 7857  df-cda 8079  df-pnf 9153  df-mnf 9154  df-xr 9155  df-ltxr 9156  df-le 9157  df-sub 9324  df-neg 9325  df-nn 10032  df-2 10089  df-n0 10253  df-z 10314  df-uz 10520  df-fz 11075  df-fzo 11167  df-hash 11650  df-word 11754  df-usgra 21398  df-wlk 21547  df-trail 21548  df-pth 21549  df-spth 21550  df-wlkon 21553  df-spthon 21556
 Copyright terms: Public domain W3C validator