Theorem nbcusgra 24286

Description: In a complete (undirected simple) graph, each vertex has all other vertices as neighbors. (Contributed by Alexander van der Vekens, 12-Oct-2017.)

Assertion

Ref	Expression
nbcusgra	|- ( ( V ComplUSGrph E /\ N e. V ) -> ( <. V , E >. Neighbors N ) = ( V \ { N } ) )

Proof of Theorem nbcusgra

Dummy variables k n x are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		cusisusgra 24281	. . 3 |- ( V ComplUSGrph E -> V USGrph E )
2		nbusgra 24251	. . . . . . 7 |- ( V USGrph E -> ( <. V , E >. Neighbors N ) = { n e. V | { N , n } e. ran E } )
3	2	adantr 465	. . . . . 6 |- ( ( V USGrph E /\ V ComplUSGrph E ) -> ( <. V , E >. Neighbors N ) = { n e. V | { N , n } e. ran E } )
4	3	adantr 465	. . . . 5 |- ( ( ( V USGrph E /\ V ComplUSGrph E ) /\ N e. V ) -> ( <. V , E >. Neighbors N ) = { n e. V | { N , n } e. ran E } )
5		usgrav 24161	. . . . . . . . . 10 |- ( V USGrph E -> ( V e. _V /\ E e. _V ) )
6		iscusgra 24279	. . . . . . . . . 10 |- ( ( V e. _V /\ E e. _V ) -> ( V ComplUSGrph E <-> ( V USGrph E /\ A. x e. V A. k e. ( V \ { x } ) { k , x } e. ran E ) ) )
7	5, 6	syl 16	. . . . . . . . 9 |- ( V USGrph E -> ( V ComplUSGrph E <-> ( V USGrph E /\ A. x e. V A. k e. ( V \ { x } ) { k , x } e. ran E ) ) )
8	7	biimpa 484	. . . . . . . 8 |- ( ( V USGrph E /\ V ComplUSGrph E ) -> ( V USGrph E /\ A. x e. V A. k e. ( V \ { x } ) { k , x } e. ran E ) )
9		df-ral 2822	. . . . . . . . . 10 |- ( A. x e. V A. k e. ( V \ { x } ) { k , x } e. ran E <-> A. x ( x e. V -> A. k e. ( V \ { x } ) { k , x } e. ran E ) )
10		preq2 4113	. . . . . . . . . . . . . . 15 |- ( n = x -> { N , n } = { N , x } )
11	10	eleq1d 2536	. . . . . . . . . . . . . 14 |- ( n = x -> ( { N , n } e. ran E <-> { N , x } e. ran E ) )
12	11	elrab 3266	. . . . . . . . . . . . 13 |- ( x e. { n e. V | { N , n } e. ran E } <-> ( x e. V /\ { N , x } e. ran E ) )
13		pm2.24 109	. . . . . . . . . . . . . . . . . . 19 |- ( x e. V -> ( -. x e. V -> x e. ( V \ { N } ) ) )
14	13	adantr 465	. . . . . . . . . . . . . . . . . 18 |- ( ( x e. V /\ { N , x } e. ran E ) -> ( -. x e. V -> x e. ( V \ { N } ) ) )
15	14	com12 31	. . . . . . . . . . . . . . . . 17 |- ( -. x e. V -> ( ( x e. V /\ { N , x } e. ran E ) -> x e. ( V \ { N } ) ) )
16		eldif 3491	. . . . . . . . . . . . . . . . . . 19 |- ( x e. ( V \ { N } ) <-> ( x e. V /\ -. x e. { N } ) )
17		pm2.24 109	. . . . . . . . . . . . . . . . . . . 20 |- ( x e. V -> ( -. x e. V -> ( x e. V /\ { N , x } e. ran E ) ) )
18	17	adantr 465	. . . . . . . . . . . . . . . . . . 19 |- ( ( x e. V /\ -. x e. { N } ) -> ( -. x e. V -> ( x e. V /\ { N , x } e. ran E ) ) )
19	16, 18	sylbi 195	. . . . . . . . . . . . . . . . . 18 |- ( x e. ( V \ { N } ) -> ( -. x e. V -> ( x e. V /\ { N , x } e. ran E ) ) )
20	19	com12 31	. . . . . . . . . . . . . . . . 17 |- ( -. x e. V -> ( x e. ( V \ { N } ) -> ( x e. V /\ { N , x } e. ran E ) ) )
21	15, 20	impbid 191	. . . . . . . . . . . . . . . 16 |- ( -. x e. V -> ( ( x e. V /\ { N , x } e. ran E ) <-> x e. ( V \ { N } ) ) )
22	21	a1d 25	. . . . . . . . . . . . . . 15 |- ( -. x e. V -> ( ( V USGrph E /\ N e. V ) -> ( ( x e. V /\ { N , x } e. ran E ) <-> x e. ( V \ { N } ) ) ) )
23		usgraedgrn 24204	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( ( V USGrph E /\ { N , x } e. ran E ) -> N =/= x )
24		elsni 4058	. . . . . . . . . . . . . . . . . . . . . . . . 25 |- ( x e. { N } -> x = N )
25		eqcom 2476	. . . . . . . . . . . . . . . . . . . . . . . . 25 |- ( N = x <-> x = N )
26	24, 25	sylibr 212	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( x e. { N } -> N = x )
27	26	necon3ai 2695	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( N =/= x -> -. x e. { N } )
28	23, 27	syl 16	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( V USGrph E /\ { N , x } e. ran E ) -> -. x e. { N } )
29	28	ex 434	. . . . . . . . . . . . . . . . . . . . 21 |- ( V USGrph E -> ( { N , x } e. ran E -> -. x e. { N } ) )
30	29	ad2antrl 727	. . . . . . . . . . . . . . . . . . . 20 |- ( ( A. k e. ( V \ { x } ) { k , x } e. ran E /\ ( V USGrph E /\ N e. V ) ) -> ( { N , x } e. ran E -> -. x e. { N } ) )
31	30	adantr 465	. . . . . . . . . . . . . . . . . . 19 |- ( ( ( A. k e. ( V \ { x } ) { k , x } e. ran E /\ ( V USGrph E /\ N e. V ) ) /\ x e. V ) -> ( { N , x } e. ran E -> -. x e. { N } ) )
32		simpr 461	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 |- ( ( -. x e. { N } /\ N e. V ) -> N e. V )
33		elsncg 4056	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 |- ( N e. V -> ( N e. { x } <-> N = x ) )
34		elsn 4047	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 |- ( x e. { N } <-> x = N )
35	34	biimpri 206	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 |- ( x = N -> x e. { N } )
36	25, 35	sylbi 195	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 |- ( N = x -> x e. { N } )
37	33, 36	syl6bi 228	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 |- ( N e. V -> ( N e. { x } -> x e. { N } ) )
38	37	con3d 133	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 |- ( N e. V -> ( -. x e. { N } -> -. N e. { x } ) )
39	38	impcom 430	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 |- ( ( -. x e. { N } /\ N e. V ) -> -. N e. { x } )
40	32, 39	eldifd 3492	. . . . . . . . . . . . . . . . . . . . . . . . . 26 |- ( ( -. x e. { N } /\ N e. V ) -> N e. ( V \ { x } ) )
41		preq1 4112	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 |- ( k = N -> { k , x } = { N , x } )
42	41	eleq1d 2536	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 |- ( k = N -> ( { k , x } e. ran E <-> { N , x } e. ran E ) )
43	42	rspcva 3217	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 |- ( ( N e. ( V \ { x } ) /\ A. k e. ( V \ { x } ) { k , x } e. ran E ) -> { N , x } e. ran E )
44		ax-1 6	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 |- ( { N , x } e. ran E -> ( V USGrph E -> { N , x } e. ran E ) )
45	44	a1d 25	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 |- ( { N , x } e. ran E -> ( x e. V -> ( V USGrph E -> { N , x } e. ran E ) ) )
46	43, 45	syl 16	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 |- ( ( N e. ( V \ { x } ) /\ A. k e. ( V \ { x } ) { k , x } e. ran E ) -> ( x e. V -> ( V USGrph E -> { N , x } e. ran E ) ) )
47	46	ex 434	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 |- ( N e. ( V \ { x } ) -> ( A. k e. ( V \ { x } ) { k , x } e. ran E -> ( x e. V -> ( V USGrph E -> { N , x } e. ran E ) ) ) )
48	47	com24 87	. . . . . . . . . . . . . . . . . . . . . . . . . 26 |- ( N e. ( V \ { x } ) -> ( V USGrph E -> ( x e. V -> ( A. k e. ( V \ { x } ) { k , x } e. ran E -> { N , x } e. ran E ) ) ) )
49	40, 48	syl 16	. . . . . . . . . . . . . . . . . . . . . . . . 25 |- ( ( -. x e. { N } /\ N e. V ) -> ( V USGrph E -> ( x e. V -> ( A. k e. ( V \ { x } ) { k , x } e. ran E -> { N , x } e. ran E ) ) ) )
50	49	ex 434	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( -. x e. { N } -> ( N e. V -> ( V USGrph E -> ( x e. V -> ( A. k e. ( V \ { x } ) { k , x } e. ran E -> { N , x } e. ran E ) ) ) ) )
51	50	com13 80	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( V USGrph E -> ( N e. V -> ( -. x e. { N } -> ( x e. V -> ( A. k e. ( V \ { x } ) { k , x } e. ran E -> { N , x } e. ran E ) ) ) ) )
52	51	imp 429	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( V USGrph E /\ N e. V ) -> ( -. x e. { N } -> ( x e. V -> ( A. k e. ( V \ { x } ) { k , x } e. ran E -> { N , x } e. ran E ) ) ) )
53	52	com12 31	. . . . . . . . . . . . . . . . . . . . 21 |- ( -. x e. { N } -> ( ( V USGrph E /\ N e. V ) -> ( x e. V -> ( A. k e. ( V \ { x } ) { k , x } e. ran E -> { N , x } e. ran E ) ) ) )
54	53	com14 88	. . . . . . . . . . . . . . . . . . . 20 |- ( A. k e. ( V \ { x } ) { k , x } e. ran E -> ( ( V USGrph E /\ N e. V ) -> ( x e. V -> ( -. x e. { N } -> { N , x } e. ran E ) ) ) )
55	54	imp31 432	. . . . . . . . . . . . . . . . . . 19 |- ( ( ( A. k e. ( V \ { x } ) { k , x } e. ran E /\ ( V USGrph E /\ N e. V ) ) /\ x e. V ) -> ( -. x e. { N } -> { N , x } e. ran E ) )
56	31, 55	impbid 191	. . . . . . . . . . . . . . . . . 18 |- ( ( ( A. k e. ( V \ { x } ) { k , x } e. ran E /\ ( V USGrph E /\ N e. V ) ) /\ x e. V ) -> ( { N , x } e. ran E <-> -. x e. { N } ) )
57	56	pm5.32da 641	. . . . . . . . . . . . . . . . 17 |- ( ( A. k e. ( V \ { x } ) { k , x } e. ran E /\ ( V USGrph E /\ N e. V ) ) -> ( ( x e. V /\ { N , x } e. ran E ) <-> ( x e. V /\ -. x e. { N } ) ) )
58	57, 16	syl6bbr 263	. . . . . . . . . . . . . . . 16 |- ( ( A. k e. ( V \ { x } ) { k , x } e. ran E /\ ( V USGrph E /\ N e. V ) ) -> ( ( x e. V /\ { N , x } e. ran E ) <-> x e. ( V \ { N } ) ) )
59	58	ex 434	. . . . . . . . . . . . . . 15 |- ( A. k e. ( V \ { x } ) { k , x } e. ran E -> ( ( V USGrph E /\ N e. V ) -> ( ( x e. V /\ { N , x } e. ran E ) <-> x e. ( V \ { N } ) ) ) )
60	22, 59	ja 161	. . . . . . . . . . . . . 14 |- ( ( x e. V -> A. k e. ( V \ { x } ) { k , x } e. ran E ) -> ( ( V USGrph E /\ N e. V ) -> ( ( x e. V /\ { N , x } e. ran E ) <-> x e. ( V \ { N } ) ) ) )
61	60	impcom 430	. . . . . . . . . . . . 13 |- ( ( ( V USGrph E /\ N e. V ) /\ ( x e. V -> A. k e. ( V \ { x } ) { k , x } e. ran E ) ) -> ( ( x e. V /\ { N , x } e. ran E ) <-> x e. ( V \ { N } ) ) )
62	12, 61	syl5bb 257	. . . . . . . . . . . 12 |- ( ( ( V USGrph E /\ N e. V ) /\ ( x e. V -> A. k e. ( V \ { x } ) { k , x } e. ran E ) ) -> ( x e. { n e. V | { N , n } e. ran E } <-> x e. ( V \ { N } ) ) )
63	62	ex 434	. . . . . . . . . . 11 |- ( ( V USGrph E /\ N e. V ) -> ( ( x e. V -> A. k e. ( V \ { x } ) { k , x } e. ran E ) -> ( x e. { n e. V | { N , n } e. ran E } <-> x e. ( V \ { N } ) ) ) )
64	63	alimdv 1685	. . . . . . . . . 10 |- ( ( V USGrph E /\ N e. V ) -> ( A. x ( x e. V -> A. k e. ( V \ { x } ) { k , x } e. ran E ) -> A. x ( x e. { n e. V | { N , n } e. ran E } <-> x e. ( V \ { N } ) ) ) )
65	9, 64	syl5bi 217	. . . . . . . . 9 |- ( ( V USGrph E /\ N e. V ) -> ( A. x e. V A. k e. ( V \ { x } ) { k , x } e. ran E -> A. x ( x e. { n e. V | { N , n } e. ran E } <-> x e. ( V \ { N } ) ) ) )
66	65	impancom 440	. . . . . . . 8 |- ( ( V USGrph E /\ A. x e. V A. k e. ( V \ { x } ) { k , x } e. ran E ) -> ( N e. V -> A. x ( x e. { n e. V | { N , n } e. ran E } <-> x e. ( V \ { N } ) ) ) )
67	8, 66	syl 16	. . . . . . 7 |- ( ( V USGrph E /\ V ComplUSGrph E ) -> ( N e. V -> A. x ( x e. { n e. V | { N , n } e. ran E } <-> x e. ( V \ { N } ) ) ) )
68	67	imp 429	. . . . . 6 |- ( ( ( V USGrph E /\ V ComplUSGrph E ) /\ N e. V ) -> A. x ( x e. { n e. V | { N , n } e. ran E } <-> x e. ( V \ { N } ) ) )
69		dfcleq 2460	. . . . . 6 |- ( { n e. V | { N , n } e. ran E } = ( V \ { N } ) <-> A. x ( x e. { n e. V | { N , n } e. ran E } <-> x e. ( V \ { N } ) ) )
70	68, 69	sylibr 212	. . . . 5 |- ( ( ( V USGrph E /\ V ComplUSGrph E ) /\ N e. V ) -> { n e. V | { N , n } e. ran E } = ( V \ { N } ) )
71	4, 70	eqtrd 2508	. . . 4 |- ( ( ( V USGrph E /\ V ComplUSGrph E ) /\ N e. V ) -> ( <. V , E >. Neighbors N ) = ( V \ { N } ) )
72	71	ex 434	. . 3 |- ( ( V USGrph E /\ V ComplUSGrph E ) -> ( N e. V -> ( <. V , E >. Neighbors N ) = ( V \ { N } ) ) )
73	1, 72	mpancom 669	. 2 |- ( V ComplUSGrph E -> ( N e. V -> ( <. V , E >. Neighbors N ) = ( V \ { N } ) ) )
74	73	imp 429	1 |- ( ( V ComplUSGrph E /\ N e. V ) -> ( <. V , E >. Neighbors N ) = ( V \ { N } ) )

