MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  friendshipgt3 Structured version   Visualization version   GIF version

Theorem friendshipgt3 27834
Description: The friendship theorem for big graphs: In every finite friendship graph with order greater than 3 there is a vertex which is adjacent to all other vertices. (Contributed by Alexander van der Vekens, 9-Oct-2018.) (Revised by AV, 4-Jun-2021.)
Hypothesis
Ref Expression
frgrreggt1.v 𝑉 = (Vtx‘𝐺)
Assertion
Ref Expression
friendshipgt3 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))
Distinct variable groups:   𝑣,𝐺   𝑣,𝑉   𝑤,𝐺,𝑣   𝑤,𝑉

Proof of Theorem friendshipgt3
Dummy variables 𝑘 𝑚 𝑡 𝑢 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 frgrreggt1.v . . . 4 𝑉 = (Vtx‘𝐺)
2 eqid 2778 . . . 4 (Edg‘𝐺) = (Edg‘𝐺)
31, 2frgrregorufrg 27738 . . 3 (𝐺 ∈ FriendGraph → ∀𝑘 ∈ ℕ0 (∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))))
433ad2ant1 1124 . 2 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → ∀𝑘 ∈ ℕ0 (∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))))
51frgrogt3nreg 27833 . 2 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → ∀𝑘 ∈ ℕ0 ¬ 𝐺RegUSGraph𝑘)
6 frgrusgr 27672 . . . . . . 7 (𝐺 ∈ FriendGraph → 𝐺 ∈ USGraph)
76anim1i 608 . . . . . 6 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) → (𝐺 ∈ USGraph ∧ 𝑉 ∈ Fin))
81isfusgr 26669 . . . . . 6 (𝐺 ∈ FinUSGraph ↔ (𝐺 ∈ USGraph ∧ 𝑉 ∈ Fin))
97, 8sylibr 226 . . . . 5 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin) → 𝐺 ∈ FinUSGraph)
1093adant3 1123 . . . 4 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → 𝐺 ∈ FinUSGraph)
11 0red 10382 . . . . . . . 8 ((𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → 0 ∈ ℝ)
12 3re 11459 . . . . . . . . 9 3 ∈ ℝ
1312a1i 11 . . . . . . . 8 ((𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → 3 ∈ ℝ)
14 hashcl 13466 . . . . . . . . . 10 (𝑉 ∈ Fin → (♯‘𝑉) ∈ ℕ0)
1514nn0red 11707 . . . . . . . . 9 (𝑉 ∈ Fin → (♯‘𝑉) ∈ ℝ)
1615adantr 474 . . . . . . . 8 ((𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → (♯‘𝑉) ∈ ℝ)
17 3pos 11491 . . . . . . . . 9 0 < 3
1817a1i 11 . . . . . . . 8 ((𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → 0 < 3)
19 simpr 479 . . . . . . . 8 ((𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → 3 < (♯‘𝑉))
2011, 13, 16, 18, 19lttrd 10539 . . . . . . 7 ((𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → 0 < (♯‘𝑉))
2120gt0ne0d 10941 . . . . . 6 ((𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → (♯‘𝑉) ≠ 0)
22 hasheq0 13473 . . . . . . . 8 (𝑉 ∈ Fin → ((♯‘𝑉) = 0 ↔ 𝑉 = ∅))
2322adantr 474 . . . . . . 7 ((𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → ((♯‘𝑉) = 0 ↔ 𝑉 = ∅))
2423necon3bid 3013 . . . . . 6 ((𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → ((♯‘𝑉) ≠ 0 ↔ 𝑉 ≠ ∅))
2521, 24mpbid 224 . . . . 5 ((𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → 𝑉 ≠ ∅)
26253adant1 1121 . . . 4 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → 𝑉 ≠ ∅)
271fusgrn0degnn0 26851 . . . 4 ((𝐺 ∈ FinUSGraph ∧ 𝑉 ≠ ∅) → ∃𝑡𝑉𝑚 ∈ ℕ0 ((VtxDeg‘𝐺)‘𝑡) = 𝑚)
2810, 26, 27syl2anc 579 . . 3 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → ∃𝑡𝑉𝑚 ∈ ℕ0 ((VtxDeg‘𝐺)‘𝑡) = 𝑚)
29 r19.26 3250 . . . . . . . 8 (∀𝑘 ∈ ℕ0 ((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ¬ 𝐺RegUSGraph𝑘) ↔ (∀𝑘 ∈ ℕ0 (∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ∀𝑘 ∈ ℕ0 ¬ 𝐺RegUSGraph𝑘))
30 simpllr 766 . . . . . . . . . 10 ((((𝑡𝑉𝑚 ∈ ℕ0) ∧ ((VtxDeg‘𝐺)‘𝑡) = 𝑚) ∧ (𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉))) → 𝑚 ∈ ℕ0)
31 fveqeq2 6457 . . . . . . . . . . . . . . 15 (𝑢 = 𝑡 → (((VtxDeg‘𝐺)‘𝑢) = 𝑚 ↔ ((VtxDeg‘𝐺)‘𝑡) = 𝑚))
3231rspcev 3511 . . . . . . . . . . . . . 14 ((𝑡𝑉 ∧ ((VtxDeg‘𝐺)‘𝑡) = 𝑚) → ∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑚)
3332ad4ant13 741 . . . . . . . . . . . . 13 ((((𝑡𝑉𝑚 ∈ ℕ0) ∧ ((VtxDeg‘𝐺)‘𝑡) = 𝑚) ∧ (𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉))) → ∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑚)
34 ornld 1045 . . . . . . . . . . . . 13 (∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑚 → (((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑚 → (𝐺RegUSGraph𝑚 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ¬ 𝐺RegUSGraph𝑚) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺)))
3533, 34syl 17 . . . . . . . . . . . 12 ((((𝑡𝑉𝑚 ∈ ℕ0) ∧ ((VtxDeg‘𝐺)‘𝑡) = 𝑚) ∧ (𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉))) → (((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑚 → (𝐺RegUSGraph𝑚 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ¬ 𝐺RegUSGraph𝑚) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺)))
3635adantr 474 . . . . . . . . . . 11 (((((𝑡𝑉𝑚 ∈ ℕ0) ∧ ((VtxDeg‘𝐺)‘𝑡) = 𝑚) ∧ (𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉))) ∧ 𝑘 = 𝑚) → (((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑚 → (𝐺RegUSGraph𝑚 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ¬ 𝐺RegUSGraph𝑚) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺)))
37 eqeq2 2789 . . . . . . . . . . . . . . . 16 (𝑘 = 𝑚 → (((VtxDeg‘𝐺)‘𝑢) = 𝑘 ↔ ((VtxDeg‘𝐺)‘𝑢) = 𝑚))
3837rexbidv 3237 . . . . . . . . . . . . . . 15 (𝑘 = 𝑚 → (∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 ↔ ∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑚))
39 breq2 4892 . . . . . . . . . . . . . . . 16 (𝑘 = 𝑚 → (𝐺RegUSGraph𝑘𝐺RegUSGraph𝑚))
4039orbi1d 903 . . . . . . . . . . . . . . 15 (𝑘 = 𝑚 → ((𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺)) ↔ (𝐺RegUSGraph𝑚 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))))
4138, 40imbi12d 336 . . . . . . . . . . . . . 14 (𝑘 = 𝑚 → ((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ↔ (∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑚 → (𝐺RegUSGraph𝑚 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺)))))
4239notbid 310 . . . . . . . . . . . . . 14 (𝑘 = 𝑚 → (¬ 𝐺RegUSGraph𝑘 ↔ ¬ 𝐺RegUSGraph𝑚))
4341, 42anbi12d 624 . . . . . . . . . . . . 13 (𝑘 = 𝑚 → (((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ¬ 𝐺RegUSGraph𝑘) ↔ ((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑚 → (𝐺RegUSGraph𝑚 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ¬ 𝐺RegUSGraph𝑚)))
4443imbi1d 333 . . . . . . . . . . . 12 (𝑘 = 𝑚 → ((((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ¬ 𝐺RegUSGraph𝑘) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺)) ↔ (((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑚 → (𝐺RegUSGraph𝑚 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ¬ 𝐺RegUSGraph𝑚) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))))
4544adantl 475 . . . . . . . . . . 11 (((((𝑡𝑉𝑚 ∈ ℕ0) ∧ ((VtxDeg‘𝐺)‘𝑡) = 𝑚) ∧ (𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉))) ∧ 𝑘 = 𝑚) → ((((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ¬ 𝐺RegUSGraph𝑘) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺)) ↔ (((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑚 → (𝐺RegUSGraph𝑚 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ¬ 𝐺RegUSGraph𝑚) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))))
4636, 45mpbird 249 . . . . . . . . . 10 (((((𝑡𝑉𝑚 ∈ ℕ0) ∧ ((VtxDeg‘𝐺)‘𝑡) = 𝑚) ∧ (𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉))) ∧ 𝑘 = 𝑚) → (((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ¬ 𝐺RegUSGraph𝑘) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺)))
4730, 46rspcimdv 3512 . . . . . . . . 9 ((((𝑡𝑉𝑚 ∈ ℕ0) ∧ ((VtxDeg‘𝐺)‘𝑡) = 𝑚) ∧ (𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉))) → (∀𝑘 ∈ ℕ0 ((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ¬ 𝐺RegUSGraph𝑘) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺)))
4847com12 32 . . . . . . . 8 (∀𝑘 ∈ ℕ0 ((∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ¬ 𝐺RegUSGraph𝑘) → ((((𝑡𝑉𝑚 ∈ ℕ0) ∧ ((VtxDeg‘𝐺)‘𝑡) = 𝑚) ∧ (𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉))) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺)))
4929, 48sylbir 227 . . . . . . 7 ((∀𝑘 ∈ ℕ0 (∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) ∧ ∀𝑘 ∈ ℕ0 ¬ 𝐺RegUSGraph𝑘) → ((((𝑡𝑉𝑚 ∈ ℕ0) ∧ ((VtxDeg‘𝐺)‘𝑡) = 𝑚) ∧ (𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉))) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺)))
5049expcom 404 . . . . . 6 (∀𝑘 ∈ ℕ0 ¬ 𝐺RegUSGraph𝑘 → (∀𝑘 ∈ ℕ0 (∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) → ((((𝑡𝑉𝑚 ∈ ℕ0) ∧ ((VtxDeg‘𝐺)‘𝑡) = 𝑚) ∧ (𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉))) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))))
5150com13 88 . . . . 5 ((((𝑡𝑉𝑚 ∈ ℕ0) ∧ ((VtxDeg‘𝐺)‘𝑡) = 𝑚) ∧ (𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉))) → (∀𝑘 ∈ ℕ0 (∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) → (∀𝑘 ∈ ℕ0 ¬ 𝐺RegUSGraph𝑘 → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))))
5251exp31 412 . . . 4 ((𝑡𝑉𝑚 ∈ ℕ0) → (((VtxDeg‘𝐺)‘𝑡) = 𝑚 → ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → (∀𝑘 ∈ ℕ0 (∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) → (∀𝑘 ∈ ℕ0 ¬ 𝐺RegUSGraph𝑘 → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))))))
5352rexlimivv 3219 . . 3 (∃𝑡𝑉𝑚 ∈ ℕ0 ((VtxDeg‘𝐺)‘𝑡) = 𝑚 → ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → (∀𝑘 ∈ ℕ0 (∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) → (∀𝑘 ∈ ℕ0 ¬ 𝐺RegUSGraph𝑘 → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺)))))
5428, 53mpcom 38 . 2 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → (∀𝑘 ∈ ℕ0 (∃𝑢𝑉 ((VtxDeg‘𝐺)‘𝑢) = 𝑘 → (𝐺RegUSGraph𝑘 ∨ ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))) → (∀𝑘 ∈ ℕ0 ¬ 𝐺RegUSGraph𝑘 → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))))
554, 5, 54mp2d 49 1 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 3 < (♯‘𝑉)) → ∃𝑣𝑉𝑤 ∈ (𝑉 ∖ {𝑣}){𝑣, 𝑤} ∈ (Edg‘𝐺))
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 198  wa 386  wo 836  w3a 1071   = wceq 1601  wcel 2107  wne 2969  wral 3090  wrex 3091  cdif 3789  c0 4141  {csn 4398  {cpr 4400   class class class wbr 4888  cfv 6137  Fincfn 8243  cr 10273  0cc0 10274   < clt 10413  3c3 11435  0cn0 11646  chash 13439  Vtxcvtx 26348  Edgcedg 26399  USGraphcusgr 26502  FinUSGraphcfusgr 26667  VtxDegcvtxdg 26817  RegUSGraphcrusgr 26908   FriendGraph cfrgr 27668
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1839  ax-4 1853  ax-5 1953  ax-6 2021  ax-7 2055  ax-8 2109  ax-9 2116  ax-10 2135  ax-11 2150  ax-12 2163  ax-13 2334  ax-ext 2754  ax-rep 5008  ax-sep 5019  ax-nul 5027  ax-pow 5079  ax-pr 5140  ax-un 7228  ax-inf2 8837  ax-ac2 9622  ax-cnex 10330  ax-resscn 10331  ax-1cn 10332  ax-icn 10333  ax-addcl 10334  ax-addrcl 10335  ax-mulcl 10336  ax-mulrcl 10337  ax-mulcom 10338  ax-addass 10339  ax-mulass 10340  ax-distr 10341  ax-i2m1 10342  ax-1ne0 10343  ax-1rid 10344  ax-rnegex 10345  ax-rrecex 10346  ax-cnre 10347  ax-pre-lttri 10348  ax-pre-lttrn 10349  ax-pre-ltadd 10350  ax-pre-mulgt0 10351  ax-pre-sup 10352
This theorem depends on definitions:  df-bi 199  df-an 387  df-or 837  df-ifp 1047  df-3or 1072  df-3an 1073  df-tru 1605  df-fal 1615  df-ex 1824  df-nf 1828  df-sb 2012  df-mo 2551  df-eu 2587  df-clab 2764  df-cleq 2770  df-clel 2774  df-nfc 2921  df-ne 2970  df-nel 3076  df-ral 3095  df-rex 3096  df-reu 3097  df-rmo 3098  df-rab 3099  df-v 3400  df-sbc 3653  df-csb 3752  df-dif 3795  df-un 3797  df-in 3799  df-ss 3806  df-pss 3808  df-nul 4142  df-if 4308  df-pw 4381  df-sn 4399  df-pr 4401  df-tp 4403  df-op 4405  df-uni 4674  df-int 4713  df-iun 4757  df-disj 4857  df-br 4889  df-opab 4951  df-mpt 4968  df-tr 4990  df-id 5263  df-eprel 5268  df-po 5276  df-so 5277  df-fr 5316  df-se 5317  df-we 5318  df-xp 5363  df-rel 5364  df-cnv 5365  df-co 5366  df-dm 5367  df-rn 5368  df-res 5369  df-ima 5370  df-pred 5935  df-ord 5981  df-on 5982  df-lim 5983  df-suc 5984  df-iota 6101  df-fun 6139  df-fn 6140  df-f 6141  df-f1 6142  df-fo 6143  df-f1o 6144  df-fv 6145  df-isom 6146  df-riota 6885  df-ov 6927  df-oprab 6928  df-mpt2 6929  df-om 7346  df-1st 7447  df-2nd 7448  df-wrecs 7691  df-recs 7753  df-rdg 7791  df-1o 7845  df-2o 7846  df-oadd 7849  df-er 8028  df-ec 8030  df-qs 8034  df-map 8144  df-pm 8145  df-en 8244  df-dom 8245  df-sdom 8246  df-fin 8247  df-sup 8638  df-inf 8639  df-oi 8706  df-card 9100  df-ac 9274  df-cda 9327  df-pnf 10415  df-mnf 10416  df-xr 10417  df-ltxr 10418  df-le 10419  df-sub 10610  df-neg 10611  df-div 11035  df-nn 11379  df-2 11442  df-3 11443  df-n0 11647  df-xnn0 11719  df-z 11733  df-uz 11997  df-rp 12142  df-xadd 12262  df-ico 12497  df-fz 12648  df-fzo 12789  df-fl 12916  df-mod 12992  df-seq 13124  df-exp 13183  df-hash 13440  df-word 13604  df-lsw 13657  df-concat 13665  df-s1 13690  df-substr 13735  df-pfx 13784  df-reps 13919  df-csh 13940  df-s2 14003  df-s3 14004  df-cj 14250  df-re 14251  df-im 14252  df-sqrt 14386  df-abs 14387  df-clim 14631  df-sum 14829  df-dvds 15392  df-gcd 15627  df-prm 15795  df-phi 15879  df-vtx 26350  df-iedg 26351  df-edg 26400  df-uhgr 26410  df-ushgr 26411  df-upgr 26434  df-umgr 26435  df-uspgr 26503  df-usgr 26504  df-fusgr 26668  df-nbgr 26684  df-vtxdg 26818  df-rgr 26909  df-rusgr 26910  df-wlks 26951  df-wlkson 26952  df-trls 27047  df-trlson 27048  df-pths 27072  df-spths 27073  df-pthson 27074  df-spthson 27075  df-wwlks 27183  df-wwlksn 27184  df-wwlksnon 27185  df-wspthsn 27186  df-wspthsnon 27187  df-clwwlk 27366  df-clwwlkn 27418  df-clwwlknon 27494  df-conngr 27594  df-frgr 27669
This theorem is referenced by:  friendship  27835
  Copyright terms: Public domain W3C validator