Metamath Proof Explorer

Theorem frgrregord13

Description: If a nonempty finite friendship graph is K-regular, then it must have order 1 or 3. Special case of frgrregord013 . (Contributed by Alexander van der Vekens, 9-Oct-2018) (Revised by AV, 4-Jun-2021)

Ref Expression
Hypothesis frgrreggt1.v ⊢ 𝑉 = ( Vtx ‘ 𝐺 )
Assertion frgrregord13 ( ( ( 𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅ ) ∧ 𝐺 RegUSGraph 𝐾 ) → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) )

Proof

Step Hyp Ref Expression
1 frgrreggt1.v ⊢ 𝑉 = ( Vtx ‘ 𝐺 )
2 simpl1 ⊢ ( ( ( 𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅ ) ∧ 𝐺 RegUSGraph 𝐾 ) → 𝐺 ∈ FriendGraph )
3 simpl2 ⊢ ( ( ( 𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅ ) ∧ 𝐺 RegUSGraph 𝐾 ) → 𝑉 ∈ Fin )
4 simpr ⊢ ( ( ( 𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅ ) ∧ 𝐺 RegUSGraph 𝐾 ) → 𝐺 RegUSGraph 𝐾 )
5 1 frgrregord013 ⊢ ( ( 𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾 ) → ( ( ♯ ‘ 𝑉 ) = 0 ∨ ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) )
6 2 3 4 5 syl3anc ⊢ ( ( ( 𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅ ) ∧ 𝐺 RegUSGraph 𝐾 ) → ( ( ♯ ‘ 𝑉 ) = 0 ∨ ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) )
7 hasheq0 ⊢ ( 𝑉 ∈ Fin → ( ( ♯ ‘ 𝑉 ) = 0 ↔ 𝑉 = ∅ ) )
8 eqneqall ⊢ ( 𝑉 = ∅ → ( 𝑉 ≠ ∅ → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) ) )
9 7 8 biimtrdi ⊢ ( 𝑉 ∈ Fin → ( ( ♯ ‘ 𝑉 ) = 0 → ( 𝑉 ≠ ∅ → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) ) ) )
10 9 com23 ⊢ ( 𝑉 ∈ Fin → ( 𝑉 ≠ ∅ → ( ( ♯ ‘ 𝑉 ) = 0 → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) ) ) )
11 10 a1i ⊢ ( 𝐺 ∈ FriendGraph → ( 𝑉 ∈ Fin → ( 𝑉 ≠ ∅ → ( ( ♯ ‘ 𝑉 ) = 0 → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) ) ) ) )
12 11 3imp ⊢ ( ( 𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅ ) → ( ( ♯ ‘ 𝑉 ) = 0 → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) ) )
13 12 adantr ⊢ ( ( ( 𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅ ) ∧ 𝐺 RegUSGraph 𝐾 ) → ( ( ♯ ‘ 𝑉 ) = 0 → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) ) )
14 13 com12 ⊢ ( ( ♯ ‘ 𝑉 ) = 0 → ( ( ( 𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅ ) ∧ 𝐺 RegUSGraph 𝐾 ) → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) ) )
15 orc ⊢ ( ( ♯ ‘ 𝑉 ) = 1 → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) )
16 15 a1d ⊢ ( ( ♯ ‘ 𝑉 ) = 1 → ( ( ( 𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅ ) ∧ 𝐺 RegUSGraph 𝐾 ) → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) ) )
17 olc ⊢ ( ( ♯ ‘ 𝑉 ) = 3 → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) )
18 17 a1d ⊢ ( ( ♯ ‘ 𝑉 ) = 3 → ( ( ( 𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅ ) ∧ 𝐺 RegUSGraph 𝐾 ) → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) ) )
19 14 16 18 3jaoi ⊢ ( ( ( ♯ ‘ 𝑉 ) = 0 ∨ ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) → ( ( ( 𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅ ) ∧ 𝐺 RegUSGraph 𝐾 ) → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) ) )
20 6 19 mpcom ⊢ ( ( ( 𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅ ) ∧ 𝐺 RegUSGraph 𝐾 ) → ( ( ♯ ‘ 𝑉 ) = 1 ∨ ( ♯ ‘ 𝑉 ) = 3 ) )