Metamath Proof Explorer

Theorem clwlkssizeeq

Description: The size of the set of closed walks as words of length N corresponds to the size of the set of closed walks of length N in a simple pseudograph. (Contributed by Alexander van der Vekens, 6-Jul-2018) (Revised by AV, 4-May-2021) (Revised by AV, 26-May-2022) (Proof shortened by AV, 3-Nov-2022)

Ref Expression
Assertion clwlkssizeeq 
|- ( ( G e. USPGraph /\ N e. NN ) -> ( # ` ( N ClWWalksN G ) ) = ( # ` { w e. ( ClWalks ` G ) | ( # ` ( 1st ` w ) ) = N } ) )

Proof

Step Hyp Ref Expression
1 fvex 
 |-  ( ClWalks ` G ) e. _V
2 1 rabex 
 |-  { w e. ( ClWalks ` G ) | ( # ` ( 1st ` w ) ) = N } e. _V
3 2 a1i 
 |-  ( ( G e. USPGraph /\ N e. NN ) -> { w e. ( ClWalks ` G ) | ( # ` ( 1st ` w ) ) = N } e. _V )
4 eqid 
 |-  ( 1st ` c ) = ( 1st ` c )
5 eqid 
 |-  ( 2nd ` c ) = ( 2nd ` c )
6 eqid 
 |-  { w e. ( ClWalks ` G ) | ( # ` ( 1st ` w ) ) = N } = { w e. ( ClWalks ` G ) | ( # ` ( 1st ` w ) ) = N }
7 eqid 
 |-  ( c e. { w e. ( ClWalks ` G ) | ( # ` ( 1st ` w ) ) = N } |-> ( ( 2nd ` c ) prefix ( # ` ( 1st ` c ) ) ) ) = ( c e. { w e. ( ClWalks ` G ) | ( # ` ( 1st ` w ) ) = N } |-> ( ( 2nd ` c ) prefix ( # ` ( 1st ` c ) ) ) )
8 4 5 6 7 clwlknf1oclwwlkn 
 |-  ( ( G e. USPGraph /\ N e. NN ) -> ( c e. { w e. ( ClWalks ` G ) | ( # ` ( 1st ` w ) ) = N } |-> ( ( 2nd ` c ) prefix ( # ` ( 1st ` c ) ) ) ) : { w e. ( ClWalks ` G ) | ( # ` ( 1st ` w ) ) = N } -1-1-onto-> ( N ClWWalksN G ) )
9 3 8 hasheqf1od 
 |-  ( ( G e. USPGraph /\ N e. NN ) -> ( # ` { w e. ( ClWalks ` G ) | ( # ` ( 1st ` w ) ) = N } ) = ( # ` ( N ClWWalksN G ) ) )
10 9 eqcomd 
 |-  ( ( G e. USPGraph /\ N e. NN ) -> ( # ` ( N ClWWalksN G ) ) = ( # ` { w e. ( ClWalks ` G ) | ( # ` ( 1st ` w ) ) = N } ) )