Theorem numclwwlk1 30049

Description: Statement 9 in [Huneke] p. 2: "If n > 1, then the number of closed n-walks v(0) ... v(n-2) v(n-1) v(n) from v = v(0) = v(n) with v(n-2) = v is kf(n-2)". Since 𝐺 is k-regular, the vertex v(n-2) = v has k neighbors v(n-1), so there are k walks from v(n-2) = v to v(n) = v (via each of v's neighbors) completing each of the f(n-2) walks from v=v(0) to v(n-2)=v. This theorem holds even for k=0, but not for n=2, since 𝐹 = ∅, but (𝑋𝐶2), the set of closed walks with length 2 on 𝑋, see 2clwwlk2 30036, needs not be ∅ in this case. This is because of the special definition of 𝐹 and the usage of words to represent (closed) walks, and does not contradict Huneke's statement, which would read "the number of closed 2-walks v(0) v(1) v(2) from v = v(0) = v(2) ... is kf(0)", where f(0)=1 is the number of empty closed walks on v, see numclwlk1lem1 30057. If the general representation of (closed) walk is used, Huneke's statement can be proven even for n = 2, see numclwlk1 30059. This case, however, is not required to prove the friendship theorem. (Contributed by Alexander van der Vekens, 26-Sep-2018.) (Revised by AV, 29-May-2021.) (Revised by AV, 6-Mar-2022.) (Proof shortened by AV, 31-Jul-2022.)

Hypotheses

Ref	Expression
extwwlkfab.v	⊢ 𝑉 = (Vtx‘𝐺)
extwwlkfab.c	⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})
extwwlkfab.f	⊢ 𝐹 = (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2))

Assertion

Ref	Expression
numclwwlk1	⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → (♯‘(𝑋𝐶𝑁)) = (𝐾 · (♯‘𝐹)))

Distinct variable groups:   𝑛,𝐺,𝑣,𝑤   𝑛,𝑁,𝑣,𝑤   𝑛,𝑉,𝑣,𝑤   𝑛,𝑋,𝑣,𝑤   𝑤,𝐹

Allowed substitution hints:   𝐶(𝑤,𝑣,𝑛)   𝐹(𝑣,𝑛)   𝐾(𝑤,𝑣,𝑛)

Proof of Theorem numclwwlk1

