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

Theorem nb3gr2nb 26482
Description: If the neighbors of two vertices in a graph with three elements are an unordered pair of the other vertices, the neighbors of all three vertices are an unordered pair of the other vertices. (Contributed by Alexander van der Vekens, 18-Oct-2017.) (Revised by AV, 28-Oct-2020.)
Assertion
Ref Expression
nb3gr2nb (((𝐴𝑋𝐵𝑌𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → (((𝐺 NeighbVtx 𝐴) = {𝐵, 𝐶} ∧ (𝐺 NeighbVtx 𝐵) = {𝐴, 𝐶}) ↔ ((𝐺 NeighbVtx 𝐴) = {𝐵, 𝐶} ∧ (𝐺 NeighbVtx 𝐵) = {𝐴, 𝐶} ∧ (𝐺 NeighbVtx 𝐶) = {𝐴, 𝐵})))

Proof of Theorem nb3gr2nb
StepHypRef Expression
1 prcom 4409 . . . . . . . . 9 {𝐴, 𝐶} = {𝐶, 𝐴}
21eleq1i 2828 . . . . . . . 8 ({𝐴, 𝐶} ∈ (Edg‘𝐺) ↔ {𝐶, 𝐴} ∈ (Edg‘𝐺))
32biimpi 206 . . . . . . 7 ({𝐴, 𝐶} ∈ (Edg‘𝐺) → {𝐶, 𝐴} ∈ (Edg‘𝐺))
43adantl 473 . . . . . 6 (({𝐴, 𝐵} ∈ (Edg‘𝐺) ∧ {𝐴, 𝐶} ∈ (Edg‘𝐺)) → {𝐶, 𝐴} ∈ (Edg‘𝐺))
5 prcom 4409 . . . . . . . . 9 {𝐵, 𝐶} = {𝐶, 𝐵}
65eleq1i 2828 . . . . . . . 8 ({𝐵, 𝐶} ∈ (Edg‘𝐺) ↔ {𝐶, 𝐵} ∈ (Edg‘𝐺))
76biimpi 206 . . . . . . 7 ({𝐵, 𝐶} ∈ (Edg‘𝐺) → {𝐶, 𝐵} ∈ (Edg‘𝐺))
87adantl 473 . . . . . 6 (({𝐵, 𝐴} ∈ (Edg‘𝐺) ∧ {𝐵, 𝐶} ∈ (Edg‘𝐺)) → {𝐶, 𝐵} ∈ (Edg‘𝐺))
94, 8anim12i 591 . . . . 5 ((({𝐴, 𝐵} ∈ (Edg‘𝐺) ∧ {𝐴, 𝐶} ∈ (Edg‘𝐺)) ∧ ({𝐵, 𝐴} ∈ (Edg‘𝐺) ∧ {𝐵, 𝐶} ∈ (Edg‘𝐺))) → ({𝐶, 𝐴} ∈ (Edg‘𝐺) ∧ {𝐶, 𝐵} ∈ (Edg‘𝐺)))
109a1i 11 . . . 4 (((𝐴𝑋𝐵𝑌𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → ((({𝐴, 𝐵} ∈ (Edg‘𝐺) ∧ {𝐴, 𝐶} ∈ (Edg‘𝐺)) ∧ ({𝐵, 𝐴} ∈ (Edg‘𝐺) ∧ {𝐵, 𝐶} ∈ (Edg‘𝐺))) → ({𝐶, 𝐴} ∈ (Edg‘𝐺) ∧ {𝐶, 𝐵} ∈ (Edg‘𝐺))))
11 eqid 2758 . . . . . 6 (Vtx‘𝐺) = (Vtx‘𝐺)
12 eqid 2758 . . . . . 6 (Edg‘𝐺) = (Edg‘𝐺)
13 simprr 813 . . . . . 6 (((𝐴𝑋𝐵𝑌𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → 𝐺 ∈ USGraph)
14 simprl 811 . . . . . 6 (((𝐴𝑋𝐵𝑌𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → (Vtx‘𝐺) = {𝐴, 𝐵, 𝐶})
15 simpl 474 . . . . . 6 (((𝐴𝑋𝐵𝑌𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → (𝐴𝑋𝐵𝑌𝐶𝑍))
1611, 12, 13, 14, 15nb3grprlem1 26478 . . . . 5 (((𝐴𝑋𝐵𝑌𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → ((𝐺 NeighbVtx 𝐴) = {𝐵, 𝐶} ↔ ({𝐴, 𝐵} ∈ (Edg‘𝐺) ∧ {𝐴, 𝐶} ∈ (Edg‘𝐺))))
17 3ancoma 1084 . . . . . . 7 ((𝐴𝑋𝐵𝑌𝐶𝑍) ↔ (𝐵𝑌𝐴𝑋𝐶𝑍))
1817biimpi 206 . . . . . 6 ((𝐴𝑋𝐵𝑌𝐶𝑍) → (𝐵𝑌𝐴𝑋𝐶𝑍))
19 tpcoma 4427 . . . . . . . . 9 {𝐴, 𝐵, 𝐶} = {𝐵, 𝐴, 𝐶}
2019eqeq2i 2770 . . . . . . . 8 ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ↔ (Vtx‘𝐺) = {𝐵, 𝐴, 𝐶})
2120biimpi 206 . . . . . . 7 ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} → (Vtx‘𝐺) = {𝐵, 𝐴, 𝐶})
2221anim1i 593 . . . . . 6 (((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph) → ((Vtx‘𝐺) = {𝐵, 𝐴, 𝐶} ∧ 𝐺 ∈ USGraph))
23 simprr 813 . . . . . . 7 (((𝐵𝑌𝐴𝑋𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐵, 𝐴, 𝐶} ∧ 𝐺 ∈ USGraph)) → 𝐺 ∈ USGraph)
24 simprl 811 . . . . . . 7 (((𝐵𝑌𝐴𝑋𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐵, 𝐴, 𝐶} ∧ 𝐺 ∈ USGraph)) → (Vtx‘𝐺) = {𝐵, 𝐴, 𝐶})
25 simpl 474 . . . . . . 7 (((𝐵𝑌𝐴𝑋𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐵, 𝐴, 𝐶} ∧ 𝐺 ∈ USGraph)) → (𝐵𝑌𝐴𝑋𝐶𝑍))
2611, 12, 23, 24, 25nb3grprlem1 26478 . . . . . 6 (((𝐵𝑌𝐴𝑋𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐵, 𝐴, 𝐶} ∧ 𝐺 ∈ USGraph)) → ((𝐺 NeighbVtx 𝐵) = {𝐴, 𝐶} ↔ ({𝐵, 𝐴} ∈ (Edg‘𝐺) ∧ {𝐵, 𝐶} ∈ (Edg‘𝐺))))
2718, 22, 26syl2an 495 . . . . 5 (((𝐴𝑋𝐵𝑌𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → ((𝐺 NeighbVtx 𝐵) = {𝐴, 𝐶} ↔ ({𝐵, 𝐴} ∈ (Edg‘𝐺) ∧ {𝐵, 𝐶} ∈ (Edg‘𝐺))))
2816, 27anbi12d 749 . . . 4 (((𝐴𝑋𝐵𝑌𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → (((𝐺 NeighbVtx 𝐴) = {𝐵, 𝐶} ∧ (𝐺 NeighbVtx 𝐵) = {𝐴, 𝐶}) ↔ (({𝐴, 𝐵} ∈ (Edg‘𝐺) ∧ {𝐴, 𝐶} ∈ (Edg‘𝐺)) ∧ ({𝐵, 𝐴} ∈ (Edg‘𝐺) ∧ {𝐵, 𝐶} ∈ (Edg‘𝐺)))))
29 3anrot 1087 . . . . . 6 ((𝐶𝑍𝐴𝑋𝐵𝑌) ↔ (𝐴𝑋𝐵𝑌𝐶𝑍))
3029biimpri 218 . . . . 5 ((𝐴𝑋𝐵𝑌𝐶𝑍) → (𝐶𝑍𝐴𝑋𝐵𝑌))
31 tprot 4426 . . . . . . . . 9 {𝐶, 𝐴, 𝐵} = {𝐴, 𝐵, 𝐶}
3231eqcomi 2767 . . . . . . . 8 {𝐴, 𝐵, 𝐶} = {𝐶, 𝐴, 𝐵}
3332eqeq2i 2770 . . . . . . 7 ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ↔ (Vtx‘𝐺) = {𝐶, 𝐴, 𝐵})
3433anbi1i 733 . . . . . 6 (((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph) ↔ ((Vtx‘𝐺) = {𝐶, 𝐴, 𝐵} ∧ 𝐺 ∈ USGraph))
3534biimpi 206 . . . . 5 (((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph) → ((Vtx‘𝐺) = {𝐶, 𝐴, 𝐵} ∧ 𝐺 ∈ USGraph))
36 simprr 813 . . . . . 6 (((𝐶𝑍𝐴𝑋𝐵𝑌) ∧ ((Vtx‘𝐺) = {𝐶, 𝐴, 𝐵} ∧ 𝐺 ∈ USGraph)) → 𝐺 ∈ USGraph)
37 simprl 811 . . . . . 6 (((𝐶𝑍𝐴𝑋𝐵𝑌) ∧ ((Vtx‘𝐺) = {𝐶, 𝐴, 𝐵} ∧ 𝐺 ∈ USGraph)) → (Vtx‘𝐺) = {𝐶, 𝐴, 𝐵})
38 simpl 474 . . . . . 6 (((𝐶𝑍𝐴𝑋𝐵𝑌) ∧ ((Vtx‘𝐺) = {𝐶, 𝐴, 𝐵} ∧ 𝐺 ∈ USGraph)) → (𝐶𝑍𝐴𝑋𝐵𝑌))
3911, 12, 36, 37, 38nb3grprlem1 26478 . . . . 5 (((𝐶𝑍𝐴𝑋𝐵𝑌) ∧ ((Vtx‘𝐺) = {𝐶, 𝐴, 𝐵} ∧ 𝐺 ∈ USGraph)) → ((𝐺 NeighbVtx 𝐶) = {𝐴, 𝐵} ↔ ({𝐶, 𝐴} ∈ (Edg‘𝐺) ∧ {𝐶, 𝐵} ∈ (Edg‘𝐺))))
4030, 35, 39syl2an 495 . . . 4 (((𝐴𝑋𝐵𝑌𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → ((𝐺 NeighbVtx 𝐶) = {𝐴, 𝐵} ↔ ({𝐶, 𝐴} ∈ (Edg‘𝐺) ∧ {𝐶, 𝐵} ∈ (Edg‘𝐺))))
4110, 28, 403imtr4d 283 . . 3 (((𝐴𝑋𝐵𝑌𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → (((𝐺 NeighbVtx 𝐴) = {𝐵, 𝐶} ∧ (𝐺 NeighbVtx 𝐵) = {𝐴, 𝐶}) → (𝐺 NeighbVtx 𝐶) = {𝐴, 𝐵}))
4241pm4.71d 669 . 2 (((𝐴𝑋𝐵𝑌𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → (((𝐺 NeighbVtx 𝐴) = {𝐵, 𝐶} ∧ (𝐺 NeighbVtx 𝐵) = {𝐴, 𝐶}) ↔ (((𝐺 NeighbVtx 𝐴) = {𝐵, 𝐶} ∧ (𝐺 NeighbVtx 𝐵) = {𝐴, 𝐶}) ∧ (𝐺 NeighbVtx 𝐶) = {𝐴, 𝐵})))
43 df-3an 1074 . 2 (((𝐺 NeighbVtx 𝐴) = {𝐵, 𝐶} ∧ (𝐺 NeighbVtx 𝐵) = {𝐴, 𝐶} ∧ (𝐺 NeighbVtx 𝐶) = {𝐴, 𝐵}) ↔ (((𝐺 NeighbVtx 𝐴) = {𝐵, 𝐶} ∧ (𝐺 NeighbVtx 𝐵) = {𝐴, 𝐶}) ∧ (𝐺 NeighbVtx 𝐶) = {𝐴, 𝐵}))
4442, 43syl6bbr 278 1 (((𝐴𝑋𝐵𝑌𝐶𝑍) ∧ ((Vtx‘𝐺) = {𝐴, 𝐵, 𝐶} ∧ 𝐺 ∈ USGraph)) → (((𝐺 NeighbVtx 𝐴) = {𝐵, 𝐶} ∧ (𝐺 NeighbVtx 𝐵) = {𝐴, 𝐶}) ↔ ((𝐺 NeighbVtx 𝐴) = {𝐵, 𝐶} ∧ (𝐺 NeighbVtx 𝐵) = {𝐴, 𝐶} ∧ (𝐺 NeighbVtx 𝐶) = {𝐴, 𝐵})))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 196  wa 383  w3a 1072   = wceq 1630  wcel 2137  {cpr 4321  {ctp 4323  cfv 6047  (class class class)co 6811  Vtxcvtx 26071  Edgcedg 26136  USGraphcusgr 26241   NeighbVtx cnbgr 26421
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1869  ax-4 1884  ax-5 1986  ax-6 2052  ax-7 2088  ax-8 2139  ax-9 2146  ax-10 2166  ax-11 2181  ax-12 2194  ax-13 2389  ax-ext 2738  ax-rep 4921  ax-sep 4931  ax-nul 4939  ax-pow 4990  ax-pr 5053  ax-un 7112  ax-cnex 10182  ax-resscn 10183  ax-1cn 10184  ax-icn 10185  ax-addcl 10186  ax-addrcl 10187  ax-mulcl 10188  ax-mulrcl 10189  ax-mulcom 10190  ax-addass 10191  ax-mulass 10192  ax-distr 10193  ax-i2m1 10194  ax-1ne0 10195  ax-1rid 10196  ax-rnegex 10197  ax-rrecex 10198  ax-cnre 10199  ax-pre-lttri 10200  ax-pre-lttrn 10201  ax-pre-ltadd 10202  ax-pre-mulgt0 10203
This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3or 1073  df-3an 1074  df-tru 1633  df-fal 1636  df-ex 1852  df-nf 1857  df-sb 2045  df-eu 2609  df-mo 2610  df-clab 2745  df-cleq 2751  df-clel 2754  df-nfc 2889  df-ne 2931  df-nel 3034  df-ral 3053  df-rex 3054  df-reu 3055  df-rmo 3056  df-rab 3057  df-v 3340  df-sbc 3575  df-csb 3673  df-dif 3716  df-un 3718  df-in 3720  df-ss 3727  df-pss 3729  df-nul 4057  df-if 4229  df-pw 4302  df-sn 4320  df-pr 4322  df-tp 4324  df-op 4326  df-uni 4587  df-int 4626  df-iun 4672  df-br 4803  df-opab 4863  df-mpt 4880  df-tr 4903  df-id 5172  df-eprel 5177  df-po 5185  df-so 5186  df-fr 5223  df-we 5225  df-xp 5270  df-rel 5271  df-cnv 5272  df-co 5273  df-dm 5274  df-rn 5275  df-res 5276  df-ima 5277  df-pred 5839  df-ord 5885  df-on 5886  df-lim 5887  df-suc 5888  df-iota 6010  df-fun 6049  df-fn 6050  df-f 6051  df-f1 6052  df-fo 6053  df-f1o 6054  df-fv 6055  df-riota 6772  df-ov 6814  df-oprab 6815  df-mpt2 6816  df-om 7229  df-1st 7331  df-2nd 7332  df-wrecs 7574  df-recs 7635  df-rdg 7673  df-1o 7727  df-2o 7728  df-oadd 7731  df-er 7909  df-en 8120  df-dom 8121  df-sdom 8122  df-fin 8123  df-card 8953  df-cda 9180  df-pnf 10266  df-mnf 10267  df-xr 10268  df-ltxr 10269  df-le 10270  df-sub 10458  df-neg 10459  df-nn 11211  df-2 11269  df-n0 11483  df-xnn0 11554  df-z 11568  df-uz 11878  df-fz 12518  df-hash 13310  df-edg 26137  df-upgr 26174  df-umgr 26175  df-usgr 26243  df-nbgr 26422
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator