Metamath Proof Explorer

Theorem nbfusgrlevtxm2

Description: If there is a vertex which is not a neighbor of another vertex, the number of neighbors of the other vertex is at most the number of vertices of the graph minus 2 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 nbfusgrlevtxm2 
|- ( ( ( G e. FinUSGraph /\ U e. V ) /\ ( M e. V /\ M =/= U /\ M e/ ( G NeighbVtx U ) ) ) -> ( # ` ( G NeighbVtx U ) ) <_ ( ( # ` V ) - 2 ) )

Proof

Step Hyp Ref Expression
1 hashnbusgrnn0.v 
 |-  V = ( Vtx ` G )
2 1 fvexi 
 |-  V e. _V
3 difexg 
 |-  ( V e. _V -> ( V \ { M , U } ) e. _V )
4 2 3 mp1i 
 |-  ( ( ( G e. FinUSGraph /\ U e. V ) /\ ( M e. V /\ M =/= U /\ M e/ ( G NeighbVtx U ) ) ) -> ( V \ { M , U } ) e. _V )
5 simpr3 
 |-  ( ( ( G e. FinUSGraph /\ U e. V ) /\ ( M e. V /\ M =/= U /\ M e/ ( G NeighbVtx U ) ) ) -> M e/ ( G NeighbVtx U ) )
6 1 nbgrssvwo2 
 |-  ( M e/ ( G NeighbVtx U ) -> ( G NeighbVtx U ) C_ ( V \ { M , U } ) )
7 5 6 syl 
 |-  ( ( ( G e. FinUSGraph /\ U e. V ) /\ ( M e. V /\ M =/= U /\ M e/ ( G NeighbVtx U ) ) ) -> ( G NeighbVtx U ) C_ ( V \ { M , U } ) )
8 hashss 
 |-  ( ( ( V \ { M , U } ) e. _V /\ ( G NeighbVtx U ) C_ ( V \ { M , U } ) ) -> ( # ` ( G NeighbVtx U ) ) <_ ( # ` ( V \ { M , U } ) ) )
9 4 7 8 syl2anc 
 |-  ( ( ( G e. FinUSGraph /\ U e. V ) /\ ( M e. V /\ M =/= U /\ M e/ ( G NeighbVtx U ) ) ) -> ( # ` ( G NeighbVtx U ) ) <_ ( # ` ( V \ { M , U } ) ) )
10 1 fusgrvtxfi 
 |-  ( G e. FinUSGraph -> V e. Fin )
11 10 ad2antrr 
 |-  ( ( ( G e. FinUSGraph /\ U e. V ) /\ ( M e. V /\ M =/= U /\ M e/ ( G NeighbVtx U ) ) ) -> V e. Fin )
12 simpr1 
 |-  ( ( ( G e. FinUSGraph /\ U e. V ) /\ ( M e. V /\ M =/= U /\ M e/ ( G NeighbVtx U ) ) ) -> M e. V )
13 simplr 
 |-  ( ( ( G e. FinUSGraph /\ U e. V ) /\ ( M e. V /\ M =/= U /\ M e/ ( G NeighbVtx U ) ) ) -> U e. V )
14 simpr2 
 |-  ( ( ( G e. FinUSGraph /\ U e. V ) /\ ( M e. V /\ M =/= U /\ M e/ ( G NeighbVtx U ) ) ) -> M =/= U )
15 hashdifpr 
 |-  ( ( V e. Fin /\ ( M e. V /\ U e. V /\ M =/= U ) ) -> ( # ` ( V \ { M , U } ) ) = ( ( # ` V ) - 2 ) )
16 11 12 13 14 15 syl13anc 
 |-  ( ( ( G e. FinUSGraph /\ U e. V ) /\ ( M e. V /\ M =/= U /\ M e/ ( G NeighbVtx U ) ) ) -> ( # ` ( V \ { M , U } ) ) = ( ( # ` V ) - 2 ) )
17 9 16 breqtrd 
 |-  ( ( ( G e. FinUSGraph /\ U e. V ) /\ ( M e. V /\ M =/= U /\ M e/ ( G NeighbVtx U ) ) ) -> ( # ` ( G NeighbVtx U ) ) <_ ( ( # ` V ) - 2 ) )