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

Theorem upgredg 27518
Description: For each edge in a pseudograph, there are two vertices which are connected by this edge. (Contributed by AV, 4-Nov-2020.) (Proof shortened by AV, 26-Nov-2021.)
Hypotheses
Ref Expression
upgredg.v 𝑉 = (Vtx‘𝐺)
upgredg.e 𝐸 = (Edg‘𝐺)
Assertion
Ref Expression
upgredg ((𝐺 ∈ UPGraph ∧ 𝐶𝐸) → ∃𝑎𝑉𝑏𝑉 𝐶 = {𝑎, 𝑏})
Distinct variable groups:   𝐶,𝑎,𝑏   𝐺,𝑎,𝑏   𝑉,𝑎,𝑏
Allowed substitution hints:   𝐸(𝑎,𝑏)

Proof of Theorem upgredg
Dummy variable 𝑥 is distinct from all other variables.
StepHypRef Expression
1 upgredg.e . . . . . 6 𝐸 = (Edg‘𝐺)
2 edgval 27430 . . . . . . 7 (Edg‘𝐺) = ran (iEdg‘𝐺)
32a1i 11 . . . . . 6 (𝐺 ∈ UPGraph → (Edg‘𝐺) = ran (iEdg‘𝐺))
41, 3eqtrid 2792 . . . . 5 (𝐺 ∈ UPGraph → 𝐸 = ran (iEdg‘𝐺))
54eleq2d 2826 . . . 4 (𝐺 ∈ UPGraph → (𝐶𝐸𝐶 ∈ ran (iEdg‘𝐺)))
6 upgredg.v . . . . . . 7 𝑉 = (Vtx‘𝐺)
7 eqid 2740 . . . . . . 7 (iEdg‘𝐺) = (iEdg‘𝐺)
86, 7upgrf 27467 . . . . . 6 (𝐺 ∈ UPGraph → (iEdg‘𝐺):dom (iEdg‘𝐺)⟶{𝑥 ∈ (𝒫 𝑉 ∖ {∅}) ∣ (♯‘𝑥) ≤ 2})
98frnd 6606 . . . . 5 (𝐺 ∈ UPGraph → ran (iEdg‘𝐺) ⊆ {𝑥 ∈ (𝒫 𝑉 ∖ {∅}) ∣ (♯‘𝑥) ≤ 2})
109sseld 3925 . . . 4 (𝐺 ∈ UPGraph → (𝐶 ∈ ran (iEdg‘𝐺) → 𝐶 ∈ {𝑥 ∈ (𝒫 𝑉 ∖ {∅}) ∣ (♯‘𝑥) ≤ 2}))
115, 10sylbid 239 . . 3 (𝐺 ∈ UPGraph → (𝐶𝐸𝐶 ∈ {𝑥 ∈ (𝒫 𝑉 ∖ {∅}) ∣ (♯‘𝑥) ≤ 2}))
1211imp 407 . 2 ((𝐺 ∈ UPGraph ∧ 𝐶𝐸) → 𝐶 ∈ {𝑥 ∈ (𝒫 𝑉 ∖ {∅}) ∣ (♯‘𝑥) ≤ 2})
13 fveq2 6771 . . . . 5 (𝑥 = 𝐶 → (♯‘𝑥) = (♯‘𝐶))
1413breq1d 5089 . . . 4 (𝑥 = 𝐶 → ((♯‘𝑥) ≤ 2 ↔ (♯‘𝐶) ≤ 2))
1514elrab 3626 . . 3 (𝐶 ∈ {𝑥 ∈ (𝒫 𝑉 ∖ {∅}) ∣ (♯‘𝑥) ≤ 2} ↔ (𝐶 ∈ (𝒫 𝑉 ∖ {∅}) ∧ (♯‘𝐶) ≤ 2))
16 hashle2prv 14203 . . . 4 (𝐶 ∈ (𝒫 𝑉 ∖ {∅}) → ((♯‘𝐶) ≤ 2 ↔ ∃𝑎𝑉𝑏𝑉 𝐶 = {𝑎, 𝑏}))
1716biimpa 477 . . 3 ((𝐶 ∈ (𝒫 𝑉 ∖ {∅}) ∧ (♯‘𝐶) ≤ 2) → ∃𝑎𝑉𝑏𝑉 𝐶 = {𝑎, 𝑏})
1815, 17sylbi 216 . 2 (𝐶 ∈ {𝑥 ∈ (𝒫 𝑉 ∖ {∅}) ∣ (♯‘𝑥) ≤ 2} → ∃𝑎𝑉𝑏𝑉 𝐶 = {𝑎, 𝑏})
1912, 18syl 17 1 ((𝐺 ∈ UPGraph ∧ 𝐶𝐸) → ∃𝑎𝑉𝑏𝑉 𝐶 = {𝑎, 𝑏})
Colors of variables: wff setvar class
Syntax hints:  wi 4  wa 396   = wceq 1542  wcel 2110  wrex 3067  {crab 3070  cdif 3889  c0 4262  𝒫 cpw 4539  {csn 4567  {cpr 4569   class class class wbr 5079  dom cdm 5590  ran crn 5591  cfv 6432  cle 11021  2c2 12039  chash 14055  Vtxcvtx 27377  iEdgciedg 27378  Edgcedg 27428  UPGraphcupgr 27461
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 1917  ax-6 1975  ax-7 2015  ax-8 2112  ax-9 2120  ax-10 2141  ax-11 2158  ax-12 2175  ax-ext 2711  ax-sep 5227  ax-nul 5234  ax-pow 5292  ax-pr 5356  ax-un 7583  ax-cnex 10938  ax-resscn 10939  ax-1cn 10940  ax-icn 10941  ax-addcl 10942  ax-addrcl 10943  ax-mulcl 10944  ax-mulrcl 10945  ax-mulcom 10946  ax-addass 10947  ax-mulass 10948  ax-distr 10949  ax-i2m1 10950  ax-1ne0 10951  ax-1rid 10952  ax-rnegex 10953  ax-rrecex 10954  ax-cnre 10955  ax-pre-lttri 10956  ax-pre-lttrn 10957  ax-pre-ltadd 10958  ax-pre-mulgt0 10959
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 845  df-3or 1087  df-3an 1088  df-tru 1545  df-fal 1555  df-ex 1787  df-nf 1791  df-sb 2072  df-mo 2542  df-eu 2571  df-clab 2718  df-cleq 2732  df-clel 2818  df-nfc 2891  df-ne 2946  df-nel 3052  df-ral 3071  df-rex 3072  df-reu 3073  df-rab 3075  df-v 3433  df-sbc 3721  df-csb 3838  df-dif 3895  df-un 3897  df-in 3899  df-ss 3909  df-pss 3911  df-nul 4263  df-if 4466  df-pw 4541  df-sn 4568  df-pr 4570  df-op 4574  df-uni 4846  df-int 4886  df-iun 4932  df-br 5080  df-opab 5142  df-mpt 5163  df-tr 5197  df-id 5490  df-eprel 5496  df-po 5504  df-so 5505  df-fr 5545  df-we 5547  df-xp 5596  df-rel 5597  df-cnv 5598  df-co 5599  df-dm 5600  df-rn 5601  df-res 5602  df-ima 5603  df-pred 6201  df-ord 6268  df-on 6269  df-lim 6270  df-suc 6271  df-iota 6390  df-fun 6434  df-fn 6435  df-f 6436  df-f1 6437  df-fo 6438  df-f1o 6439  df-fv 6440  df-riota 7229  df-ov 7275  df-oprab 7276  df-mpo 7277  df-om 7708  df-1st 7825  df-2nd 7826  df-frecs 8089  df-wrecs 8120  df-recs 8194  df-rdg 8233  df-1o 8289  df-2o 8290  df-oadd 8293  df-er 8490  df-en 8726  df-dom 8727  df-sdom 8728  df-fin 8729  df-dju 9670  df-card 9708  df-pnf 11022  df-mnf 11023  df-xr 11024  df-ltxr 11025  df-le 11026  df-sub 11218  df-neg 11219  df-nn 11985  df-2 12047  df-n0 12245  df-xnn0 12317  df-z 12331  df-uz 12594  df-fz 13251  df-hash 14056  df-edg 27429  df-upgr 27463
This theorem is referenced by:  upgrpredgv  27520  upgredg2vtx  27522  upgredgpr  27523  edglnl  27524  numedglnl  27525  isomuspgrlem1  45258  isomuspgrlem2b  45260  isomuspgrlem2d  45262
  Copyright terms: Public domain W3C validator