Metamath Proof Explorer

Theorem nbfusgrlevtxm1

Description: The number of neighbors of a vertex is at most the number of vertices of the graph minus 1 in a finite simple graph. (Contributed by AV, 16-Dec-2020) (Proof shortened by AV, 13-Feb-2022)

Ref Expression
Hypothesis hashnbusgrnn0.v 
|- V = ( Vtx ` G )
Assertion nbfusgrlevtxm1 
|- ( ( G e. FinUSGraph /\ U e. V ) -> ( # ` ( G NeighbVtx U ) ) <_ ( ( # ` V ) - 1 ) )

Proof

Step Hyp Ref Expression
1 hashnbusgrnn0.v 
 |-  V = ( Vtx ` G )
2 1 fvexi 
 |-  V e. _V
3 2 difexi 
 |-  ( V \ { U } ) e. _V
4 1 nbgrssovtx 
 |-  ( G NeighbVtx U ) C_ ( V \ { U } )
5 4 a1i 
 |-  ( ( G e. FinUSGraph /\ U e. V ) -> ( G NeighbVtx U ) C_ ( V \ { U } ) )
6 hashss 
 |-  ( ( ( V \ { U } ) e. _V /\ ( G NeighbVtx U ) C_ ( V \ { U } ) ) -> ( # ` ( G NeighbVtx U ) ) <_ ( # ` ( V \ { U } ) ) )
7 3 5 6 sylancr 
 |-  ( ( G e. FinUSGraph /\ U e. V ) -> ( # ` ( G NeighbVtx U ) ) <_ ( # ` ( V \ { U } ) ) )
8 1 fusgrvtxfi 
 |-  ( G e. FinUSGraph -> V e. Fin )
9 hashdifsn 
 |-  ( ( V e. Fin /\ U e. V ) -> ( # ` ( V \ { U } ) ) = ( ( # ` V ) - 1 ) )
10 9 eqcomd 
 |-  ( ( V e. Fin /\ U e. V ) -> ( ( # ` V ) - 1 ) = ( # ` ( V \ { U } ) ) )
11 8 10 sylan 
 |-  ( ( G e. FinUSGraph /\ U e. V ) -> ( ( # ` V ) - 1 ) = ( # ` ( V \ { U } ) ) )
12 7 11 breqtrrd 
 |-  ( ( G e. FinUSGraph /\ U e. V ) -> ( # ` ( G NeighbVtx U ) ) <_ ( ( # ` V ) - 1 ) )