Description: The number of closed walks (defined as words) with a fixed length is the sum of the sizes of all equivalence classes according to .~ . (Contributed by Alexander van der Vekens, 10-Apr-2018) (Revised by AV, 30-Apr-2021)
Ref | Expression | ||
---|---|---|---|
Hypotheses | erclwwlkn.w | ⊢ 𝑊 = ( 𝑁 ClWWalksN 𝐺 ) | |
erclwwlkn.r | ⊢ ∼ = { 〈 𝑡 , 𝑢 〉 ∣ ( 𝑡 ∈ 𝑊 ∧ 𝑢 ∈ 𝑊 ∧ ∃ 𝑛 ∈ ( 0 ... 𝑁 ) 𝑡 = ( 𝑢 cyclShift 𝑛 ) ) } | ||
Assertion | hashclwwlkn0 | ⊢ ( ( Vtx ‘ 𝐺 ) ∈ Fin → ( ♯ ‘ 𝑊 ) = Σ 𝑥 ∈ ( 𝑊 / ∼ ) ( ♯ ‘ 𝑥 ) ) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | erclwwlkn.w | ⊢ 𝑊 = ( 𝑁 ClWWalksN 𝐺 ) | |
2 | erclwwlkn.r | ⊢ ∼ = { 〈 𝑡 , 𝑢 〉 ∣ ( 𝑡 ∈ 𝑊 ∧ 𝑢 ∈ 𝑊 ∧ ∃ 𝑛 ∈ ( 0 ... 𝑁 ) 𝑡 = ( 𝑢 cyclShift 𝑛 ) ) } | |
3 | 1 2 | erclwwlkn | ⊢ ∼ Er 𝑊 |
4 | 3 | a1i | ⊢ ( ( Vtx ‘ 𝐺 ) ∈ Fin → ∼ Er 𝑊 ) |
5 | clwwlknfi | ⊢ ( ( Vtx ‘ 𝐺 ) ∈ Fin → ( 𝑁 ClWWalksN 𝐺 ) ∈ Fin ) | |
6 | 1 5 | eqeltrid | ⊢ ( ( Vtx ‘ 𝐺 ) ∈ Fin → 𝑊 ∈ Fin ) |
7 | 4 6 | qshash | ⊢ ( ( Vtx ‘ 𝐺 ) ∈ Fin → ( ♯ ‘ 𝑊 ) = Σ 𝑥 ∈ ( 𝑊 / ∼ ) ( ♯ ‘ 𝑥 ) ) |