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 ⊢ 𝑉 = ( Vtx ‘ 𝐺 )
Assertion nbfusgrlevtxm2 ( ( ( 𝐺 ∈ FinUSGraph ∧ 𝑈 ∈ 𝑉 ) ∧ ( 𝑀 ∈ 𝑉 ∧ 𝑀 ≠ 𝑈 ∧ 𝑀 ∉ ( 𝐺 NeighbVtx 𝑈 ) ) ) → ( ♯ ‘ ( 𝐺 NeighbVtx 𝑈 ) ) ≤ ( ( ♯ ‘ 𝑉 ) − 2 ) )

Proof

Step Hyp Ref Expression
1 hashnbusgrnn0.v ⊢ 𝑉 = ( Vtx ‘ 𝐺 )
2 1 fvexi ⊢ 𝑉 ∈ V
3 difexg ⊢ ( 𝑉 ∈ V → ( 𝑉 ∖ { 𝑀 , 𝑈 } ) ∈ V )
4 2 3 mp1i ⊢ ( ( ( 𝐺 ∈ FinUSGraph ∧ 𝑈 ∈ 𝑉 ) ∧ ( 𝑀 ∈ 𝑉 ∧ 𝑀 ≠ 𝑈 ∧ 𝑀 ∉ ( 𝐺 NeighbVtx 𝑈 ) ) ) → ( 𝑉 ∖ { 𝑀 , 𝑈 } ) ∈ V )
5 simpr3 ⊢ ( ( ( 𝐺 ∈ FinUSGraph ∧ 𝑈 ∈ 𝑉 ) ∧ ( 𝑀 ∈ 𝑉 ∧ 𝑀 ≠ 𝑈 ∧ 𝑀 ∉ ( 𝐺 NeighbVtx 𝑈 ) ) ) → 𝑀 ∉ ( 𝐺 NeighbVtx 𝑈 ) )
6 1 nbgrssvwo2 ⊢ ( 𝑀 ∉ ( 𝐺 NeighbVtx 𝑈 ) → ( 𝐺 NeighbVtx 𝑈 ) ⊆ ( 𝑉 ∖ { 𝑀 , 𝑈 } ) )
7 5 6 syl ⊢ ( ( ( 𝐺 ∈ FinUSGraph ∧ 𝑈 ∈ 𝑉 ) ∧ ( 𝑀 ∈ 𝑉 ∧ 𝑀 ≠ 𝑈 ∧ 𝑀 ∉ ( 𝐺 NeighbVtx 𝑈 ) ) ) → ( 𝐺 NeighbVtx 𝑈 ) ⊆ ( 𝑉 ∖ { 𝑀 , 𝑈 } ) )
8 hashss ⊢ ( ( ( 𝑉 ∖ { 𝑀 , 𝑈 } ) ∈ V ∧ ( 𝐺 NeighbVtx 𝑈 ) ⊆ ( 𝑉 ∖ { 𝑀 , 𝑈 } ) ) → ( ♯ ‘ ( 𝐺 NeighbVtx 𝑈 ) ) ≤ ( ♯ ‘ ( 𝑉 ∖ { 𝑀 , 𝑈 } ) ) )
9 4 7 8 syl2anc ⊢ ( ( ( 𝐺 ∈ FinUSGraph ∧ 𝑈 ∈ 𝑉 ) ∧ ( 𝑀 ∈ 𝑉 ∧ 𝑀 ≠ 𝑈 ∧ 𝑀 ∉ ( 𝐺 NeighbVtx 𝑈 ) ) ) → ( ♯ ‘ ( 𝐺 NeighbVtx 𝑈 ) ) ≤ ( ♯ ‘ ( 𝑉 ∖ { 𝑀 , 𝑈 } ) ) )
10 1 fusgrvtxfi ⊢ ( 𝐺 ∈ FinUSGraph → 𝑉 ∈ Fin )
11 10 ad2antrr ⊢ ( ( ( 𝐺 ∈ FinUSGraph ∧ 𝑈 ∈ 𝑉 ) ∧ ( 𝑀 ∈ 𝑉 ∧ 𝑀 ≠ 𝑈 ∧ 𝑀 ∉ ( 𝐺 NeighbVtx 𝑈 ) ) ) → 𝑉 ∈ Fin )
12 simpr1 ⊢ ( ( ( 𝐺 ∈ FinUSGraph ∧ 𝑈 ∈ 𝑉 ) ∧ ( 𝑀 ∈ 𝑉 ∧ 𝑀 ≠ 𝑈 ∧ 𝑀 ∉ ( 𝐺 NeighbVtx 𝑈 ) ) ) → 𝑀 ∈ 𝑉 )
13 simplr ⊢ ( ( ( 𝐺 ∈ FinUSGraph ∧ 𝑈 ∈ 𝑉 ) ∧ ( 𝑀 ∈ 𝑉 ∧ 𝑀 ≠ 𝑈 ∧ 𝑀 ∉ ( 𝐺 NeighbVtx 𝑈 ) ) ) → 𝑈 ∈ 𝑉 )
14 simpr2 ⊢ ( ( ( 𝐺 ∈ FinUSGraph ∧ 𝑈 ∈ 𝑉 ) ∧ ( 𝑀 ∈ 𝑉 ∧ 𝑀 ≠ 𝑈 ∧ 𝑀 ∉ ( 𝐺 NeighbVtx 𝑈 ) ) ) → 𝑀 ≠ 𝑈 )
15 hashdifpr ⊢ ( ( 𝑉 ∈ Fin ∧ ( 𝑀 ∈ 𝑉 ∧ 𝑈 ∈ 𝑉 ∧ 𝑀 ≠ 𝑈 ) ) → ( ♯ ‘ ( 𝑉 ∖ { 𝑀 , 𝑈 } ) ) = ( ( ♯ ‘ 𝑉 ) − 2 ) )
16 11 12 13 14 15 syl13anc ⊢ ( ( ( 𝐺 ∈ FinUSGraph ∧ 𝑈 ∈ 𝑉 ) ∧ ( 𝑀 ∈ 𝑉 ∧ 𝑀 ≠ 𝑈 ∧ 𝑀 ∉ ( 𝐺 NeighbVtx 𝑈 ) ) ) → ( ♯ ‘ ( 𝑉 ∖ { 𝑀 , 𝑈 } ) ) = ( ( ♯ ‘ 𝑉 ) − 2 ) )
17 9 16 breqtrd ⊢ ( ( ( 𝐺 ∈ FinUSGraph ∧ 𝑈 ∈ 𝑉 ) ∧ ( 𝑀 ∈ 𝑉 ∧ 𝑀 ≠ 𝑈 ∧ 𝑀 ∉ ( 𝐺 NeighbVtx 𝑈 ) ) ) → ( ♯ ‘ ( 𝐺 NeighbVtx 𝑈 ) ) ≤ ( ( ♯ ‘ 𝑉 ) − 2 ) )