Metamath Proof Explorer


Theorem umgrhashecclwwlk

Description: The size of every equivalence class of the equivalence relation over the set of closed walks (defined as words) with a fixed length which is a prime number equals this length (in an undirected simple graph). (Contributed by Alexander van der Vekens, 17-Jun-2018) (Revised by AV, 1-May-2021)

Ref Expression
Hypotheses erclwwlkn.w W = N ClWWalksN G
erclwwlkn.r ˙ = t u | t W u W n 0 N t = u cyclShift n
Assertion umgrhashecclwwlk G UMGraph N U W / ˙ U = N

Proof

Step Hyp Ref Expression
1 erclwwlkn.w W = N ClWWalksN G
2 erclwwlkn.r ˙ = t u | t W u W n 0 N t = u cyclShift n
3 1 2 eclclwwlkn1 U W / ˙ U W / ˙ x W U = y W | n 0 N y = x cyclShift n
4 rabeq W = N ClWWalksN G y W | n 0 N y = x cyclShift n = y N ClWWalksN G | n 0 N y = x cyclShift n
5 1 4 mp1i G UMGraph N x W y W | n 0 N y = x cyclShift n = y N ClWWalksN G | n 0 N y = x cyclShift n
6 prmnn N N
7 6 nnnn0d N N 0
8 7 adantl G UMGraph N N 0
9 1 eleq2i x W x N ClWWalksN G
10 9 biimpi x W x N ClWWalksN G
11 clwwlknscsh N 0 x N ClWWalksN G y N ClWWalksN G | n 0 N y = x cyclShift n = y Word Vtx G | n 0 N y = x cyclShift n
12 8 10 11 syl2an G UMGraph N x W y N ClWWalksN G | n 0 N y = x cyclShift n = y Word Vtx G | n 0 N y = x cyclShift n
13 5 12 eqtrd G UMGraph N x W y W | n 0 N y = x cyclShift n = y Word Vtx G | n 0 N y = x cyclShift n
14 13 eqeq2d G UMGraph N x W U = y W | n 0 N y = x cyclShift n U = y Word Vtx G | n 0 N y = x cyclShift n
15 6 adantl G UMGraph N N
16 simpll x Word Vtx G x = N N x Word Vtx G
17 elnnne0 N N 0 N 0
18 eqeq1 N = x N = 0 x = 0
19 18 eqcoms x = N N = 0 x = 0
20 hasheq0 x Word Vtx G x = 0 x =
21 19 20 sylan9bbr x Word Vtx G x = N N = 0 x =
22 21 necon3bid x Word Vtx G x = N N 0 x
23 22 biimpcd N 0 x Word Vtx G x = N x
24 17 23 simplbiim N x Word Vtx G x = N x
25 24 impcom x Word Vtx G x = N N x
26 simplr x Word Vtx G x = N N x = N
27 26 eqcomd x Word Vtx G x = N N N = x
28 16 25 27 3jca x Word Vtx G x = N N x Word Vtx G x N = x
29 28 ex x Word Vtx G x = N N x Word Vtx G x N = x
30 eqid Vtx G = Vtx G
31 30 clwwlknbp x N ClWWalksN G x Word Vtx G x = N
32 29 31 syl11 N x N ClWWalksN G x Word Vtx G x N = x
33 9 32 syl5bi N x W x Word Vtx G x N = x
34 15 33 syl G UMGraph N x W x Word Vtx G x N = x
35 34 imp G UMGraph N x W x Word Vtx G x N = x
36 scshwfzeqfzo x Word Vtx G x N = x y Word Vtx G | n 0 N y = x cyclShift n = y Word Vtx G | n 0 ..^ N y = x cyclShift n
37 35 36 syl G UMGraph N x W y Word Vtx G | n 0 N y = x cyclShift n = y Word Vtx G | n 0 ..^ N y = x cyclShift n
38 37 eqeq2d G UMGraph N x W U = y Word Vtx G | n 0 N y = x cyclShift n U = y Word Vtx G | n 0 ..^ N y = x cyclShift n
39 fveq2 U = y Word Vtx G | n 0 ..^ x y = x cyclShift n U = y Word Vtx G | n 0 ..^ x y = x cyclShift n
40 simprl x Word Vtx G x x ClWWalksN G G UMGraph x G UMGraph
41 prmuz2 x x 2
42 41 adantl G UMGraph x x 2
43 42 adantl x Word Vtx G x x ClWWalksN G G UMGraph x x 2
44 simplr x Word Vtx G x x ClWWalksN G G UMGraph x x x ClWWalksN G
45 umgr2cwwkdifex G UMGraph x 2 x x ClWWalksN G i 0 ..^ x x i x 0
46 40 43 44 45 syl3anc x Word Vtx G x x ClWWalksN G G UMGraph x i 0 ..^ x x i x 0
47 oveq2 n = m x cyclShift n = x cyclShift m
48 47 eqeq2d n = m y = x cyclShift n y = x cyclShift m
49 48 cbvrexvw n 0 ..^ x y = x cyclShift n m 0 ..^ x y = x cyclShift m
50 eqeq1 y = u y = x cyclShift m u = x cyclShift m
51 eqcom u = x cyclShift m x cyclShift m = u
52 50 51 bitrdi y = u y = x cyclShift m x cyclShift m = u
53 52 rexbidv y = u m 0 ..^ x y = x cyclShift m m 0 ..^ x x cyclShift m = u
54 49 53 syl5bb y = u n 0 ..^ x y = x cyclShift n m 0 ..^ x x cyclShift m = u
55 54 cbvrabv y Word Vtx G | n 0 ..^ x y = x cyclShift n = u Word Vtx G | m 0 ..^ x x cyclShift m = u
56 55 cshwshashnsame x Word Vtx G x i 0 ..^ x x i x 0 y Word Vtx G | n 0 ..^ x y = x cyclShift n = x
57 56 ad2ant2rl x Word Vtx G x x ClWWalksN G G UMGraph x i 0 ..^ x x i x 0 y Word Vtx G | n 0 ..^ x y = x cyclShift n = x
58 46 57 mpd x Word Vtx G x x ClWWalksN G G UMGraph x y Word Vtx G | n 0 ..^ x y = x cyclShift n = x
59 39 58 sylan9eqr x Word Vtx G x x ClWWalksN G G UMGraph x U = y Word Vtx G | n 0 ..^ x y = x cyclShift n U = x
60 59 exp41 x Word Vtx G x x ClWWalksN G G UMGraph x U = y Word Vtx G | n 0 ..^ x y = x cyclShift n U = x
61 60 adantr x Word Vtx G x = N x x ClWWalksN G G UMGraph x U = y Word Vtx G | n 0 ..^ x y = x cyclShift n U = x
62 oveq1 N = x N ClWWalksN G = x ClWWalksN G
63 62 eleq2d N = x x N ClWWalksN G x x ClWWalksN G
64 eleq1 N = x N x
65 64 anbi2d N = x G UMGraph N G UMGraph x
66 oveq2 N = x 0 ..^ N = 0 ..^ x
67 66 rexeqdv N = x n 0 ..^ N y = x cyclShift n n 0 ..^ x y = x cyclShift n
68 67 rabbidv N = x y Word Vtx G | n 0 ..^ N y = x cyclShift n = y Word Vtx G | n 0 ..^ x y = x cyclShift n
69 68 eqeq2d N = x U = y Word Vtx G | n 0 ..^ N y = x cyclShift n U = y Word Vtx G | n 0 ..^ x y = x cyclShift n
70 eqeq2 N = x U = N U = x
71 69 70 imbi12d N = x U = y Word Vtx G | n 0 ..^ N y = x cyclShift n U = N U = y Word Vtx G | n 0 ..^ x y = x cyclShift n U = x
72 65 71 imbi12d N = x G UMGraph N U = y Word Vtx G | n 0 ..^ N y = x cyclShift n U = N G UMGraph x U = y Word Vtx G | n 0 ..^ x y = x cyclShift n U = x
73 63 72 imbi12d N = x x N ClWWalksN G G UMGraph N U = y Word Vtx G | n 0 ..^ N y = x cyclShift n U = N x x ClWWalksN G G UMGraph x U = y Word Vtx G | n 0 ..^ x y = x cyclShift n U = x
74 73 eqcoms x = N x N ClWWalksN G G UMGraph N U = y Word Vtx G | n 0 ..^ N y = x cyclShift n U = N x x ClWWalksN G G UMGraph x U = y Word Vtx G | n 0 ..^ x y = x cyclShift n U = x
75 74 adantl x Word Vtx G x = N x N ClWWalksN G G UMGraph N U = y Word Vtx G | n 0 ..^ N y = x cyclShift n U = N x x ClWWalksN G G UMGraph x U = y Word Vtx G | n 0 ..^ x y = x cyclShift n U = x
76 61 75 mpbird x Word Vtx G x = N x N ClWWalksN G G UMGraph N U = y Word Vtx G | n 0 ..^ N y = x cyclShift n U = N
77 31 76 mpcom x N ClWWalksN G G UMGraph N U = y Word Vtx G | n 0 ..^ N y = x cyclShift n U = N
78 77 1 eleq2s x W G UMGraph N U = y Word Vtx G | n 0 ..^ N y = x cyclShift n U = N
79 78 impcom G UMGraph N x W U = y Word Vtx G | n 0 ..^ N y = x cyclShift n U = N
80 38 79 sylbid G UMGraph N x W U = y Word Vtx G | n 0 N y = x cyclShift n U = N
81 14 80 sylbid G UMGraph N x W U = y W | n 0 N y = x cyclShift n U = N
82 81 rexlimdva G UMGraph N x W U = y W | n 0 N y = x cyclShift n U = N
83 82 com12 x W U = y W | n 0 N y = x cyclShift n G UMGraph N U = N
84 3 83 syl6bi U W / ˙ U W / ˙ G UMGraph N U = N
85 84 pm2.43i U W / ˙ G UMGraph N U = N
86 85 com12 G UMGraph N U W / ˙ U = N