Metamath Proof Explorer

Theorem nbusgrvtxm1

Description: If the number of neighbors of a vertex in a finite simple graph is the number of vertices of the graph minus 1, each vertex except the first mentioned vertex is a neighbor of this vertex. (Contributed by Alexander van der Vekens, 14-Jul-2018) (Revised by AV, 16-Dec-2020)

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

Proof

Step Hyp Ref Expression
1 hashnbusgrnn0.v 
 |-  V = ( Vtx ` G )
2 ax-1 
 |-  ( M e. ( G NeighbVtx U ) -> ( ( M e. V /\ M =/= U ) -> M e. ( G NeighbVtx U ) ) )
3 2 2a1d 
 |-  ( M e. ( G NeighbVtx U ) -> ( ( G e. FinUSGraph /\ U e. V ) -> ( ( # ` ( G NeighbVtx U ) ) = ( ( # ` V ) - 1 ) -> ( ( M e. V /\ M =/= U ) -> M e. ( G NeighbVtx U ) ) ) ) )
4 simpr 
 |-  ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) -> ( G e. FinUSGraph /\ U e. V ) )
5 4 adantr 
 |-  ( ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) /\ ( M e. V /\ M =/= U ) ) -> ( G e. FinUSGraph /\ U e. V ) )
6 simprl 
 |-  ( ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) /\ ( M e. V /\ M =/= U ) ) -> M e. V )
7 simpr 
 |-  ( ( M e. V /\ M =/= U ) -> M =/= U )
8 7 adantl 
 |-  ( ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) /\ ( M e. V /\ M =/= U ) ) -> M =/= U )
9 df-nel 
 |-  ( M e/ ( G NeighbVtx U ) <-> -. M e. ( G NeighbVtx U ) )
10 9 biimpri 
 |-  ( -. M e. ( G NeighbVtx U ) -> M e/ ( G NeighbVtx U ) )
11 10 adantr 
 |-  ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) -> M e/ ( G NeighbVtx U ) )
12 11 adantr 
 |-  ( ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) /\ ( M e. V /\ M =/= U ) ) -> M e/ ( G NeighbVtx U ) )