Dummy variable 𝑥 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		rusgrusgr 29256	. . . . 5 ⊢ (𝐺 RegUSGraph 𝐾 → 𝐺 ∈ USGraph)
2	1	ad2antlr 724	. . . 4 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → 𝐺 ∈ USGraph)
3		simprl 768	. . . 4 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → 𝑋 ∈ 𝑉)
4		simprr 770	. . . 4 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → 𝑁 ∈ (ℤ≥‘3))
5		extwwlkfab.v	. . . . 5 ⊢ 𝑉 = (Vtx‘𝐺)
6		extwwlkfab.c	. . . . 5 ⊢ 𝐶 = (𝑣 ∈ 𝑉, 𝑛 ∈ (ℤ≥‘2) ↦ {𝑤 ∈ (𝑣(ClWWalksNOn‘𝐺)𝑛) ∣ (𝑤‘(𝑛 − 2)) = 𝑣})
7		extwwlkfab.f	. . . . 5 ⊢ 𝐹 = (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2))
8	5, 6, 7	numclwwlk1lem2 30048	. . . 4 ⊢ ((𝐺 ∈ USGraph ∧ 𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3)) → (𝑋𝐶𝑁) ≈ (𝐹 × (𝐺 NeighbVtx 𝑋)))
9	2, 3, 4, 8	syl3anc 1368	. . 3 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → (𝑋𝐶𝑁) ≈ (𝐹 × (𝐺 NeighbVtx 𝑋)))
10		hasheni 14304	. . 3 ⊢ ((𝑋𝐶𝑁) ≈ (𝐹 × (𝐺 NeighbVtx 𝑋)) → (♯‘(𝑋𝐶𝑁)) = (♯‘(𝐹 × (𝐺 NeighbVtx 𝑋))))
11	9, 10	syl 17	. 2 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → (♯‘(𝑋𝐶𝑁)) = (♯‘(𝐹 × (𝐺 NeighbVtx 𝑋))))
12		eqid 2724	. . . . . . 7 ⊢ (Vtx‘𝐺) = (Vtx‘𝐺)
13	12	clwwlknonfin 29782	. . . . . 6 ⊢ ((Vtx‘𝐺) ∈ Fin → (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2)) ∈ Fin)
14	5	eleq1i 2816	. . . . . 6 ⊢ (𝑉 ∈ Fin ↔ (Vtx‘𝐺) ∈ Fin)
15	7	eleq1i 2816	. . . . . 6 ⊢ (𝐹 ∈ Fin ↔ (𝑋(ClWWalksNOn‘𝐺)(𝑁 − 2)) ∈ Fin)
16	13, 14, 15	3imtr4i 292	. . . . 5 ⊢ (𝑉 ∈ Fin → 𝐹 ∈ Fin)
17	16	adantr 480	. . . 4 ⊢ ((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) → 𝐹 ∈ Fin)
18	17	adantr 480	. . 3 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → 𝐹 ∈ Fin)
19	5	finrusgrfusgr 29257	. . . . . . 7 ⊢ ((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) → 𝐺 ∈ FinUSGraph)
20	19	ancoms 458	. . . . . 6 ⊢ ((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) → 𝐺 ∈ FinUSGraph)
21		fusgrfis 29022	. . . . . 6 ⊢ (𝐺 ∈ FinUSGraph → (Edg‘𝐺) ∈ Fin)
22	20, 21	syl 17	. . . . 5 ⊢ ((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) → (Edg‘𝐺) ∈ Fin)
23	22	adantr 480	. . . 4 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → (Edg‘𝐺) ∈ Fin)
24		eqid 2724	. . . . 5 ⊢ (Edg‘𝐺) = (Edg‘𝐺)
25	5, 24	nbusgrfi 29066	. . . 4 ⊢ ((𝐺 ∈ USGraph ∧ (Edg‘𝐺) ∈ Fin ∧ 𝑋 ∈ 𝑉) → (𝐺 NeighbVtx 𝑋) ∈ Fin)
26	2, 23, 3, 25	syl3anc 1368	. . 3 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → (𝐺 NeighbVtx 𝑋) ∈ Fin)
27		hashxp 14390	. . 3 ⊢ ((𝐹 ∈ Fin ∧ (𝐺 NeighbVtx 𝑋) ∈ Fin) → (♯‘(𝐹 × (𝐺 NeighbVtx 𝑋))) = ((♯‘𝐹) · (♯‘(𝐺 NeighbVtx 𝑋))))
28	18, 26, 27	syl2anc 583	. 2 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → (♯‘(𝐹 × (𝐺 NeighbVtx 𝑋))) = ((♯‘𝐹) · (♯‘(𝐺 NeighbVtx 𝑋))))
29	5	rusgrpropnb 29275	. . . . . . . . 9 ⊢ (𝐺 RegUSGraph 𝐾 → (𝐺 ∈ USGraph ∧ 𝐾 ∈ ℕ0* ∧ ∀𝑥 ∈ 𝑉 (♯‘(𝐺 NeighbVtx 𝑥)) = 𝐾))
30		oveq2 7409	. . . . . . . . . . . 12 ⊢ (𝑥 = 𝑋 → (𝐺 NeighbVtx 𝑥) = (𝐺 NeighbVtx 𝑋))
31	30	fveqeq2d 6889	. . . . . . . . . . 11 ⊢ (𝑥 = 𝑋 → ((♯‘(𝐺 NeighbVtx 𝑥)) = 𝐾 ↔ (♯‘(𝐺 NeighbVtx 𝑋)) = 𝐾))
32	31	rspccv 3601	. . . . . . . . . 10 ⊢ (∀𝑥 ∈ 𝑉 (♯‘(𝐺 NeighbVtx 𝑥)) = 𝐾 → (𝑋 ∈ 𝑉 → (♯‘(𝐺 NeighbVtx 𝑋)) = 𝐾))
33	32	3ad2ant3 1132	. . . . . . . . 9 ⊢ ((𝐺 ∈ USGraph ∧ 𝐾 ∈ ℕ0* ∧ ∀𝑥 ∈ 𝑉 (♯‘(𝐺 NeighbVtx 𝑥)) = 𝐾) → (𝑋 ∈ 𝑉 → (♯‘(𝐺 NeighbVtx 𝑋)) = 𝐾))
34	29, 33	syl 17	. . . . . . . 8 ⊢ (𝐺 RegUSGraph 𝐾 → (𝑋 ∈ 𝑉 → (♯‘(𝐺 NeighbVtx 𝑋)) = 𝐾))
35	34	adantl 481	. . . . . . 7 ⊢ ((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) → (𝑋 ∈ 𝑉 → (♯‘(𝐺 NeighbVtx 𝑋)) = 𝐾))
36	35	com12 32	. . . . . 6 ⊢ (𝑋 ∈ 𝑉 → ((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) → (♯‘(𝐺 NeighbVtx 𝑋)) = 𝐾))
37	36	adantr 480	. . . . 5 ⊢ ((𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3)) → ((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) → (♯‘(𝐺 NeighbVtx 𝑋)) = 𝐾))
38	37	impcom 407	. . . 4 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → (♯‘(𝐺 NeighbVtx 𝑋)) = 𝐾)
39	38	oveq2d 7417	. . 3 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → ((♯‘𝐹) · (♯‘(𝐺 NeighbVtx 𝑋))) = ((♯‘𝐹) · 𝐾))
40		hashcl 14312	. . . . 5 ⊢ (𝐹 ∈ Fin → (♯‘𝐹) ∈ ℕ0)
41		nn0cn 12478	. . . . 5 ⊢ ((♯‘𝐹) ∈ ℕ0 → (♯‘𝐹) ∈ ℂ)
42	18, 40, 41	3syl 18	. . . 4 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → (♯‘𝐹) ∈ ℂ)
43	20	adantr 480	. . . . . 6 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → 𝐺 ∈ FinUSGraph)
44		simplr 766	. . . . . 6 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → 𝐺 RegUSGraph 𝐾)
45		ne0i 4326	. . . . . . . 8 ⊢ (𝑋 ∈ 𝑉 → 𝑉 ≠ ∅)
46	45	adantr 480	. . . . . . 7 ⊢ ((𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3)) → 𝑉 ≠ ∅)
47	46	adantl 481	. . . . . 6 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → 𝑉 ≠ ∅)
48	5	frusgrnn0 29263	. . . . . 6 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝐺 RegUSGraph 𝐾 ∧ 𝑉 ≠ ∅) → 𝐾 ∈ ℕ0)
49	43, 44, 47, 48	syl3anc 1368	. . . . 5 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → 𝐾 ∈ ℕ0)
50	49	nn0cnd 12530	. . . 4 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → 𝐾 ∈ ℂ)
51	42, 50	mulcomd 11231	. . 3 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → ((♯‘𝐹) · 𝐾) = (𝐾 · (♯‘𝐹)))
52	39, 51	eqtrd 2764	. 2 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → ((♯‘𝐹) · (♯‘(𝐺 NeighbVtx 𝑋))) = (𝐾 · (♯‘𝐹)))
53	11, 28, 52	3eqtrd 2768	1 ⊢ (((𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ (ℤ≥‘3))) → (♯‘(𝑋𝐶𝑁)) = (𝐾 · (♯‘𝐹)))

