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

Theorem frghash2spot 30661
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 the third claim in the proof of the friendship theorem in [Huneke] p. 2: "... the paths of length two in G: by assumption there are ( n 2 ) such paths.". However, the order of vertices is not respected by Huneke, so he only counts half of the paths which are existing when respecting the order as it is the case for simple paths represented by orderes triples. (Contributed by Alexander van der Vekens, 6-Mar-2018.)
Assertion
Ref Expression
frghash2spot  |-  ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  -> 
( # `  ( V 2SPathOnOt  E ) )  =  ( ( # `  V
)  x.  ( (
# `  V )  -  1 ) ) )

Proof of Theorem frghash2spot
Dummy variables  a 
b are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 frisusgra 30589 . . . . 5  |-  ( V FriendGrph  E  ->  V USGrph  E )
2 usgrav 23275 . . . . 5  |-  ( V USGrph  E  ->  ( V  e. 
_V  /\  E  e.  _V ) )
3 2spot2iun2spont 30415 . . . . 5  |-  ( ( V  e.  _V  /\  E  e.  _V )  ->  ( V 2SPathOnOt  E )  =  U_ a  e.  V  U_ b  e.  ( V 
\  { a } ) ( a ( V 2SPathOnOt  E ) b ) )
41, 2, 33syl 20 . . . 4  |-  ( V FriendGrph  E  ->  ( V 2SPathOnOt  E )  =  U_ a  e.  V  U_ b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b ) )
54fveq2d 5700 . . 3  |-  ( V FriendGrph  E  ->  ( # `  ( V 2SPathOnOt  E ) )  =  ( # `  U_ a  e.  V  U_ b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b ) ) )
65adantr 465 . 2  |-  ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  -> 
( # `  ( V 2SPathOnOt  E ) )  =  ( # `  U_ a  e.  V  U_ b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b ) ) )
7 simpl 457 . . . 4  |-  ( ( V  e.  Fin  /\  V  =/=  (/) )  ->  V  e.  Fin )
87adantl 466 . . 3  |-  ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  ->  V  e.  Fin )
9 diffi 7548 . . . . . . 7  |-  ( V  e.  Fin  ->  ( V  \  { a } )  e.  Fin )
109adantr 465 . . . . . 6  |-  ( ( V  e.  Fin  /\  V  =/=  (/) )  ->  ( V  \  { a } )  e.  Fin )
1110adantl 466 . . . . 5  |-  ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  -> 
( V  \  {
a } )  e. 
Fin )
1211adantr 465 . . . 4  |-  ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  ->  ( V  \  { a } )  e.  Fin )
13 simpr 461 . . . . . . . . . 10  |-  ( ( V  e.  _V  /\  E  e.  _V )  ->  E  e.  _V )
141, 2, 133syl 20 . . . . . . . . 9  |-  ( V FriendGrph  E  ->  E  e.  _V )
1514, 7anim12ci 567 . . . . . . . 8  |-  ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  -> 
( V  e.  Fin  /\  E  e.  _V )
)
1615adantr 465 . . . . . . 7  |-  ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  ->  ( V  e.  Fin  /\  E  e. 
_V ) )
1716adantr 465 . . . . . 6  |-  ( ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  /\  b  e.  ( V  \  { a } ) )  -> 
( V  e.  Fin  /\  E  e.  _V )
)
18 simpr 461 . . . . . . 7  |-  ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  ->  a  e.  V )
19 eldifi 3483 . . . . . . 7  |-  ( b  e.  ( V  \  { a } )  ->  b  e.  V
)
2018, 19anim12i 566 . . . . . 6  |-  ( ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  /\  b  e.  ( V  \  { a } ) )  -> 
( a  e.  V  /\  b  e.  V
) )
21 2spotfi 30416 . . . . . 6  |-  ( ( ( V  e.  Fin  /\  E  e.  _V )  /\  ( a  e.  V  /\  b  e.  V
) )  ->  (
a ( V 2SPathOnOt  E ) b )  e.  Fin )
2217, 20, 21syl2anc 661 . . . . 5  |-  ( ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  /\  b  e.  ( V  \  { a } ) )  -> 
( a ( V 2SPathOnOt  E ) b )  e.  Fin )
2322ralrimiva 2804 . . . 4  |-  ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  ->  A. b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b )  e.  Fin )
24 iunfi 7604 . . . 4  |-  ( ( ( V  \  {
a } )  e. 
Fin  /\  A. b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b )  e.  Fin )  ->  U_ b  e.  ( V  \  { a } ) ( a ( V 2SPathOnOt  E )
b )  e.  Fin )
2512, 23, 24syl2anc 661 . . 3  |-  ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  ->  U_ b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b )  e.  Fin )
26 2spotiundisj 30660 . . . . 5  |-  ( ( V  e.  _V  /\  E  e.  _V )  -> Disj  a  e.  V  U_ b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b ) )
271, 2, 263syl 20 . . . 4  |-  ( V FriendGrph  E  -> Disj  a  e.  V  U_ b  e.  ( V  \  { a } ) ( a ( V 2SPathOnOt  E ) b ) )
2827adantr 465 . . 3  |-  ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  -> Disj  a  e.  V  U_ b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b ) )
298, 25, 28hashiun 13290 . 2  |-  ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  -> 
( # `  U_ a  e.  V  U_ b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b ) )  = 
sum_ a  e.  V  ( # `  U_ b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b ) ) )
30 2spotdisj 30659 . . . . . . 7  |-  ( ( ( V  e.  Fin  /\  E  e.  _V )  /\  a  e.  V
)  -> Disj  b  e.  ( V  \  { a } ) ( a ( V 2SPathOnOt  E )
b ) )
3115, 30sylan 471 . . . . . 6  |-  ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  -> Disj  b  e.  ( V  \  { a } ) ( a ( V 2SPathOnOt  E )
b ) )
3212, 22, 31hashiun 13290 . . . . 5  |-  ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  ->  ( # `  U_ b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b ) )  = 
sum_ b  e.  ( V  \  { a } ) ( # `  ( a ( V 2SPathOnOt  E ) b ) ) )
33 simplll 757 . . . . . . 7  |-  ( ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  /\  b  e.  ( V  \  { a } ) )  ->  V FriendGrph  E )
34 eldifsni 4006 . . . . . . . . 9  |-  ( b  e.  ( V  \  { a } )  ->  b  =/=  a
)
3534necomd 2700 . . . . . . . 8  |-  ( b  e.  ( V  \  { a } )  ->  a  =/=  b
)
3635adantl 466 . . . . . . 7  |-  ( ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  /\  b  e.  ( V  \  { a } ) )  -> 
a  =/=  b )
37 frg2spot1 30656 . . . . . . 7  |-  ( ( V FriendGrph  E  /\  (
a  e.  V  /\  b  e.  V )  /\  a  =/=  b
)  ->  ( # `  (
a ( V 2SPathOnOt  E ) b ) )  =  1 )
3833, 20, 36, 37syl3anc 1218 . . . . . 6  |-  ( ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  /\  b  e.  ( V  \  { a } ) )  -> 
( # `  ( a ( V 2SPathOnOt  E )
b ) )  =  1 )
3938sumeq2dv 13185 . . . . 5  |-  ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  ->  sum_ b  e.  ( V  \  {
a } ) (
# `  ( a
( V 2SPathOnOt  E ) b ) )  =  sum_ b  e.  ( V  \  { a } ) 1 )
40 ax-1cn 9345 . . . . . . . . . . 11  |-  1  e.  CC
419, 40jctir 538 . . . . . . . . . 10  |-  ( V  e.  Fin  ->  (
( V  \  {
a } )  e. 
Fin  /\  1  e.  CC ) )
4241adantr 465 . . . . . . . . 9  |-  ( ( V  e.  Fin  /\  V  =/=  (/) )  ->  (
( V  \  {
a } )  e. 
Fin  /\  1  e.  CC ) )
4342adantr 465 . . . . . . . 8  |-  ( ( ( V  e.  Fin  /\  V  =/=  (/) )  /\  a  e.  V )  ->  ( ( V  \  { a } )  e.  Fin  /\  1  e.  CC ) )
44 fsumconst 13262 . . . . . . . 8  |-  ( ( ( V  \  {
a } )  e. 
Fin  /\  1  e.  CC )  ->  sum_ b  e.  ( V  \  {
a } ) 1  =  ( ( # `  ( V  \  {
a } ) )  x.  1 ) )
4543, 44syl 16 . . . . . . 7  |-  ( ( ( V  e.  Fin  /\  V  =/=  (/) )  /\  a  e.  V )  -> 
sum_ b  e.  ( V  \  { a } ) 1  =  ( ( # `  ( V  \  { a } ) )  x.  1 ) )
46 hashdifsn 12174 . . . . . . . . 9  |-  ( ( V  e.  Fin  /\  a  e.  V )  ->  ( # `  ( V  \  { a } ) )  =  ( ( # `  V
)  -  1 ) )
4746adantlr 714 . . . . . . . 8  |-  ( ( ( V  e.  Fin  /\  V  =/=  (/) )  /\  a  e.  V )  ->  ( # `  ( V  \  { a } ) )  =  ( ( # `  V
)  -  1 ) )
4847oveq1d 6111 . . . . . . 7  |-  ( ( ( V  e.  Fin  /\  V  =/=  (/) )  /\  a  e.  V )  ->  ( ( # `  ( V  \  { a } ) )  x.  1 )  =  ( ( ( # `  V
)  -  1 )  x.  1 ) )
49 hashnncl 12139 . . . . . . . . . . . 12  |-  ( V  e.  Fin  ->  (
( # `  V )  e.  NN  <->  V  =/=  (/) ) )
5049biimpar 485 . . . . . . . . . . 11  |-  ( ( V  e.  Fin  /\  V  =/=  (/) )  ->  ( # `
 V )  e.  NN )
51 nnm1nn0 10626 . . . . . . . . . . 11  |-  ( (
# `  V )  e.  NN  ->  ( ( # `
 V )  - 
1 )  e.  NN0 )
5250, 51syl 16 . . . . . . . . . 10  |-  ( ( V  e.  Fin  /\  V  =/=  (/) )  ->  (
( # `  V )  -  1 )  e. 
NN0 )
5352nn0red 10642 . . . . . . . . 9  |-  ( ( V  e.  Fin  /\  V  =/=  (/) )  ->  (
( # `  V )  -  1 )  e.  RR )
54 ax-1rid 9357 . . . . . . . . 9  |-  ( ( ( # `  V
)  -  1 )  e.  RR  ->  (
( ( # `  V
)  -  1 )  x.  1 )  =  ( ( # `  V
)  -  1 ) )
5553, 54syl 16 . . . . . . . 8  |-  ( ( V  e.  Fin  /\  V  =/=  (/) )  ->  (
( ( # `  V
)  -  1 )  x.  1 )  =  ( ( # `  V
)  -  1 ) )
5655adantr 465 . . . . . . 7  |-  ( ( ( V  e.  Fin  /\  V  =/=  (/) )  /\  a  e.  V )  ->  ( ( ( # `  V )  -  1 )  x.  1 )  =  ( ( # `  V )  -  1 ) )
5745, 48, 563eqtrd 2479 . . . . . 6  |-  ( ( ( V  e.  Fin  /\  V  =/=  (/) )  /\  a  e.  V )  -> 
sum_ b  e.  ( V  \  { a } ) 1  =  ( ( # `  V
)  -  1 ) )
5857adantll 713 . . . . 5  |-  ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  ->  sum_ b  e.  ( V  \  {
a } ) 1  =  ( ( # `  V )  -  1 ) )
5932, 39, 583eqtrd 2479 . . . 4  |-  ( ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  /\  a  e.  V
)  ->  ( # `  U_ b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b ) )  =  ( ( # `  V
)  -  1 ) )
6059sumeq2dv 13185 . . 3  |-  ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  ->  sum_ a  e.  V  (
# `  U_ b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b ) )  = 
sum_ a  e.  V  ( ( # `  V
)  -  1 ) )
61 hashcl 12131 . . . . . . . 8  |-  ( V  e.  Fin  ->  ( # `
 V )  e. 
NN0 )
6261nn0cnd 10643 . . . . . . 7  |-  ( V  e.  Fin  ->  ( # `
 V )  e.  CC )
6340a1i 11 . . . . . . 7  |-  ( V  e.  Fin  ->  1  e.  CC )
6462, 63subcld 9724 . . . . . 6  |-  ( V  e.  Fin  ->  (
( # `  V )  -  1 )  e.  CC )
65 fsumconst 13262 . . . . . 6  |-  ( ( V  e.  Fin  /\  ( ( # `  V
)  -  1 )  e.  CC )  ->  sum_ a  e.  V  ( ( # `  V
)  -  1 )  =  ( ( # `  V )  x.  (
( # `  V )  -  1 ) ) )
6664, 65mpdan 668 . . . . 5  |-  ( V  e.  Fin  ->  sum_ a  e.  V  ( ( # `
 V )  - 
1 )  =  ( ( # `  V
)  x.  ( (
# `  V )  -  1 ) ) )
6766adantr 465 . . . 4  |-  ( ( V  e.  Fin  /\  V  =/=  (/) )  ->  sum_ a  e.  V  ( ( # `
 V )  - 
1 )  =  ( ( # `  V
)  x.  ( (
# `  V )  -  1 ) ) )
6867adantl 466 . . 3  |-  ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  ->  sum_ a  e.  V  ( ( # `  V
)  -  1 )  =  ( ( # `  V )  x.  (
( # `  V )  -  1 ) ) )
6960, 68eqtrd 2475 . 2  |-  ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  ->  sum_ a  e.  V  (
# `  U_ b  e.  ( V  \  {
a } ) ( a ( V 2SPathOnOt  E ) b ) )  =  ( ( # `  V
)  x.  ( (
# `  V )  -  1 ) ) )
706, 29, 693eqtrd 2479 1  |-  ( ( V FriendGrph  E  /\  ( V  e.  Fin  /\  V  =/=  (/) ) )  -> 
( # `  ( V 2SPathOnOt  E ) )  =  ( ( # `  V
)  x.  ( (
# `  V )  -  1 ) ) )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    /\ wa 369    = wceq 1369    e. wcel 1756    =/= wne 2611   A.wral 2720   _Vcvv 2977    \ cdif 3330   (/)c0 3642   {csn 3882   U_ciun 4176  Disj wdisj 4267   class class class wbr 4297   ` cfv 5423  (class class class)co 6096   Fincfn 7315   CCcc 9285   RRcr 9286   1c1 9288    x. cmul 9292    - cmin 9600   NNcn 10327   NN0cn0 10584   #chash 12108   sum_csu 13168   USGrph cusg 23269   2SPathOnOt c2spthot 30380   2SPathOnOt c2pthonot 30381   FriendGrph cfrgra 30585
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1591  ax-4 1602  ax-5 1670  ax-6 1708  ax-7 1728  ax-8 1758  ax-9 1760  ax-10 1775  ax-11 1780  ax-12 1792  ax-13 1943  ax-ext 2423  ax-rep 4408  ax-sep 4418  ax-nul 4426  ax-pow 4475  ax-pr 4536  ax-un 6377  ax-inf2 7852  ax-cnex 9343  ax-resscn 9344  ax-1cn 9345  ax-icn 9346  ax-addcl 9347  ax-addrcl 9348  ax-mulcl 9349  ax-mulrcl 9350  ax-mulcom 9351  ax-addass 9352  ax-mulass 9353  ax-distr 9354  ax-i2m1 9355  ax-1ne0 9356  ax-1rid 9357  ax-rnegex 9358  ax-rrecex 9359  ax-cnre 9360  ax-pre-lttri 9361  ax-pre-lttrn 9362  ax-pre-ltadd 9363  ax-pre-mulgt0 9364  ax-pre-sup 9365
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 966  df-3an 967  df-tru 1372  df-fal 1375  df-ex 1587  df-nf 1590  df-sb 1701  df-eu 2257  df-mo 2258  df-clab 2430  df-cleq 2436  df-clel 2439  df-nfc 2573  df-ne 2613  df-nel 2614  df-ral 2725  df-rex 2726  df-reu 2727  df-rmo 2728  df-rab 2729  df-v 2979  df-sbc 3192  df-csb 3294  df-dif 3336  df-un 3338  df-in 3340  df-ss 3347  df-pss 3349  df-nul 3643  df-if 3797  df-pw 3867  df-sn 3883  df-pr 3885  df-tp 3887  df-op 3889  df-ot 3891  df-uni 4097  df-int 4134  df-iun 4178  df-disj 4268  df-br 4298  df-opab 4356  df-mpt 4357  df-tr 4391  df-eprel 4637  df-id 4641  df-po 4646  df-so 4647  df-fr 4684  df-se 4685  df-we 4686  df-ord 4727  df-on 4728  df-lim 4729  df-suc 4730  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-iota 5386  df-fun 5425  df-fn 5426  df-f 5427  df-f1 5428  df-fo 5429  df-f1o 5430  df-fv 5431  df-isom 5432  df-riota 6057  df-ov 6099  df-oprab 6100  df-mpt2 6101  df-om 6482  df-1st 6582  df-2nd 6583  df-recs 6837  df-rdg 6871  df-1o 6925  df-oadd 6929  df-er 7106  df-map 7221  df-pm 7222  df-en 7316  df-dom 7317  df-sdom 7318  df-fin 7319  df-sup 7696  df-oi 7729  df-card 8114  df-cda 8342  df-pnf 9425  df-mnf 9426  df-xr 9427  df-ltxr 9428  df-le 9429  df-sub 9602  df-neg 9603  df-div 9999  df-nn 10328  df-2 10385  df-3 10386  df-n0 10585  df-z 10652  df-uz 10867  df-rp 10997  df-fz 11443  df-fzo 11554  df-seq 11812  df-exp 11871  df-hash 12109  df-word 12234  df-cj 12593  df-re 12594  df-im 12595  df-sqr 12729  df-abs 12730  df-clim 12971  df-sum 13169  df-usgra 23271  df-wlk 23420  df-trail 23421  df-pth 23422  df-spth 23423  df-wlkon 23426  df-spthon 23429  df-2wlkonot 30382  df-2spthonot 30384  df-2spthsot 30385  df-frgra 30586
This theorem is referenced by:  frgregordn0  30668
  Copyright terms: Public domain W3C validator