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

Theorem frgrhash2wsp 27407
 Description: The number of simple paths of length 2 is n*(n-1) in a friendship graph with n vertices. This corresponds to the proof of claim 3 in [Huneke] p. 2: "... the paths of length two in G: by assumption there are ( n 2 ) such paths.". However, Huneke counts undirected paths, so obtains the result ((𝑛C2) = ((𝑛 · (𝑛 − 1)) / 2)), whereas we count directed paths, obtaining twice that number. (Contributed by Alexander van der Vekens, 6-Mar-2018.) (Revised by AV, 10-Jan-2022.)
Hypothesis
Ref Expression
frgrhash2wsp.v 𝑉 = (Vtx‘𝐺)
Assertion
Ref Expression
frgrhash2wsp ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) → (♯‘(2 WSPathsN 𝐺)) = ((♯‘𝑉) · ((♯‘𝑉) − 1)))

Proof of Theorem frgrhash2wsp
Dummy variables 𝑎 𝑏 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 2nn 11298 . . . . 5 2 ∈ ℕ
2 frgrhash2wsp.v . . . . . 6 𝑉 = (Vtx‘𝐺)
32wspniunwspnon 26964 . . . . 5 ((2 ∈ ℕ ∧ 𝐺 ∈ FriendGraph ) → (2 WSPathsN 𝐺) = 𝑎𝑉 𝑏 ∈ (𝑉 ∖ {𝑎})(𝑎(2 WSPathsNOn 𝐺)𝑏))
41, 3mpan 708 . . . 4 (𝐺 ∈ FriendGraph → (2 WSPathsN 𝐺) = 𝑎𝑉 𝑏 ∈ (𝑉 ∖ {𝑎})(𝑎(2 WSPathsNOn 𝐺)𝑏))
54fveq2d 6308 . . 3 (𝐺 ∈ FriendGraph → (♯‘(2 WSPathsN 𝐺)) = (♯‘ 𝑎𝑉 𝑏 ∈ (𝑉 ∖ {𝑎})(𝑎(2 WSPathsNOn 𝐺)𝑏)))
65adantr 472 . 2 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) → (♯‘(2 WSPathsN 𝐺)) = (♯‘ 𝑎𝑉 𝑏 ∈ (𝑉 ∖ {𝑎})(𝑎(2 WSPathsNOn 𝐺)𝑏)))
7 simpr 479 . . 3 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) → 𝑉 ∈ Fin)
8 eqid 2724 . . 3 (𝑉 ∖ {𝑎}) = (𝑉 ∖ {𝑎})
92eleq1i 2794 . . . . . 6 (𝑉 ∈ Fin ↔ (Vtx‘𝐺) ∈ Fin)
10 wspthnonfi 26963 . . . . . 6 ((Vtx‘𝐺) ∈ Fin → (𝑎(2 WSPathsNOn 𝐺)𝑏) ∈ Fin)
119, 10sylbi 207 . . . . 5 (𝑉 ∈ Fin → (𝑎(2 WSPathsNOn 𝐺)𝑏) ∈ Fin)
1211adantl 473 . . . 4 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) → (𝑎(2 WSPathsNOn 𝐺)𝑏) ∈ Fin)
13123ad2ant1 1125 . . 3 (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) ∧ 𝑎𝑉𝑏 ∈ (𝑉 ∖ {𝑎})) → (𝑎(2 WSPathsNOn 𝐺)𝑏) ∈ Fin)
14 2wspiundisj 27006 . . . 4 Disj 𝑎𝑉 𝑏 ∈ (𝑉 ∖ {𝑎})(𝑎(2 WSPathsNOn 𝐺)𝑏)
1514a1i 11 . . 3 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) → Disj 𝑎𝑉 𝑏 ∈ (𝑉 ∖ {𝑎})(𝑎(2 WSPathsNOn 𝐺)𝑏))
16 2wspdisj 27005 . . . 4 Disj 𝑏 ∈ (𝑉 ∖ {𝑎})(𝑎(2 WSPathsNOn 𝐺)𝑏)
1716a1i 11 . . 3 (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) ∧ 𝑎𝑉) → Disj 𝑏 ∈ (𝑉 ∖ {𝑎})(𝑎(2 WSPathsNOn 𝐺)𝑏))
18 simplll 815 . . . . 5 ((((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) ∧ 𝑎𝑉) ∧ 𝑏 ∈ (𝑉 ∖ {𝑎})) → 𝐺 ∈ FriendGraph )
19 simpr 479 . . . . . 6 (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) ∧ 𝑎𝑉) → 𝑎𝑉)
20 eldifi 3840 . . . . . 6 (𝑏 ∈ (𝑉 ∖ {𝑎}) → 𝑏𝑉)
2119, 20anim12i 591 . . . . 5 ((((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) ∧ 𝑎𝑉) ∧ 𝑏 ∈ (𝑉 ∖ {𝑎})) → (𝑎𝑉𝑏𝑉))
22 eldifsni 4429 . . . . . . 7 (𝑏 ∈ (𝑉 ∖ {𝑎}) → 𝑏𝑎)
2322necomd 2951 . . . . . 6 (𝑏 ∈ (𝑉 ∖ {𝑎}) → 𝑎𝑏)
2423adantl 473 . . . . 5 ((((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) ∧ 𝑎𝑉) ∧ 𝑏 ∈ (𝑉 ∖ {𝑎})) → 𝑎𝑏)
252frgr2wsp1 27405 . . . . 5 ((𝐺 ∈ FriendGraph ∧ (𝑎𝑉𝑏𝑉) ∧ 𝑎𝑏) → (♯‘(𝑎(2 WSPathsNOn 𝐺)𝑏)) = 1)
2618, 21, 24, 25syl3anc 1439 . . . 4 ((((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) ∧ 𝑎𝑉) ∧ 𝑏 ∈ (𝑉 ∖ {𝑎})) → (♯‘(𝑎(2 WSPathsNOn 𝐺)𝑏)) = 1)
27263impa 1100 . . 3 (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) ∧ 𝑎𝑉𝑏 ∈ (𝑉 ∖ {𝑎})) → (♯‘(𝑎(2 WSPathsNOn 𝐺)𝑏)) = 1)
287, 8, 13, 15, 17, 27hash2iun1dif1 14676 . 2 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) → (♯‘ 𝑎𝑉 𝑏 ∈ (𝑉 ∖ {𝑎})(𝑎(2 WSPathsNOn 𝐺)𝑏)) = ((♯‘𝑉) · ((♯‘𝑉) − 1)))
296, 28eqtrd 2758 1 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) → (♯‘(2 WSPathsN 𝐺)) = ((♯‘𝑉) · ((♯‘𝑉) − 1)))
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ∧ wa 383   = wceq 1596   ∈ wcel 2103   ≠ wne 2896   ∖ cdif 3677  {csn 4285  ∪ ciun 4628  Disj wdisj 4728  ‘cfv 6001  (class class class)co 6765  Fincfn 8072  1c1 10050   · cmul 10054   − cmin 10379  ℕcn 11133  2c2 11183  ♯chash 13232  Vtxcvtx 25994   WSPathsN cwwspthsn 26852   WSPathsNOn cwwspthsnon 26853   FriendGraph cfrgr 27331 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1835  ax-4 1850  ax-5 1952  ax-6 2018  ax-7 2054  ax-8 2105  ax-9 2112  ax-10 2132  ax-11 2147  ax-12 2160  ax-13 2355  ax-ext 2704  ax-rep 4879  ax-sep 4889  ax-nul 4897  ax-pow 4948  ax-pr 5011  ax-un 7066  ax-inf2 8651  ax-ac2 9398  ax-cnex 10105  ax-resscn 10106  ax-1cn 10107  ax-icn 10108  ax-addcl 10109  ax-addrcl 10110  ax-mulcl 10111  ax-mulrcl 10112  ax-mulcom 10113  ax-addass 10114  ax-mulass 10115  ax-distr 10116  ax-i2m1 10117  ax-1ne0 10118  ax-1rid 10119  ax-rnegex 10120  ax-rrecex 10121  ax-cnre 10122  ax-pre-lttri 10123  ax-pre-lttrn 10124  ax-pre-ltadd 10125  ax-pre-mulgt0 10126  ax-pre-sup 10127 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 1599  df-fal 1602  df-ex 1818  df-nf 1823  df-sb 2011  df-eu 2575  df-mo 2576  df-clab 2711  df-cleq 2717  df-clel 2720  df-nfc 2855  df-ne 2897  df-nel 3000  df-ral 3019  df-rex 3020  df-reu 3021  df-rmo 3022  df-rab 3023  df-v 3306  df-sbc 3542  df-csb 3640  df-dif 3683  df-un 3685  df-in 3687  df-ss 3694  df-pss 3696  df-nul 4024  df-if 4195  df-pw 4268  df-sn 4286  df-pr 4288  df-tp 4290  df-op 4292  df-uni 4545  df-int 4584  df-iun 4630  df-disj 4729  df-br 4761  df-opab 4821  df-mpt 4838  df-tr 4861  df-id 5128  df-eprel 5133  df-po 5139  df-so 5140  df-fr 5177  df-se 5178  df-we 5179  df-xp 5224  df-rel 5225  df-cnv 5226  df-co 5227  df-dm 5228  df-rn 5229  df-res 5230  df-ima 5231  df-pred 5793  df-ord 5839  df-on 5840  df-lim 5841  df-suc 5842  df-iota 5964  df-fun 6003  df-fn 6004  df-f 6005  df-f1 6006  df-fo 6007  df-f1o 6008  df-fv 6009  df-isom 6010  df-riota 6726  df-ov 6768  df-oprab 6769  df-mpt2 6770  df-om 7183  df-1st 7285  df-2nd 7286  df-wrecs 7527  df-recs 7588  df-rdg 7626  df-1o 7680  df-2o 7681  df-oadd 7684  df-er 7862  df-map 7976  df-pm 7977  df-en 8073  df-dom 8074  df-sdom 8075  df-fin 8076  df-sup 8464  df-oi 8531  df-card 8878  df-ac 9052  df-cda 9103  df-pnf 10189  df-mnf 10190  df-xr 10191  df-ltxr 10192  df-le 10193  df-sub 10381  df-neg 10382  df-div 10798  df-nn 11134  df-2 11192  df-3 11193  df-n0 11406  df-xnn0 11477  df-z 11491  df-uz 11801  df-rp 11947  df-fz 12441  df-fzo 12581  df-seq 12917  df-exp 12976  df-hash 13233  df-word 13406  df-concat 13408  df-s1 13409  df-s2 13714  df-s3 13715  df-cj 13959  df-re 13960  df-im 13961  df-sqrt 14095  df-abs 14096  df-clim 14339  df-sum 14537  df-edg 26060  df-uhgr 26073  df-upgr 26097  df-umgr 26098  df-uspgr 26165  df-usgr 26166  df-wlks 26626  df-wlkson 26627  df-trls 26720  df-trlson 26721  df-pths 26743  df-spths 26744  df-pthson 26745  df-spthson 26746  df-wwlks 26854  df-wwlksn 26855  df-wwlksnon 26856  df-wspthsn 26857  df-wspthsnon 26858  df-frgr 27332 This theorem is referenced by:  frrusgrord0  27415
 Copyright terms: Public domain W3C validator