Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
||
Mirrors > Home > MPE Home > Th. List > clwwlknclwwlkdifnum | Structured version Visualization version GIF version |
Description: In a 𝐾-regular graph, the size of the set 𝐴 of walks of length 𝑁 starting with a fixed vertex 𝑋 and ending not at this vertex is the difference between 𝐾 to the power of 𝑁 and the size of the set 𝐵 of closed walks of length 𝑁 anchored at this vertex 𝑋. (Contributed by Alexander van der Vekens, 30-Sep-2018.) (Revised by AV, 7-May-2021.) (Revised by AV, 8-Mar-2022.) (Proof shortened by AV, 16-Mar-2022.) |
Ref | Expression |
---|---|
clwwlknclwwlkdif.a | ⊢ 𝐴 = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ((𝑤‘0) = 𝑋 ∧ (lastS‘𝑤) ≠ 𝑋)} |
clwwlknclwwlkdif.b | ⊢ 𝐵 = (𝑋(𝑁 WWalksNOn 𝐺)𝑋) |
clwwlknclwwlkdifnum.v | ⊢ 𝑉 = (Vtx‘𝐺) |
Ref | Expression |
---|---|
clwwlknclwwlkdifnum | ⊢ (((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → (♯‘𝐴) = ((𝐾↑𝑁) − (♯‘𝐵))) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | clwwlknclwwlkdif.a | . . . . 5 ⊢ 𝐴 = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ((𝑤‘0) = 𝑋 ∧ (lastS‘𝑤) ≠ 𝑋)} | |
2 | clwwlknclwwlkdif.b | . . . . 5 ⊢ 𝐵 = (𝑋(𝑁 WWalksNOn 𝐺)𝑋) | |
3 | eqid 2738 | . . . . 5 ⊢ {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} | |
4 | 1, 2, 3 | clwwlknclwwlkdif 27916 | . . . 4 ⊢ 𝐴 = ({𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} ∖ 𝐵) |
5 | 4 | fveq2i 6677 | . . 3 ⊢ (♯‘𝐴) = (♯‘({𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} ∖ 𝐵)) |
6 | 5 | a1i 11 | . 2 ⊢ (((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → (♯‘𝐴) = (♯‘({𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} ∖ 𝐵))) |
7 | clwwlknclwwlkdifnum.v | . . . . . . . 8 ⊢ 𝑉 = (Vtx‘𝐺) | |
8 | 7 | eleq1i 2823 | . . . . . . 7 ⊢ (𝑉 ∈ Fin ↔ (Vtx‘𝐺) ∈ Fin) |
9 | 8 | biimpi 219 | . . . . . 6 ⊢ (𝑉 ∈ Fin → (Vtx‘𝐺) ∈ Fin) |
10 | 9 | adantl 485 | . . . . 5 ⊢ ((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) → (Vtx‘𝐺) ∈ Fin) |
11 | 10 | adantr 484 | . . . 4 ⊢ (((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → (Vtx‘𝐺) ∈ Fin) |
12 | wwlksnfi 27844 | . . . 4 ⊢ ((Vtx‘𝐺) ∈ Fin → (𝑁 WWalksN 𝐺) ∈ Fin) | |
13 | rabfi 8821 | . . . 4 ⊢ ((𝑁 WWalksN 𝐺) ∈ Fin → {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} ∈ Fin) | |
14 | 11, 12, 13 | 3syl 18 | . . 3 ⊢ (((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} ∈ Fin) |
15 | 7 | iswwlksnon 27791 | . . . . . . . 8 ⊢ (𝑋(𝑁 WWalksNOn 𝐺)𝑋) = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ((𝑤‘0) = 𝑋 ∧ (𝑤‘𝑁) = 𝑋)} |
16 | ancom 464 | . . . . . . . . 9 ⊢ (((𝑤‘0) = 𝑋 ∧ (𝑤‘𝑁) = 𝑋) ↔ ((𝑤‘𝑁) = 𝑋 ∧ (𝑤‘0) = 𝑋)) | |
17 | 16 | rabbii 3374 | . . . . . . . 8 ⊢ {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ((𝑤‘0) = 𝑋 ∧ (𝑤‘𝑁) = 𝑋)} = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ((𝑤‘𝑁) = 𝑋 ∧ (𝑤‘0) = 𝑋)} |
18 | 15, 17 | eqtri 2761 | . . . . . . 7 ⊢ (𝑋(𝑁 WWalksNOn 𝐺)𝑋) = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ((𝑤‘𝑁) = 𝑋 ∧ (𝑤‘0) = 𝑋)} |
19 | 18 | a1i 11 | . . . . . 6 ⊢ ((𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0) → (𝑋(𝑁 WWalksNOn 𝐺)𝑋) = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ((𝑤‘𝑁) = 𝑋 ∧ (𝑤‘0) = 𝑋)}) |
20 | 2, 19 | syl5eq 2785 | . . . . 5 ⊢ ((𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0) → 𝐵 = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ((𝑤‘𝑁) = 𝑋 ∧ (𝑤‘0) = 𝑋)}) |
21 | simpr 488 | . . . . . . 7 ⊢ (((𝑤‘𝑁) = 𝑋 ∧ (𝑤‘0) = 𝑋) → (𝑤‘0) = 𝑋) | |
22 | 21 | a1i 11 | . . . . . 6 ⊢ (𝑤 ∈ (𝑁 WWalksN 𝐺) → (((𝑤‘𝑁) = 𝑋 ∧ (𝑤‘0) = 𝑋) → (𝑤‘0) = 𝑋)) |
23 | 22 | ss2rabi 3966 | . . . . 5 ⊢ {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ((𝑤‘𝑁) = 𝑋 ∧ (𝑤‘0) = 𝑋)} ⊆ {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} |
24 | 20, 23 | eqsstrdi 3931 | . . . 4 ⊢ ((𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0) → 𝐵 ⊆ {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋}) |
25 | 24 | adantl 485 | . . 3 ⊢ (((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → 𝐵 ⊆ {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋}) |
26 | hashssdif 13865 | . . 3 ⊢ (({𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} ∈ Fin ∧ 𝐵 ⊆ {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋}) → (♯‘({𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} ∖ 𝐵)) = ((♯‘{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋}) − (♯‘𝐵))) | |
27 | 14, 25, 26 | syl2anc 587 | . 2 ⊢ (((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → (♯‘({𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} ∖ 𝐵)) = ((♯‘{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋}) − (♯‘𝐵))) |
28 | simpl 486 | . . . . 5 ⊢ ((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) → 𝐺 RegUSGraph 𝐾) | |
29 | 28 | adantr 484 | . . . 4 ⊢ (((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → 𝐺 RegUSGraph 𝐾) |
30 | simpr 488 | . . . . 5 ⊢ ((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) → 𝑉 ∈ Fin) | |
31 | 30 | adantr 484 | . . . 4 ⊢ (((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → 𝑉 ∈ Fin) |
32 | simpl 486 | . . . . 5 ⊢ ((𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0) → 𝑋 ∈ 𝑉) | |
33 | 32 | adantl 485 | . . . 4 ⊢ (((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → 𝑋 ∈ 𝑉) |
34 | simpr 488 | . . . . 5 ⊢ ((𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0) → 𝑁 ∈ ℕ0) | |
35 | 34 | adantl 485 | . . . 4 ⊢ (((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → 𝑁 ∈ ℕ0) |
36 | 7 | rusgrnumwwlkg 27914 | . . . 4 ⊢ ((𝐺 RegUSGraph 𝐾 ∧ (𝑉 ∈ Fin ∧ 𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → (♯‘{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋}) = (𝐾↑𝑁)) |
37 | 29, 31, 33, 35, 36 | syl13anc 1373 | . . 3 ⊢ (((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → (♯‘{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋}) = (𝐾↑𝑁)) |
38 | 37 | oveq1d 7185 | . 2 ⊢ (((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → ((♯‘{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋}) − (♯‘𝐵)) = ((𝐾↑𝑁) − (♯‘𝐵))) |
39 | 6, 27, 38 | 3eqtrd 2777 | 1 ⊢ (((𝐺 RegUSGraph 𝐾 ∧ 𝑉 ∈ Fin) ∧ (𝑋 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0)) → (♯‘𝐴) = ((𝐾↑𝑁) − (♯‘𝐵))) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ∧ wa 399 = wceq 1542 ∈ wcel 2114 ≠ wne 2934 {crab 3057 ∖ cdif 3840 ⊆ wss 3843 class class class wbr 5030 ‘cfv 6339 (class class class)co 7170 Fincfn 8555 0cc0 10615 − cmin 10948 ℕ0cn0 11976 ↑cexp 13521 ♯chash 13782 lastSclsw 14003 Vtxcvtx 26941 RegUSGraph crusgr 27498 WWalksN cwwlksn 27764 WWalksNOn cwwlksnon 27765 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1802 ax-4 1816 ax-5 1917 ax-6 1975 ax-7 2020 ax-8 2116 ax-9 2124 ax-10 2145 ax-11 2162 ax-12 2179 ax-ext 2710 ax-rep 5154 ax-sep 5167 ax-nul 5174 ax-pow 5232 ax-pr 5296 ax-un 7479 ax-inf2 9177 ax-cnex 10671 ax-resscn 10672 ax-1cn 10673 ax-icn 10674 ax-addcl 10675 ax-addrcl 10676 ax-mulcl 10677 ax-mulrcl 10678 ax-mulcom 10679 ax-addass 10680 ax-mulass 10681 ax-distr 10682 ax-i2m1 10683 ax-1ne0 10684 ax-1rid 10685 ax-rnegex 10686 ax-rrecex 10687 ax-cnre 10688 ax-pre-lttri 10689 ax-pre-lttrn 10690 ax-pre-ltadd 10691 ax-pre-mulgt0 10692 ax-pre-sup 10693 |
This theorem depends on definitions: df-bi 210 df-an 400 df-or 847 df-3or 1089 df-3an 1090 df-tru 1545 df-fal 1555 df-ex 1787 df-nf 1791 df-sb 2075 df-mo 2540 df-eu 2570 df-clab 2717 df-cleq 2730 df-clel 2811 df-nfc 2881 df-ne 2935 df-nel 3039 df-ral 3058 df-rex 3059 df-reu 3060 df-rmo 3061 df-rab 3062 df-v 3400 df-sbc 3681 df-csb 3791 df-dif 3846 df-un 3848 df-in 3850 df-ss 3860 df-pss 3862 df-nul 4212 df-if 4415 df-pw 4490 df-sn 4517 df-pr 4519 df-tp 4521 df-op 4523 df-uni 4797 df-int 4837 df-iun 4883 df-disj 4996 df-br 5031 df-opab 5093 df-mpt 5111 df-tr 5137 df-id 5429 df-eprel 5434 df-po 5442 df-so 5443 df-fr 5483 df-se 5484 df-we 5485 df-xp 5531 df-rel 5532 df-cnv 5533 df-co 5534 df-dm 5535 df-rn 5536 df-res 5537 df-ima 5538 df-pred 6129 df-ord 6175 df-on 6176 df-lim 6177 df-suc 6178 df-iota 6297 df-fun 6341 df-fn 6342 df-f 6343 df-f1 6344 df-fo 6345 df-f1o 6346 df-fv 6347 df-isom 6348 df-riota 7127 df-ov 7173 df-oprab 7174 df-mpo 7175 df-om 7600 df-1st 7714 df-2nd 7715 df-wrecs 7976 df-recs 8037 df-rdg 8075 df-1o 8131 df-2o 8132 df-oadd 8135 df-er 8320 df-map 8439 df-pm 8440 df-en 8556 df-dom 8557 df-sdom 8558 df-fin 8559 df-sup 8979 df-oi 9047 df-dju 9403 df-card 9441 df-pnf 10755 df-mnf 10756 df-xr 10757 df-ltxr 10758 df-le 10759 df-sub 10950 df-neg 10951 df-div 11376 df-nn 11717 df-2 11779 df-3 11780 df-n0 11977 df-xnn0 12049 df-z 12063 df-uz 12325 df-rp 12473 df-xadd 12591 df-fz 12982 df-fzo 13125 df-seq 13461 df-exp 13522 df-hash 13783 df-word 13956 df-lsw 14004 df-concat 14012 df-s1 14039 df-substr 14092 df-pfx 14122 df-cj 14548 df-re 14549 df-im 14550 df-sqrt 14684 df-abs 14685 df-clim 14935 df-sum 15136 df-vtx 26943 df-iedg 26944 df-edg 26993 df-uhgr 27003 df-ushgr 27004 df-upgr 27027 df-umgr 27028 df-uspgr 27095 df-usgr 27096 df-fusgr 27259 df-nbgr 27275 df-vtxdg 27408 df-rgr 27499 df-rusgr 27500 df-wwlks 27768 df-wwlksn 27769 df-wwlksnon 27770 |
This theorem is referenced by: numclwwlkqhash 28312 |
Copyright terms: Public domain | W3C validator |