13 1 nbfusgrlevtxm2 
 |-  ( ( ( G e. FinUSGraph /\ U e. V ) /\ ( M e. V /\ M =/= U /\ M e/ ( G NeighbVtx U ) ) ) -> ( # ` ( G NeighbVtx U ) ) <_ ( ( # ` V ) - 2 ) )
14 5 6 8 12 13 syl13anc 
 |-  ( ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) /\ ( M e. V /\ M =/= U ) ) -> ( # ` ( G NeighbVtx U ) ) <_ ( ( # ` V ) - 2 ) )
15 breq1 
 |-  ( ( # ` ( G NeighbVtx U ) ) = ( ( # ` V ) - 1 ) -> ( ( # ` ( G NeighbVtx U ) ) <_ ( ( # ` V ) - 2 ) <-> ( ( # ` V ) - 1 ) <_ ( ( # ` V ) - 2 ) ) )
16 15 adantl 
 |-  ( ( ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) /\ ( M e. V /\ M =/= U ) ) /\ ( # ` ( G NeighbVtx U ) ) = ( ( # ` V ) - 1 ) ) -> ( ( # ` ( G NeighbVtx U ) ) <_ ( ( # ` V ) - 2 ) <-> ( ( # ` V ) - 1 ) <_ ( ( # ` V ) - 2 ) ) )
17 1 fusgrvtxfi 
 |-  ( G e. FinUSGraph -> V e. Fin )
18 hashcl 
 |-  ( V e. Fin -> ( # ` V ) e. NN0 )
19 nn0re 
 |-  ( ( # ` V ) e. NN0 -> ( # ` V ) e. RR )
20 1red 
 |-  ( ( # ` V ) e. RR -> 1 e. RR )
21 2re 
 |-  2 e. RR
22 21 a1i 
 |-  ( ( # ` V ) e. RR -> 2 e. RR )
23 id 
 |-  ( ( # ` V ) e. RR -> ( # ` V ) e. RR )
24 1lt2 
 |-  1 < 2
25 24 a1i 
 |-  ( ( # ` V ) e. RR -> 1 < 2 )
26 20 22 23 25 ltsub2dd 
 |-  ( ( # ` V ) e. RR -> ( ( # ` V ) - 2 ) < ( ( # ` V ) - 1 ) )
27 23 22 resubcld 
 |-  ( ( # ` V ) e. RR -> ( ( # ` V ) - 2 ) e. RR )
28 peano2rem 
 |-  ( ( # ` V ) e. RR -> ( ( # ` V ) - 1 ) e. RR )
29 27 28 ltnled 
 |-  ( ( # ` V ) e. RR -> ( ( ( # ` V ) - 2 ) < ( ( # ` V ) - 1 ) <-> -. ( ( # ` V ) - 1 ) <_ ( ( # ` V ) - 2 ) ) )
30 26 29 mpbid 
 |-  ( ( # ` V ) e. RR -> -. ( ( # ` V ) - 1 ) <_ ( ( # ` V ) - 2 ) )
31 17 18 19 30 4syl 
 |-  ( G e. FinUSGraph -> -. ( ( # ` V ) - 1 ) <_ ( ( # ` V ) - 2 ) )
32 31 pm2.21d 
 |-  ( G e. FinUSGraph -> ( ( ( # ` V ) - 1 ) <_ ( ( # ` V ) - 2 ) -> M e. ( G NeighbVtx U ) ) )
33 32 adantr 
 |-  ( ( G e. FinUSGraph /\ U e. V ) -> ( ( ( # ` V ) - 1 ) <_ ( ( # ` V ) - 2 ) -> M e. ( G NeighbVtx U ) ) )
34 33 ad3antlr 
 |-  ( ( ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) /\ ( M e. V /\ M =/= U ) ) /\ ( # ` ( G NeighbVtx U ) ) = ( ( # ` V ) - 1 ) ) -> ( ( ( # ` V ) - 1 ) <_ ( ( # ` V ) - 2 ) -> M e. ( G NeighbVtx U ) ) )
35 16 34 sylbid 
 |-  ( ( ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) /\ ( M e. V /\ M =/= U ) ) /\ ( # ` ( G NeighbVtx U ) ) = ( ( # ` V ) - 1 ) ) -> ( ( # ` ( G NeighbVtx U ) ) <_ ( ( # ` V ) - 2 ) -> M e. ( G NeighbVtx U ) ) )
36 35 ex 
 |-  ( ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) /\ ( M e. V /\ M =/= U ) ) -> ( ( # ` ( G NeighbVtx U ) ) = ( ( # ` V ) - 1 ) -> ( ( # ` ( G NeighbVtx U ) ) <_ ( ( # ` V ) - 2 ) -> M e. ( G NeighbVtx U ) ) ) )
37 14 36 mpid 
 |-  ( ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) /\ ( M e. V /\ M =/= U ) ) -> ( ( # ` ( G NeighbVtx U ) ) = ( ( # ` V ) - 1 ) -> M e. ( G NeighbVtx U ) ) )
38 37 ex 
 |-  ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) -> ( ( M e. V /\ M =/= U ) -> ( ( # ` ( G NeighbVtx U ) ) = ( ( # ` V ) - 1 ) -> M e. ( G NeighbVtx U ) ) ) )
39 38 com23 
 |-  ( ( -. M e. ( G NeighbVtx U ) /\ ( G e. FinUSGraph /\ U e. V ) ) -> ( ( # ` ( G NeighbVtx U ) ) = ( ( # ` V ) - 1 ) -> ( ( M e. V /\ M =/= U ) -> M e. ( G NeighbVtx U ) ) ) )
40 39 ex 
 |-  ( -. M e. ( G NeighbVtx U ) -> ( ( G e. FinUSGraph /\ U e. V ) -> ( ( # ` ( G NeighbVtx U ) ) = ( ( # ` V ) - 1 ) -> ( ( M e. V /\ M =/= U ) -> M e. ( G NeighbVtx U ) ) ) ) )
41 3 40 pm2.61i 
 |-  ( ( G e. FinUSGraph /\ U e. V ) -> ( ( # ` ( G NeighbVtx U ) ) = ( ( # ` V ) - 1 ) -> ( ( M e. V /\ M =/= U ) -> M e. ( G NeighbVtx U ) ) ) )