Syntax hints:   -. wn 3   -> wi 4   <-> wb 184   /\ wa 369   A.wal 1377   = wceq 1379   e. wcel 1767   =/= wne 2662   A.wral 2817   {crab 2821   _Vcvv 3118   \ cdif 3478   {csn 4033   {cpr 4035   <.cop 4039   class class class wbr 4453   ran crn 5006  (class class class)co 6295   USGrph cusg 24153   Neighbors cnbgra 24240   ComplUSGrph ccusgra 24241

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1601  ax-4 1612  ax-5 1680  ax-6 1719  ax-7 1739  ax-8 1769  ax-9 1771  ax-10 1786  ax-11 1791  ax-12 1803  ax-13 1968  ax-ext 2445  ax-rep 4564  ax-sep 4574  ax-nul 4582  ax-pow 4631  ax-pr 4692  ax-un 6587  ax-cnex 9560  ax-resscn 9561  ax-1cn 9562  ax-icn 9563  ax-addcl 9564  ax-addrcl 9565  ax-mulcl 9566  ax-mulrcl 9567  ax-mulcom 9568  ax-addass 9569  ax-mulass 9570  ax-distr 9571  ax-i2m1 9572  ax-1ne0 9573  ax-1rid 9574  ax-rnegex 9575  ax-rrecex 9576  ax-cnre 9577  ax-pre-lttri 9578  ax-pre-lttrn 9579  ax-pre-ltadd 9580  ax-pre-mulgt0 9581

This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 974  df-3an 975  df-tru 1382  df-ex 1597  df-nf 1600  df-sb 1712  df-eu 2279  df-mo 2280  df-clab 2453  df-cleq 2459  df-clel 2462  df-nfc 2617  df-ne 2664  df-nel 2665  df-ral 2822  df-rex 2823  df-reu 2824  df-rmo 2825  df-rab 2826  df-v 3120  df-sbc 3337  df-csb 3441  df-dif 3484  df-un 3486  df-in 3488  df-ss 3495  df-pss 3497  df-nul 3791  df-if 3946  df-pw 4018  df-sn 4034  df-pr 4036  df-tp 4038  df-op 4040  df-uni 4252  df-int 4289  df-iun 4333  df-br 4454  df-opab 4512  df-mpt 4513  df-tr 4547  df-eprel 4797  df-id 4801  df-po 4806  df-so 4807  df-fr 4844  df-we 4846  df-ord 4887  df-on 4888  df-lim 4889  df-suc 4890  df-xp 5011  df-rel 5012  df-cnv 5013  df-co 5014  df-dm 5015  df-rn 5016  df-res 5017  df-ima 5018  df-iota 5557  df-fun 5596  df-fn 5597  df-f 5598  df-f1 5599  df-fo 5600  df-f1o 5601  df-fv 5602  df-riota 6256  df-ov 6298  df-oprab 6299  df-mpt2 6300  df-om 6696  df-1st 6795  df-2nd 6796  df-recs 7054  df-rdg 7088  df-1o 7142  df-oadd 7146  df-er 7323  df-en 7529  df-dom 7530  df-sdom 7531  df-fin 7532  df-card 8332  df-cda 8560  df-pnf 9642  df-mnf 9643  df-xr 9644  df-ltxr 9645  df-le 9646  df-sub 9819  df-neg 9820  df-nn 10549  df-2 10606  df-n0 10808  df-z 10877  df-uz 11095  df-fz 11685  df-hash 12386  df-usgra 24156  df-nbgra 24243  df-cusgra 24244

This theorem is referenced by:  cusgrasizeindslem3  24298  cusgraisrusgra  24761  vdcusgra  32149