Syntax hints:   → wi 4   ∧ wa 395   ∧ w3a 1084   = wceq 1533   ∈ wcel 2098   ≠ wne 2932  ∀wral 3053  {crab 3424  ∅c0 4314   class class class wbr 5138   × cxp 5664  ‘cfv 6533  (class class class)co 7401   ∈ cmpo 7403   ≈ cen 8931  Fincfn 8934  ℂcc 11103   · cmul 11110   − cmin 11440  2c2 12263  3c3 12264  ℕ₀cn0 12468  ℕ₀^*cxnn0 12540  ℤ_≥cuz 12818  ♯chash 14286  Vtxcvtx 28691  Edgcedg 28742  USGraphcusgr 28844  FinUSGraphcfusgr 29008   NeighbVtx cnbgr 29024   RegUSGraph crusgr 29248  ClWWalksNOncclwwlknon 29775

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1789  ax-4 1803  ax-5 1905  ax-6 1963  ax-7 2003  ax-8 2100  ax-9 2108  ax-10 2129  ax-11 2146  ax-12 2163  ax-ext 2695  ax-rep 5275  ax-sep 5289  ax-nul 5296  ax-pow 5353  ax-pr 5417  ax-un 7718  ax-cnex 11161  ax-resscn 11162  ax-1cn 11163  ax-icn 11164  ax-addcl 11165  ax-addrcl 11166  ax-mulcl 11167  ax-mulrcl 11168  ax-mulcom 11169  ax-addass 11170  ax-mulass 11171  ax-distr 11172  ax-i2m1 11173  ax-1ne0 11174  ax-1rid 11175  ax-rnegex 11176  ax-rrecex 11177  ax-cnre 11178  ax-pre-lttri 11179  ax-pre-lttrn 11180  ax-pre-ltadd 11181  ax-pre-mulgt0 11182

This theorem depends on definitions:  df-bi 206  df-an 396  df-or 845  df-3or 1085  df-3an 1086  df-tru 1536  df-fal 1546  df-ex 1774  df-nf 1778  df-sb 2060  df-mo 2526  df-eu 2555  df-clab 2702  df-cleq 2716  df-clel 2802  df-nfc 2877  df-ne 2933  df-nel 3039  df-ral 3054  df-rex 3063  df-rmo 3368  df-reu 3369  df-rab 3425  df-v 3468  df-sbc 3770  df-csb 3886  df-dif 3943  df-un 3945  df-in 3947  df-ss 3957  df-pss 3959  df-nul 4315  df-if 4521  df-pw 4596  df-sn 4621  df-pr 4623  df-op 4627  df-uni 4900  df-int 4941  df-iun 4989  df-br 5139  df-opab 5201  df-mpt 5222  df-tr 5256  df-id 5564  df-eprel 5570  df-po 5578  df-so 5579  df-fr 5621  df-we 5623  df-xp 5672  df-rel 5673  df-cnv 5674  df-co 5675  df-dm 5676  df-rn 5677  df-res 5678  df-ima 5679  df-pred 6290  df-ord 6357  df-on 6358  df-lim 6359  df-suc 6360  df-iota 6485  df-fun 6535  df-fn 6536  df-f 6537  df-f1 6538  df-fo 6539  df-f1o 6540  df-fv 6541  df-riota 7357  df-ov 7404  df-oprab 7405  df-mpo 7406  df-om 7849  df-1st 7968  df-2nd 7969  df-frecs 8261  df-wrecs 8292  df-recs 8366  df-rdg 8405  df-1o 8461  df-2o 8462  df-oadd 8465  df-er 8698  df-map 8817  df-pm 8818  df-en 8935  df-dom 8936  df-sdom 8937  df-fin 8938  df-dju 9891  df-card 9929  df-pnf 11246  df-mnf 11247  df-xr 11248  df-ltxr 11249  df-le 11250  df-sub 11442  df-neg 11443  df-nn 12209  df-2 12271  df-3 12272  df-n0 12469  df-xnn0 12541  df-z 12555  df-uz 12819  df-rp 12971  df-xadd 13089  df-fz 13481  df-fzo 13624  df-seq 13963  df-exp 14024  df-hash 14287  df-word 14461  df-lsw 14509  df-concat 14517  df-s1 14542  df-substr 14587  df-pfx 14617  df-s2 14795  df-vtx 28693  df-iedg 28694  df-edg 28743  df-uhgr 28753  df-ushgr 28754  df-upgr 28777  df-umgr 28778  df-uspgr 28845  df-usgr 28846  df-fusgr 29009  df-nbgr 29025  df-vtxdg 29158  df-rgr 29249  df-rusgr 29250  df-wwlks 29519  df-wwlksn 29520  df-clwwlk 29670  df-clwwlkn 29713  df-clwwlknon 29776

This theorem is referenced by:  numclwlk1lem2  30058  numclwwlk3  30073