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

Theorem egrsubgr 26339
Description: An empty graph consisting of a subset of vertices of a graph (and having no edges) is a subgraph of the graph. (Contributed by AV, 17-Nov-2020.) (Proof shortened by AV, 17-Dec-2020.)
Assertion
Ref Expression
egrsubgr (((𝐺𝑊𝑆𝑈) ∧ (Vtx‘𝑆) ⊆ (Vtx‘𝐺) ∧ (Fun (iEdg‘𝑆) ∧ (Edg‘𝑆) = ∅)) → 𝑆 SubGraph 𝐺)

Proof of Theorem egrsubgr
StepHypRef Expression
1 simp2 1129 . 2 (((𝐺𝑊𝑆𝑈) ∧ (Vtx‘𝑆) ⊆ (Vtx‘𝐺) ∧ (Fun (iEdg‘𝑆) ∧ (Edg‘𝑆) = ∅)) → (Vtx‘𝑆) ⊆ (Vtx‘𝐺))
2 eqid 2748 . . . . . . 7 (iEdg‘𝑆) = (iEdg‘𝑆)
3 eqid 2748 . . . . . . 7 (Edg‘𝑆) = (Edg‘𝑆)
42, 3edg0iedg0 26119 . . . . . 6 (Fun (iEdg‘𝑆) → ((Edg‘𝑆) = ∅ ↔ (iEdg‘𝑆) = ∅))
54adantl 473 . . . . 5 (((𝐺𝑊𝑆𝑈) ∧ Fun (iEdg‘𝑆)) → ((Edg‘𝑆) = ∅ ↔ (iEdg‘𝑆) = ∅))
6 res0 5543 . . . . . . 7 ((iEdg‘𝐺) ↾ ∅) = ∅
76eqcomi 2757 . . . . . 6 ∅ = ((iEdg‘𝐺) ↾ ∅)
8 id 22 . . . . . 6 ((iEdg‘𝑆) = ∅ → (iEdg‘𝑆) = ∅)
9 dmeq 5467 . . . . . . . 8 ((iEdg‘𝑆) = ∅ → dom (iEdg‘𝑆) = dom ∅)
10 dm0 5482 . . . . . . . 8 dom ∅ = ∅
119, 10syl6eq 2798 . . . . . . 7 ((iEdg‘𝑆) = ∅ → dom (iEdg‘𝑆) = ∅)
1211reseq2d 5539 . . . . . 6 ((iEdg‘𝑆) = ∅ → ((iEdg‘𝐺) ↾ dom (iEdg‘𝑆)) = ((iEdg‘𝐺) ↾ ∅))
137, 8, 123eqtr4a 2808 . . . . 5 ((iEdg‘𝑆) = ∅ → (iEdg‘𝑆) = ((iEdg‘𝐺) ↾ dom (iEdg‘𝑆)))
145, 13syl6bi 243 . . . 4 (((𝐺𝑊𝑆𝑈) ∧ Fun (iEdg‘𝑆)) → ((Edg‘𝑆) = ∅ → (iEdg‘𝑆) = ((iEdg‘𝐺) ↾ dom (iEdg‘𝑆))))
1514impr 650 . . 3 (((𝐺𝑊𝑆𝑈) ∧ (Fun (iEdg‘𝑆) ∧ (Edg‘𝑆) = ∅)) → (iEdg‘𝑆) = ((iEdg‘𝐺) ↾ dom (iEdg‘𝑆)))
16153adant2 1123 . 2 (((𝐺𝑊𝑆𝑈) ∧ (Vtx‘𝑆) ⊆ (Vtx‘𝐺) ∧ (Fun (iEdg‘𝑆) ∧ (Edg‘𝑆) = ∅)) → (iEdg‘𝑆) = ((iEdg‘𝐺) ↾ dom (iEdg‘𝑆)))
17 0ss 4103 . . . . 5 ∅ ⊆ 𝒫 (Vtx‘𝑆)
18 sseq1 3755 . . . . 5 ((Edg‘𝑆) = ∅ → ((Edg‘𝑆) ⊆ 𝒫 (Vtx‘𝑆) ↔ ∅ ⊆ 𝒫 (Vtx‘𝑆)))
1917, 18mpbiri 248 . . . 4 ((Edg‘𝑆) = ∅ → (Edg‘𝑆) ⊆ 𝒫 (Vtx‘𝑆))
2019adantl 473 . . 3 ((Fun (iEdg‘𝑆) ∧ (Edg‘𝑆) = ∅) → (Edg‘𝑆) ⊆ 𝒫 (Vtx‘𝑆))
21203ad2ant3 1127 . 2 (((𝐺𝑊𝑆𝑈) ∧ (Vtx‘𝑆) ⊆ (Vtx‘𝐺) ∧ (Fun (iEdg‘𝑆) ∧ (Edg‘𝑆) = ∅)) → (Edg‘𝑆) ⊆ 𝒫 (Vtx‘𝑆))
22 eqid 2748 . . . 4 (Vtx‘𝑆) = (Vtx‘𝑆)
23 eqid 2748 . . . 4 (Vtx‘𝐺) = (Vtx‘𝐺)
24 eqid 2748 . . . 4 (iEdg‘𝐺) = (iEdg‘𝐺)
2522, 23, 2, 24, 3issubgr 26333 . . 3 ((𝐺𝑊𝑆𝑈) → (𝑆 SubGraph 𝐺 ↔ ((Vtx‘𝑆) ⊆ (Vtx‘𝐺) ∧ (iEdg‘𝑆) = ((iEdg‘𝐺) ↾ dom (iEdg‘𝑆)) ∧ (Edg‘𝑆) ⊆ 𝒫 (Vtx‘𝑆))))
26253ad2ant1 1125 . 2 (((𝐺𝑊𝑆𝑈) ∧ (Vtx‘𝑆) ⊆ (Vtx‘𝐺) ∧ (Fun (iEdg‘𝑆) ∧ (Edg‘𝑆) = ∅)) → (𝑆 SubGraph 𝐺 ↔ ((Vtx‘𝑆) ⊆ (Vtx‘𝐺) ∧ (iEdg‘𝑆) = ((iEdg‘𝐺) ↾ dom (iEdg‘𝑆)) ∧ (Edg‘𝑆) ⊆ 𝒫 (Vtx‘𝑆))))
271, 16, 21, 26mpbir3and 1406 1 (((𝐺𝑊𝑆𝑈) ∧ (Vtx‘𝑆) ⊆ (Vtx‘𝐺) ∧ (Fun (iEdg‘𝑆) ∧ (Edg‘𝑆) = ∅)) → 𝑆 SubGraph 𝐺)
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 196  wa 383  w3a 1072   = wceq 1620  wcel 2127  wss 3703  c0 4046  𝒫 cpw 4290   class class class wbr 4792  dom cdm 5254  cres 5256  Fun wfun 6031  cfv 6037  Vtxcvtx 26044  iEdgciedg 26045  Edgcedg 26109   SubGraph csubgr 26329
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1859  ax-4 1874  ax-5 1976  ax-6 2042  ax-7 2078  ax-8 2129  ax-9 2136  ax-10 2156  ax-11 2171  ax-12 2184  ax-13 2379  ax-ext 2728  ax-sep 4921  ax-nul 4929  ax-pow 4980  ax-pr 5043  ax-un 7102
This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3an 1074  df-tru 1623  df-ex 1842  df-nf 1847  df-sb 2035  df-eu 2599  df-mo 2600  df-clab 2735  df-cleq 2741  df-clel 2744  df-nfc 2879  df-ral 3043  df-rex 3044  df-rab 3047  df-v 3330  df-sbc 3565  df-csb 3663  df-dif 3706  df-un 3708  df-in 3710  df-ss 3717  df-nul 4047  df-if 4219  df-pw 4292  df-sn 4310  df-pr 4312  df-op 4316  df-uni 4577  df-br 4793  df-opab 4853  df-mpt 4870  df-id 5162  df-xp 5260  df-rel 5261  df-cnv 5262  df-co 5263  df-dm 5264  df-rn 5265  df-res 5266  df-iota 6000  df-fun 6039  df-fv 6045  df-edg 26110  df-subgr 26330
This theorem is referenced by:  0uhgrsubgr  26341
  Copyright terms: Public domain W3C validator