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

Theorem frgrregord13 28333
Description: If a nonempty finite friendship graph is 𝐾-regular, then it must have order 1 or 3. Special case of frgrregord013 28332. (Contributed by Alexander van der Vekens, 9-Oct-2018.) (Revised by AV, 4-Jun-2021.)
Hypothesis
Ref Expression
frgrreggt1.v 𝑉 = (Vtx‘𝐺)
Assertion
Ref Expression
frgrregord13 (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) ∧ 𝐺 RegUSGraph 𝐾) → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3))

Proof of Theorem frgrregord13
StepHypRef Expression
1 simpl1 1192 . . 3 (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) ∧ 𝐺 RegUSGraph 𝐾) → 𝐺 ∈ FriendGraph )
2 simpl2 1193 . . 3 (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) ∧ 𝐺 RegUSGraph 𝐾) → 𝑉 ∈ Fin)
3 simpr 488 . . 3 (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) ∧ 𝐺 RegUSGraph 𝐾) → 𝐺 RegUSGraph 𝐾)
4 frgrreggt1.v . . . 4 𝑉 = (Vtx‘𝐺)
54frgrregord013 28332 . . 3 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝐺 RegUSGraph 𝐾) → ((♯‘𝑉) = 0 ∨ (♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3))
61, 2, 3, 5syl3anc 1372 . 2 (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) ∧ 𝐺 RegUSGraph 𝐾) → ((♯‘𝑉) = 0 ∨ (♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3))
7 hasheq0 13817 . . . . . . . . 9 (𝑉 ∈ Fin → ((♯‘𝑉) = 0 ↔ 𝑉 = ∅))
8 eqneqall 2945 . . . . . . . . 9 (𝑉 = ∅ → (𝑉 ≠ ∅ → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3)))
97, 8syl6bi 256 . . . . . . . 8 (𝑉 ∈ Fin → ((♯‘𝑉) = 0 → (𝑉 ≠ ∅ → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3))))
109com23 86 . . . . . . 7 (𝑉 ∈ Fin → (𝑉 ≠ ∅ → ((♯‘𝑉) = 0 → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3))))
1110a1i 11 . . . . . 6 (𝐺 ∈ FriendGraph → (𝑉 ∈ Fin → (𝑉 ≠ ∅ → ((♯‘𝑉) = 0 → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3)))))
12113imp 1112 . . . . 5 ((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) → ((♯‘𝑉) = 0 → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3)))
1312adantr 484 . . . 4 (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) ∧ 𝐺 RegUSGraph 𝐾) → ((♯‘𝑉) = 0 → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3)))
1413com12 32 . . 3 ((♯‘𝑉) = 0 → (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) ∧ 𝐺 RegUSGraph 𝐾) → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3)))
15 orc 866 . . . 4 ((♯‘𝑉) = 1 → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3))
1615a1d 25 . . 3 ((♯‘𝑉) = 1 → (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) ∧ 𝐺 RegUSGraph 𝐾) → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3)))
17 olc 867 . . . 4 ((♯‘𝑉) = 3 → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3))
1817a1d 25 . . 3 ((♯‘𝑉) = 3 → (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) ∧ 𝐺 RegUSGraph 𝐾) → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3)))
1914, 16, 183jaoi 1428 . 2 (((♯‘𝑉) = 0 ∨ (♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3) → (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) ∧ 𝐺 RegUSGraph 𝐾) → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3)))
206, 19mpcom 38 1 (((𝐺 ∈ FriendGraph ∧ 𝑉 ∈ Fin ∧ 𝑉 ≠ ∅) ∧ 𝐺 RegUSGraph 𝐾) → ((♯‘𝑉) = 1 ∨ (♯‘𝑉) = 3))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wa 399  wo 846  w3o 1087  w3a 1088   = wceq 1542  wcel 2113  wne 2934  c0 4212   class class class wbr 5031  cfv 6340  Fincfn 8556  0cc0 10616  1c1 10617  3c3 11773  chash 13783  Vtxcvtx 26941   RegUSGraph crusgr 27498   FriendGraph cfrgr 28195
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1802  ax-4 1816  ax-5 1916  ax-6 1974  ax-7 2019  ax-8 2115  ax-9 2123  ax-10 2144  ax-11 2161  ax-12 2178  ax-ext 2710  ax-rep 5155  ax-sep 5168  ax-nul 5175  ax-pow 5233  ax-pr 5297  ax-un 7480  ax-inf2 9178  ax-ac2 9964  ax-cnex 10672  ax-resscn 10673  ax-1cn 10674  ax-icn 10675  ax-addcl 10676  ax-addrcl 10677  ax-mulcl 10678  ax-mulrcl 10679  ax-mulcom 10680  ax-addass 10681  ax-mulass 10682  ax-distr 10683  ax-i2m1 10684  ax-1ne0 10685  ax-1rid 10686  ax-rnegex 10687  ax-rrecex 10688  ax-cnre 10689  ax-pre-lttri 10690  ax-pre-lttrn 10691  ax-pre-ltadd 10692  ax-pre-mulgt0 10693  ax-pre-sup 10694
This theorem depends on definitions:  df-bi 210  df-an 400  df-or 847  df-ifp 1063  df-3or 1089  df-3an 1090  df-tru 1545  df-fal 1555  df-ex 1787  df-nf 1791  df-sb 2074  df-mo 2540  df-eu 2570  df-clab 2717  df-cleq 2730  df-clel 2811  df-nfc 2881  df-ne 2935  df-nel 3039  df-ral 3058  df-rex 3059  df-reu 3060  df-rmo 3061  df-rab 3062  df-v 3400  df-sbc 3683  df-csb 3792  df-dif 3847  df-un 3849  df-in 3851  df-ss 3861  df-pss 3863  df-nul 4213  df-if 4416  df-pw 4491  df-sn 4518  df-pr 4520  df-tp 4522  df-op 4524  df-uni 4798  df-int 4838  df-iun 4884  df-disj 4997  df-br 5032  df-opab 5094  df-mpt 5112  df-tr 5138  df-id 5430  df-eprel 5435  df-po 5443  df-so 5444  df-fr 5484  df-se 5485  df-we 5486  df-xp 5532  df-rel 5533  df-cnv 5534  df-co 5535  df-dm 5536  df-rn 5537  df-res 5538  df-ima 5539  df-pred 6130  df-ord 6176  df-on 6177  df-lim 6178  df-suc 6179  df-iota 6298  df-fun 6342  df-fn 6343  df-f 6344  df-f1 6345  df-fo 6346  df-f1o 6347  df-fv 6348  df-isom 6349  df-riota 7128  df-ov 7174  df-oprab 7175  df-mpo 7176  df-om 7601  df-1st 7715  df-2nd 7716  df-wrecs 7977  df-recs 8038  df-rdg 8076  df-1o 8132  df-2o 8133  df-oadd 8136  df-er 8321  df-ec 8323  df-qs 8327  df-map 8440  df-pm 8441  df-en 8557  df-dom 8558  df-sdom 8559  df-fin 8560  df-sup 8980  df-inf 8981  df-oi 9048  df-dju 9404  df-card 9442  df-ac 9617  df-pnf 10756  df-mnf 10757  df-xr 10758  df-ltxr 10759  df-le 10760  df-sub 10951  df-neg 10952  df-div 11377  df-nn 11718  df-2 11780  df-3 11781  df-n0 11978  df-xnn0 12050  df-z 12064  df-uz 12326  df-rp 12474  df-xadd 12592  df-ico 12828  df-fz 12983  df-fzo 13126  df-fl 13254  df-mod 13330  df-seq 13462  df-exp 13523  df-hash 13784  df-word 13957  df-lsw 14005  df-concat 14013  df-s1 14040  df-substr 14093  df-pfx 14123  df-reps 14221  df-csh 14241  df-s2 14300  df-s3 14301  df-cj 14549  df-re 14550  df-im 14551  df-sqrt 14685  df-abs 14686  df-clim 14936  df-sum 15137  df-dvds 15701  df-gcd 15939  df-prm 16114  df-phi 16204  df-vtx 26943  df-iedg 26944  df-edg 26993  df-uhgr 27003  df-ushgr 27004  df-upgr 27027  df-umgr 27028  df-uspgr 27095  df-usgr 27096  df-fusgr 27259  df-nbgr 27275  df-vtxdg 27408  df-rgr 27499  df-rusgr 27500  df-wlks 27541  df-wlkson 27542  df-trls 27634  df-trlson 27635  df-pths 27657  df-spths 27658  df-pthson 27659  df-spthson 27660  df-wwlks 27768  df-wwlksn 27769  df-wwlksnon 27770  df-wspthsn 27771  df-wspthsnon 27772  df-clwwlk 27919  df-clwwlkn 27962  df-clwwlknon 28025  df-conngr 28124  df-frgr 28196
This theorem is referenced by:  frgrogt3nreg  28334
  Copyright terms: Public domain W3C validator