Theorem structtocusgr 29534

Description: Any (extensible) structure with a base set can be made a complete simple graph with the set of pairs of elements of the base set regarded as edges. (Contributed by AV, 10-Nov-2021.) (Revised by AV, 17-Nov-2021.) (Proof shortened by AV, 14-Feb-2022.)

Hypotheses

Ref	Expression
structtousgr.p	⊢ 𝑃 = {𝑥 ∈ 𝒫 (Base‘𝑆) ∣ (♯‘𝑥) = 2}
structtousgr.s	⊢ (𝜑 → 𝑆 Struct 𝑋)
structtousgr.g	⊢ 𝐺 = (𝑆 sSet ⟨(.ef‘ndx), ( I ↾ 𝑃)⟩)
structtousgr.b	⊢ (𝜑 → (Base‘ndx) ∈ dom 𝑆)

Assertion

Ref	Expression
structtocusgr	⊢ (𝜑 → 𝐺 ∈ ComplUSGraph)

Distinct variable groups:   𝑥,𝐺   𝑥,𝑃   𝑥,𝑆   𝜑,𝑥

Allowed substitution hint:   𝑋(𝑥)

Proof of Theorem structtocusgr

Dummy variables 𝑒 𝑛 𝑣 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		structtousgr.p	. . 3 ⊢ 𝑃 = {𝑥 ∈ 𝒫 (Base‘𝑆) ∣ (♯‘𝑥) = 2}
2		structtousgr.s	. . 3 ⊢ (𝜑 → 𝑆 Struct 𝑋)
3		structtousgr.g	. . 3 ⊢ 𝐺 = (𝑆 sSet ⟨(.ef‘ndx), ( I ↾ 𝑃)⟩)
4		structtousgr.b	. . 3 ⊢ (𝜑 → (Base‘ndx) ∈ dom 𝑆)
5	1, 2, 3, 4	structtousgr 29533	. 2 ⊢ (𝜑 → 𝐺 ∈ USGraph)
6		simpr 485	. . . . 5 ⊢ ((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) → 𝑣 ∈ (Vtx‘𝐺))
7		eldifi 4062	. . . . . . . 8 ⊢ (𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣}) → 𝑛 ∈ (Vtx‘𝐺))
8	6, 7	anim12ci 620	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) ∧ 𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣})) → (𝑛 ∈ (Vtx‘𝐺) ∧ 𝑣 ∈ (Vtx‘𝐺)))
9		eldifsni 4724	. . . . . . . 8 ⊢ (𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣}) → 𝑛 ≠ 𝑣)
10	9	adantl 482	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) ∧ 𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣})) → 𝑛 ≠ 𝑣)
11		fvexd 6843	. . . . . . . . 9 ⊢ (((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) ∧ 𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣})) → (Base‘𝑆) ∈ V)
12	3	fveq2i 6831	. . . . . . . . . . . . 13 ⊢ (Vtx‘𝐺) = (Vtx‘(𝑆 sSet ⟨(.ef‘ndx), ( I ↾ 𝑃)⟩))
13		eqid 2739	. . . . . . . . . . . . . 14 ⊢ (.ef‘ndx) = (.ef‘ndx)
14		fvex 6841	. . . . . . . . . . . . . . 15 ⊢ (Base‘𝑆) ∈ V
15	1	cusgrexilem1 29527	. . . . . . . . . . . . . . 15 ⊢ ((Base‘𝑆) ∈ V → ( I ↾ 𝑃) ∈ V)
16	14, 15	mp1i 13	. . . . . . . . . . . . . 14 ⊢ (𝜑 → ( I ↾ 𝑃) ∈ V)
17	13, 2, 4, 16	setsvtx 29123	. . . . . . . . . . . . 13 ⊢ (𝜑 → (Vtx‘(𝑆 sSet ⟨(.ef‘ndx), ( I ↾ 𝑃)⟩)) = (Base‘𝑆))
18	12, 17	eqtrid 2786	. . . . . . . . . . . 12 ⊢ (𝜑 → (Vtx‘𝐺) = (Base‘𝑆))
19	18	eleq2d 2825	. . . . . . . . . . 11 ⊢ (𝜑 → (𝑣 ∈ (Vtx‘𝐺) ↔ 𝑣 ∈ (Base‘𝑆)))
20	19	biimpa 477	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) → 𝑣 ∈ (Base‘𝑆))
21	20	adantr 481	. . . . . . . . 9 ⊢ (((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) ∧ 𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣})) → 𝑣 ∈ (Base‘𝑆))
22	18	difeq1d 4057	. . . . . . . . . . . . 13 ⊢ (𝜑 → ((Vtx‘𝐺) ∖ {𝑣}) = ((Base‘𝑆) ∖ {𝑣}))
23	22	eleq2d 2825	. . . . . . . . . . . 12 ⊢ (𝜑 → (𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣}) ↔ 𝑛 ∈ ((Base‘𝑆) ∖ {𝑣})))
24	23	biimpd 230	. . . . . . . . . . 11 ⊢ (𝜑 → (𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣}) → 𝑛 ∈ ((Base‘𝑆) ∖ {𝑣})))
25	24	adantr 481	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) → (𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣}) → 𝑛 ∈ ((Base‘𝑆) ∖ {𝑣})))
26	25	imp 407	. . . . . . . . 9 ⊢ (((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) ∧ 𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣})) → 𝑛 ∈ ((Base‘𝑆) ∖ {𝑣}))
27	1	cusgrexilem2 29530	. . . . . . . . 9 ⊢ ((((Base‘𝑆) ∈ V ∧ 𝑣 ∈ (Base‘𝑆)) ∧ 𝑛 ∈ ((Base‘𝑆) ∖ {𝑣})) → ∃𝑒 ∈ ran ( I ↾ 𝑃){𝑣, 𝑛} ⊆ 𝑒)
28	11, 21, 26, 27	syl21anc 843	. . . . . . . 8 ⊢ (((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) ∧ 𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣})) → ∃𝑒 ∈ ran ( I ↾ 𝑃){𝑣, 𝑛} ⊆ 𝑒)
29		edgval 29137	. . . . . . . . . . 11 ⊢ (Edg‘𝐺) = ran (iEdg‘𝐺)
30	3	fveq2i 6831	. . . . . . . . . . . . 13 ⊢ (iEdg‘𝐺) = (iEdg‘(𝑆 sSet ⟨(.ef‘ndx), ( I ↾ 𝑃)⟩))
31	13, 2, 4, 16	setsiedg 29124	. . . . . . . . . . . . 13 ⊢ (𝜑 → (iEdg‘(𝑆 sSet ⟨(.ef‘ndx), ( I ↾ 𝑃)⟩)) = ( I ↾ 𝑃))
32	30, 31	eqtrid 2786	. . . . . . . . . . . 12 ⊢ (𝜑 → (iEdg‘𝐺) = ( I ↾ 𝑃))
33	32	rneqd 5881	. . . . . . . . . . 11 ⊢ (𝜑 → ran (iEdg‘𝐺) = ran ( I ↾ 𝑃))
34	29, 33	eqtrid 2786	. . . . . . . . . 10 ⊢ (𝜑 → (Edg‘𝐺) = ran ( I ↾ 𝑃))
35	34	rexeqdv 3298	. . . . . . . . 9 ⊢ (𝜑 → (∃𝑒 ∈ (Edg‘𝐺){𝑣, 𝑛} ⊆ 𝑒 ↔ ∃𝑒 ∈ ran ( I ↾ 𝑃){𝑣, 𝑛} ⊆ 𝑒))
36	35	ad2antrr 732	. . . . . . . 8 ⊢ (((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) ∧ 𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣})) → (∃𝑒 ∈ (Edg‘𝐺){𝑣, 𝑛} ⊆ 𝑒 ↔ ∃𝑒 ∈ ran ( I ↾ 𝑃){𝑣, 𝑛} ⊆ 𝑒))
37	28, 36	mpbird 258	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) ∧ 𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣})) → ∃𝑒 ∈ (Edg‘𝐺){𝑣, 𝑛} ⊆ 𝑒)
38		eqid 2739	. . . . . . . 8 ⊢ (Vtx‘𝐺) = (Vtx‘𝐺)
39		eqid 2739	. . . . . . . 8 ⊢ (Edg‘𝐺) = (Edg‘𝐺)
40	38, 39	nbgrel 29428	. . . . . . 7 ⊢ (𝑛 ∈ (𝐺 NeighbVtx 𝑣) ↔ ((𝑛 ∈ (Vtx‘𝐺) ∧ 𝑣 ∈ (Vtx‘𝐺)) ∧ 𝑛 ≠ 𝑣 ∧ ∃𝑒 ∈ (Edg‘𝐺){𝑣, 𝑛} ⊆ 𝑒))
41	8, 10, 37, 40	syl3anbrc 1350	. . . . . 6 ⊢ (((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) ∧ 𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣})) → 𝑛 ∈ (𝐺 NeighbVtx 𝑣))
42	41	ralrimiva 3131	. . . . 5 ⊢ ((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) → ∀𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣})𝑛 ∈ (𝐺 NeighbVtx 𝑣))
43	38	uvtxel 29476	. . . . 5 ⊢ (𝑣 ∈ (UnivVtx‘𝐺) ↔ (𝑣 ∈ (Vtx‘𝐺) ∧ ∀𝑛 ∈ ((Vtx‘𝐺) ∖ {𝑣})𝑛 ∈ (𝐺 NeighbVtx 𝑣)))
44	6, 42, 43	sylanbrc 589	. . . 4 ⊢ ((𝜑 ∧ 𝑣 ∈ (Vtx‘𝐺)) → 𝑣 ∈ (UnivVtx‘𝐺))
45	44	ralrimiva 3131	. . 3 ⊢ (𝜑 → ∀𝑣 ∈ (Vtx‘𝐺)𝑣 ∈ (UnivVtx‘𝐺))
46	5	elexd 3454	. . . 4 ⊢ (𝜑 → 𝐺 ∈ V)
47	38	iscplgr 29503	. . . 4 ⊢ (𝐺 ∈ V → (𝐺 ∈ ComplGraph ↔ ∀𝑣 ∈ (Vtx‘𝐺)𝑣 ∈ (UnivVtx‘𝐺)))
48	46, 47	syl 17	. . 3 ⊢ (𝜑 → (𝐺 ∈ ComplGraph ↔ ∀𝑣 ∈ (Vtx‘𝐺)𝑣 ∈ (UnivVtx‘𝐺)))
49	45, 48	mpbird 258	. 2 ⊢ (𝜑 → 𝐺 ∈ ComplGraph)
50		iscusgr 29506	. 2 ⊢ (𝐺 ∈ ComplUSGraph ↔ (𝐺 ∈ USGraph ∧ 𝐺 ∈ ComplGraph))
51	5, 49, 50	sylanbrc 589	1 ⊢ (𝜑 → 𝐺 ∈ ComplUSGraph)

Syntax hints:   → wi 4   ↔ wb 207   ∧ wa 396   = wceq 1547   ∈ wcel 2119   ≠ wne 2934  ∀wral 3053  ∃wrex 3063  {crab 3391  Vcvv 3431   ∖ cdif 3880   ⊆ wss 3883  𝒫 cpw 4530  {csn 4556  {cpr 4558  ⟨cop 4562   class class class wbr 5073   I cid 5513  dom cdm 5619  ran crn 5620   ↾ cres 5621  ‘cfv 6486  (class class class)co 7357  2c2 12228  ♯chash 14284   Struct cstr 17108   sSet csts 17125  ndxcnx 17155  Basecbs 17171  .efcedgf 29076  Vtxcvtx 29084  iEdgciedg 29085  Edgcedg 29135  USGraphcusgr 29237   NeighbVtx cnbgr 29420  UnivVtxcuvtx 29473  ComplGraphccplgr 29497  ComplUSGraphccusgr 29498

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 1974  ax-7 2015  ax-8 2121  ax-9 2129  ax-10 2152  ax-11 2168  ax-12 2189  ax-ext 2711  ax-sep 5219  ax-nul 5229  ax-pow 5295  ax-pr 5363  ax-un 7679  ax-cnex 11086  ax-resscn 11087  ax-1cn 11088  ax-icn 11089  ax-addcl 11090  ax-addrcl 11091  ax-mulcl 11092  ax-mulrcl 11093  ax-mulcom 11094  ax-addass 11095  ax-mulass 11096  ax-distr 11097  ax-i2m1 11098  ax-1ne0 11099  ax-1rid 11100  ax-rnegex 11101  ax-rrecex 11102  ax-cnre 11103  ax-pre-lttri 11104  ax-pre-lttrn 11105  ax-pre-ltadd 11106  ax-pre-mulgt0 11107

This theorem depends on definitions:  df-bi 208  df-an 397  df-or 854  df-3or 1093  df-3an 1094  df-tru 1550  df-fal 1560  df-ex 1787  df-nf 1791  df-sb 2074  df-mo 2543  df-eu 2573  df-clab 2718  df-cleq 2731  df-clel 2814  df-nfc 2888  df-ne 2935  df-nel 3039  df-ral 3054  df-rex 3064  df-reu 3345  df-rab 3392  df-v 3433  df-sbc 3724  df-csb 3832  df-dif 3886  df-un 3888  df-in 3890  df-ss 3900  df-pss 3903  df-nul 4263  df-if 4456  df-pw 4532  df-sn 4557  df-pr 4559  df-op 4563  df-uni 4840  df-int 4879  df-iun 4924  df-br 5074  df-opab 5136  df-mpt 5155  df-tr 5181  df-id 5514  df-eprel 5519  df-po 5527  df-so 5528  df-fr 5572  df-we 5574  df-xp 5625  df-rel 5626  df-cnv 5627  df-co 5628  df-dm 5629  df-rn 5630  df-res 5631  df-ima 5632  df-pred 6253  df-ord 6314  df-on 6315  df-lim 6316  df-suc 6317  df-iota 6442  df-fun 6488  df-fn 6489  df-f 6490  df-f1 6491  df-fo 6492  df-f1o 6493  df-fv 6494  df-riota 7314  df-ov 7360  df-oprab 7361  df-mpo 7362  df-om 7808  df-1st 7932  df-2nd 7933  df-frecs 8222  df-wrecs 8253  df-recs 8302  df-rdg 8340  df-1o 8396  df-oadd 8400  df-er 8634  df-en 8885  df-dom 8886  df-sdom 8887  df-fin 8888  df-dju 9817  df-card 9855  df-pnf 11173  df-mnf 11174  df-xr 11175  df-ltxr 11176  df-le 11177  df-sub 11371  df-neg 11372  df-nn 12167  df-2 12236  df-3 12237  df-4 12238  df-5 12239  df-6 12240  df-7 12241  df-8 12242  df-9 12243  df-n0 12430  df-xnn0 12503  df-z 12517  df-dec 12637  df-uz 12781  df-fz 13454  df-hash 14285  df-struct 17109  df-sets 17126  df-slot 17144  df-ndx 17156  df-base 17172  df-edgf 29077  df-vtx 29086  df-iedg 29087  df-edg 29136  df-usgr 29239  df-nbgr 29421  df-uvtx 29474  df-cplgr 29499  df-cusgr 29500

This theorem is referenced by:  cffldtocusgr  29535