Metamath Proof Explorer < Previous   Next > Nearby theorems Mirrors  >  Home  >  MPE Home  >  Th. List  >  usgreghash2spot Structured version   Unicode version

Theorem usgreghash2spot 25668
 Description: In a finite k-regular graph with N vertices there are N times " choose 2 " paths with length 2, according to statement 8 in [Huneke] p. 2: "... giving n * ( k 2 ) total paths of length two.", if the direction of traversing the path is not respected. For simple paths of length 2 represented by ordered triples, however, we have again n*k*(k-1) such paths. (Contributed by Alexander van der Vekens, 11-Mar-2018.)
Assertion
Ref Expression
usgreghash2spot USGrph VDeg 2SPathOnOt
Distinct variable groups:   ,   ,   ,

Proof of Theorem usgreghash2spot
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 eleq1 2492 . . . . . . . . . 10 2SPathOnOt 2SPathOnOt
2 fveq2 5872 . . . . . . . . . . . 12
32fveq2d 5876 . . . . . . . . . . 11
43eqeq1d 2422 . . . . . . . . . 10
51, 4anbi12d 715 . . . . . . . . 9 2SPathOnOt 2SPathOnOt
65cbvrabv 3077 . . . . . . . 8 2SPathOnOt 2SPathOnOt
76mpteq2i 4500 . . . . . . 7 2SPathOnOt 2SPathOnOt
87usgreg2spot 25666 . . . . . 6 USGrph VDeg 2SPathOnOt 2SPathOnOt
983adant3 1025 . . . . 5 USGrph VDeg 2SPathOnOt 2SPathOnOt
109imp 430 . . . 4 USGrph VDeg 2SPathOnOt 2SPathOnOt
1110fveq2d 5876 . . 3 USGrph VDeg 2SPathOnOt 2SPathOnOt
12 simpl 458 . . . . 5 VDeg
13 simpr 462 . . . . . . 7 VDeg
14 3xpfi 7840 . . . . . . . . 9
15 rabexg 4566 . . . . . . . . 9 2SPathOnOt
1614, 15syl 17 . . . . . . . 8 2SPathOnOt
1716ad2antrr 730 . . . . . . 7 VDeg 2SPathOnOt
18 eqeq2 2435 . . . . . . . . . 10
1918anbi2d 708 . . . . . . . . 9 2SPathOnOt 2SPathOnOt
2019rabbidv 3070 . . . . . . . 8 2SPathOnOt 2SPathOnOt
21 eqid 2420 . . . . . . . 8 2SPathOnOt 2SPathOnOt
2220, 21fvmptg 5953 . . . . . . 7 2SPathOnOt 2SPathOnOt 2SPathOnOt
2313, 17, 22syl2anc 665 . . . . . 6 VDeg 2SPathOnOt 2SPathOnOt
2414ad2antrr 730 . . . . . . 7 VDeg
25 rabfi 7793 . . . . . . 7 2SPathOnOt
2624, 25syl 17 . . . . . 6 VDeg 2SPathOnOt
2723, 26eqeltrd 2508 . . . . 5 VDeg 2SPathOnOt
28 elex 3087 . . . . . . 7
2972spotmdisj 25667 . . . . . . 7 Disj 2SPathOnOt
3028, 29syl 17 . . . . . 6 Disj 2SPathOnOt
3130adantr 466 . . . . 5 VDeg Disj 2SPathOnOt
3212, 27, 31hashiun 13849 . . . 4 VDeg 2SPathOnOt 2SPathOnOt
33323ad2antl2 1168 . . 3 USGrph VDeg 2SPathOnOt 2SPathOnOt
347usgreghash2spotv 25665 . . . . . . . . 9 USGrph VDeg 2SPathOnOt
35 ralim 2812 . . . . . . . . 9 VDeg 2SPathOnOt VDeg 2SPathOnOt
3634, 35syl 17 . . . . . . . 8 USGrph VDeg 2SPathOnOt
37363adant3 1025 . . . . . . 7 USGrph VDeg 2SPathOnOt
3837imp 430 . . . . . 6 USGrph VDeg 2SPathOnOt
39 fveq2 5872 . . . . . . . . 9 2SPathOnOt 2SPathOnOt
4039fveq2d 5876 . . . . . . . 8 2SPathOnOt 2SPathOnOt
4140eqeq1d 2422 . . . . . . 7 2SPathOnOt 2SPathOnOt
4241rspccva 3178 . . . . . 6 2SPathOnOt 2SPathOnOt
4338, 42sylan 473 . . . . 5 USGrph VDeg 2SPathOnOt
4443sumeq2dv 13736 . . . 4 USGrph VDeg 2SPathOnOt
45 simpl2 1009 . . . . 5 USGrph VDeg
46 usgfidegfi 25509 . . . . . . . 8 USGrph VDeg
47 r19.26 2953 . . . . . . . . . . 11 VDeg VDeg VDeg VDeg
48 eleq1 2492 . . . . . . . . . . . . . 14 VDeg VDeg
4948biimpac 488 . . . . . . . . . . . . 13 VDeg VDeg
5049ralimi 2816 . . . . . . . . . . . 12 VDeg VDeg
51 r19.2z 3883 . . . . . . . . . . . . . 14
52 nn0cn 10868 . . . . . . . . . . . . . . . 16
53 kcnktkm1cn 10039 . . . . . . . . . . . . . . . 16
5452, 53syl 17 . . . . . . . . . . . . . . 15
5554rexlimivw 2912 . . . . . . . . . . . . . 14
5651, 55syl 17 . . . . . . . . . . . . 13
5756expcom 436 . . . . . . . . . . . 12
5850, 57syl 17 . . . . . . . . . . 11 VDeg VDeg
5947, 58sylbir 216 . . . . . . . . . 10 VDeg VDeg
6059ex 435 . . . . . . . . 9 VDeg VDeg
6160com23 81 . . . . . . . 8 VDeg VDeg
6246, 61syl 17 . . . . . . 7 USGrph VDeg
6362ex 435 . . . . . 6 USGrph VDeg
64633imp1 1218 . . . . 5 USGrph VDeg
65 fsumconst 13818 . . . . 5
6645, 64, 65syl2anc 665 . . . 4 USGrph VDeg
6744, 66eqtrd 2461 . . 3 USGrph VDeg 2SPathOnOt
6811, 33, 673eqtrd 2465 . 2 USGrph VDeg 2SPathOnOt
6968ex 435 1 USGrph VDeg 2SPathOnOt
 Colors of variables: wff setvar class Syntax hints:   wi 4   wa 370   w3a 982   wceq 1437   wcel 1867   wne 2616  wral 2773  wrex 2774  crab 2777  cvv 3078  c0 3758  ciun 4293  Disj wdisj 4388   class class class wbr 4417   cmpt 4475   cxp 4843  cfv 5592  (class class class)co 6296  c1st 6796  c2nd 6797  cfn 7568  cc 9526  c1 9529   cmul 9533   cmin 9849  cn0 10858  chash 12501  csu 13719   USGrph cusg 24929   2SPathOnOt c2spthot 25455   VDeg cvdg 25492 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1665  ax-4 1678  ax-5 1748  ax-6 1794  ax-7 1838  ax-8 1869  ax-9 1871  ax-10 1886  ax-11 1891  ax-12 1904  ax-13 2052  ax-ext 2398  ax-rep 4529  ax-sep 4539  ax-nul 4547  ax-pow 4594  ax-pr 4652  ax-un 6588  ax-inf2 8137  ax-cnex 9584  ax-resscn 9585  ax-1cn 9586  ax-icn 9587  ax-addcl 9588  ax-addrcl 9589  ax-mulcl 9590  ax-mulrcl 9591  ax-mulcom 9592  ax-addass 9593  ax-mulass 9594  ax-distr 9595  ax-i2m1 9596  ax-1ne0 9597  ax-1rid 9598  ax-rnegex 9599  ax-rrecex 9600  ax-cnre 9601  ax-pre-lttri 9602  ax-pre-lttrn 9603  ax-pre-ltadd 9604  ax-pre-mulgt0 9605  ax-pre-sup 9606 This theorem depends on definitions:  df-bi 188  df-or 371  df-an 372  df-3or 983  df-3an 984  df-tru 1440  df-fal 1443  df-ex 1660  df-nf 1664  df-sb 1787  df-eu 2267  df-mo 2268  df-clab 2406  df-cleq 2412  df-clel 2415  df-nfc 2570  df-ne 2618  df-nel 2619  df-ral 2778  df-rex 2779  df-reu 2780  df-rmo 2781  df-rab 2782  df-v 3080  df-sbc 3297  df-csb 3393  df-dif 3436  df-un 3438  df-in 3440  df-ss 3447  df-pss 3449  df-nul 3759  df-if 3907  df-pw 3978  df-sn 3994  df-pr 3996  df-tp 3998  df-op 4000  df-ot 4002  df-uni 4214  df-int 4250  df-iun 4295  df-disj 4389  df-br 4418  df-opab 4476  df-mpt 4477  df-tr 4512  df-eprel 4756  df-id 4760  df-po 4766  df-so 4767  df-fr 4804  df-se 4805  df-we 4806  df-xp 4851  df-rel 4852  df-cnv 4853  df-co 4854  df-dm 4855  df-rn 4856  df-res 4857  df-ima 4858  df-pred 5390  df-ord 5436  df-on 5437  df-lim 5438  df-suc 5439  df-iota 5556  df-fun 5594  df-fn 5595  df-f 5596  df-f1 5597  df-fo 5598  df-f1o 5599  df-fv 5600  df-isom 5601  df-riota 6258  df-ov 6299  df-oprab 6300  df-mpt2 6301  df-om 6698  df-1st 6798  df-2nd 6799  df-wrecs 7027  df-recs 7089  df-rdg 7127  df-1o 7181  df-2o 7182  df-oadd 7185  df-er 7362  df-map 7473  df-pm 7474  df-en 7569  df-dom 7570  df-sdom 7571  df-fin 7572  df-sup 7953  df-oi 8016  df-card 8363  df-cda 8587  df-pnf 9666  df-mnf 9667  df-xr 9668  df-ltxr 9669  df-le 9670  df-sub 9851  df-neg 9852  df-div 10259  df-nn 10599  df-2 10657  df-3 10658  df-n0 10859  df-z 10927  df-uz 11149  df-rp 11292  df-xadd 11399  df-fz 11772  df-fzo 11903  df-seq 12200  df-exp 12259  df-hash 12502  df-word 12640  df-cj 13130  df-re 13131  df-im 13132  df-sqrt 13266  df-abs 13267  df-clim 13519  df-sum 13720  df-usgra 24932  df-nbgra 25019  df-wlk 25107  df-trail 25108  df-pth 25109  df-spth 25110  df-wlkon 25113  df-spthon 25116  df-2wlkonot 25457  df-2spthonot 25459  df-2spthsot 25460  df-vdgr 25493 This theorem is referenced by:  frgregordn0  25669
 Copyright terms: Public domain W3C validator