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

Theorem cusgrsize 27223
 Description: The size of a finite complete simple graph with 𝑛 vertices (𝑛 ∈ ℕ0) is (𝑛C2) ("𝑛 choose 2") resp. (((𝑛 − 1)∗𝑛) / 2), see definition in section I.1 of [Bollobas] p. 3 . (Contributed by Alexander van der Vekens, 11-Jan-2018.) (Revised by AV, 10-Nov-2020.)
Hypotheses
Ref Expression
cusgrsizeindb0.v 𝑉 = (Vtx‘𝐺)
cusgrsizeindb0.e 𝐸 = (Edg‘𝐺)
Assertion
Ref Expression
cusgrsize ((𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin) → (♯‘𝐸) = ((♯‘𝑉)C2))

Proof of Theorem cusgrsize
Dummy variables 𝑒 𝑓 𝑛 𝑣 𝑐 𝑤 𝑦 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 cusgrsizeindb0.e . . . . 5 𝐸 = (Edg‘𝐺)
2 edgval 26821 . . . . 5 (Edg‘𝐺) = ran (iEdg‘𝐺)
31, 2eqtri 2843 . . . 4 𝐸 = ran (iEdg‘𝐺)
43a1i 11 . . 3 ((𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin) → 𝐸 = ran (iEdg‘𝐺))
54fveq2d 6650 . 2 ((𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin) → (♯‘𝐸) = (♯‘ran (iEdg‘𝐺)))
6 cusgrsizeindb0.v . . . . 5 𝑉 = (Vtx‘𝐺)
76opeq1i 4782 . . . 4 𝑉, (iEdg‘𝐺)⟩ = ⟨(Vtx‘𝐺), (iEdg‘𝐺)⟩
8 cusgrop 27207 . . . 4 (𝐺 ∈ ComplUSGraph → ⟨(Vtx‘𝐺), (iEdg‘𝐺)⟩ ∈ ComplUSGraph)
97, 8eqeltrid 2915 . . 3 (𝐺 ∈ ComplUSGraph → ⟨𝑉, (iEdg‘𝐺)⟩ ∈ ComplUSGraph)
10 fvex 6659 . . . 4 (iEdg‘𝐺) ∈ V
11 fvex 6659 . . . . 5 (Edg‘⟨𝑣, 𝑒⟩) ∈ V
12 rabexg 5210 . . . . . 6 ((Edg‘⟨𝑣, 𝑒⟩) ∈ V → {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐} ∈ V)
1312resiexd 6955 . . . . 5 ((Edg‘⟨𝑣, 𝑒⟩) ∈ V → ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐}) ∈ V)
1411, 13ax-mp 5 . . . 4 ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐}) ∈ V
15 rneq 5782 . . . . . 6 (𝑒 = (iEdg‘𝐺) → ran 𝑒 = ran (iEdg‘𝐺))
1615fveq2d 6650 . . . . 5 (𝑒 = (iEdg‘𝐺) → (♯‘ran 𝑒) = (♯‘ran (iEdg‘𝐺)))
17 fveq2 6646 . . . . . 6 (𝑣 = 𝑉 → (♯‘𝑣) = (♯‘𝑉))
1817oveq1d 7148 . . . . 5 (𝑣 = 𝑉 → ((♯‘𝑣)C2) = ((♯‘𝑉)C2))
1916, 18eqeqan12rd 2839 . . . 4 ((𝑣 = 𝑉𝑒 = (iEdg‘𝐺)) → ((♯‘ran 𝑒) = ((♯‘𝑣)C2) ↔ (♯‘ran (iEdg‘𝐺)) = ((♯‘𝑉)C2)))
20 rneq 5782 . . . . . 6 (𝑒 = 𝑓 → ran 𝑒 = ran 𝑓)
2120fveq2d 6650 . . . . 5 (𝑒 = 𝑓 → (♯‘ran 𝑒) = (♯‘ran 𝑓))
22 fveq2 6646 . . . . . 6 (𝑣 = 𝑤 → (♯‘𝑣) = (♯‘𝑤))
2322oveq1d 7148 . . . . 5 (𝑣 = 𝑤 → ((♯‘𝑣)C2) = ((♯‘𝑤)C2))
2421, 23eqeqan12rd 2839 . . . 4 ((𝑣 = 𝑤𝑒 = 𝑓) → ((♯‘ran 𝑒) = ((♯‘𝑣)C2) ↔ (♯‘ran 𝑓) = ((♯‘𝑤)C2)))
25 vex 3476 . . . . . . 7 𝑣 ∈ V
26 vex 3476 . . . . . . 7 𝑒 ∈ V
2725, 26opvtxfvi 26781 . . . . . 6 (Vtx‘⟨𝑣, 𝑒⟩) = 𝑣
2827eqcomi 2829 . . . . 5 𝑣 = (Vtx‘⟨𝑣, 𝑒⟩)
29 eqid 2820 . . . . 5 (Edg‘⟨𝑣, 𝑒⟩) = (Edg‘⟨𝑣, 𝑒⟩)
30 eqid 2820 . . . . 5 {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐} = {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐}
31 eqid 2820 . . . . 5 ⟨(𝑣 ∖ {𝑛}), ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})⟩ = ⟨(𝑣 ∖ {𝑛}), ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})⟩
3228, 29, 30, 31cusgrres 27217 . . . 4 ((⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ 𝑛𝑣) → ⟨(𝑣 ∖ {𝑛}), ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})⟩ ∈ ComplUSGraph)
33 rneq 5782 . . . . . . 7 (𝑓 = ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐}) → ran 𝑓 = ran ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐}))
3433fveq2d 6650 . . . . . 6 (𝑓 = ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐}) → (♯‘ran 𝑓) = (♯‘ran ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})))
3534adantl 484 . . . . 5 ((𝑤 = (𝑣 ∖ {𝑛}) ∧ 𝑓 = ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})) → (♯‘ran 𝑓) = (♯‘ran ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})))
36 fveq2 6646 . . . . . . 7 (𝑤 = (𝑣 ∖ {𝑛}) → (♯‘𝑤) = (♯‘(𝑣 ∖ {𝑛})))
3736adantr 483 . . . . . 6 ((𝑤 = (𝑣 ∖ {𝑛}) ∧ 𝑓 = ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})) → (♯‘𝑤) = (♯‘(𝑣 ∖ {𝑛})))
3837oveq1d 7148 . . . . 5 ((𝑤 = (𝑣 ∖ {𝑛}) ∧ 𝑓 = ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})) → ((♯‘𝑤)C2) = ((♯‘(𝑣 ∖ {𝑛}))C2))
3935, 38eqeq12d 2836 . . . 4 ((𝑤 = (𝑣 ∖ {𝑛}) ∧ 𝑓 = ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})) → ((♯‘ran 𝑓) = ((♯‘𝑤)C2) ↔ (♯‘ran ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})) = ((♯‘(𝑣 ∖ {𝑛}))C2)))
40 edgopval 26823 . . . . . . . . 9 ((𝑣 ∈ V ∧ 𝑒 ∈ V) → (Edg‘⟨𝑣, 𝑒⟩) = ran 𝑒)
4140el2v 3480 . . . . . . . 8 (Edg‘⟨𝑣, 𝑒⟩) = ran 𝑒
4241a1i 11 . . . . . . 7 ((⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = 0) → (Edg‘⟨𝑣, 𝑒⟩) = ran 𝑒)
4342eqcomd 2826 . . . . . 6 ((⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = 0) → ran 𝑒 = (Edg‘⟨𝑣, 𝑒⟩))
4443fveq2d 6650 . . . . 5 ((⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = 0) → (♯‘ran 𝑒) = (♯‘(Edg‘⟨𝑣, 𝑒⟩)))
45 cusgrusgr 27188 . . . . . . 7 (⟨𝑣, 𝑒⟩ ∈ ComplUSGraph → ⟨𝑣, 𝑒⟩ ∈ USGraph)
46 usgruhgr 26955 . . . . . . 7 (⟨𝑣, 𝑒⟩ ∈ USGraph → ⟨𝑣, 𝑒⟩ ∈ UHGraph)
4745, 46syl 17 . . . . . 6 (⟨𝑣, 𝑒⟩ ∈ ComplUSGraph → ⟨𝑣, 𝑒⟩ ∈ UHGraph)
4828, 29cusgrsizeindb0 27218 . . . . . 6 ((⟨𝑣, 𝑒⟩ ∈ UHGraph ∧ (♯‘𝑣) = 0) → (♯‘(Edg‘⟨𝑣, 𝑒⟩)) = ((♯‘𝑣)C2))
4947, 48sylan 582 . . . . 5 ((⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = 0) → (♯‘(Edg‘⟨𝑣, 𝑒⟩)) = ((♯‘𝑣)C2))
5044, 49eqtrd 2855 . . . 4 ((⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = 0) → (♯‘ran 𝑒) = ((♯‘𝑣)C2))
51 rnresi 5919 . . . . . . . . . 10 ran ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐}) = {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐}
5251fveq2i 6649 . . . . . . . . 9 (♯‘ran ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})) = (♯‘{𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})
5341a1i 11 . . . . . . . . . . 11 (((𝑦 + 1) ∈ ℕ0 ∧ (⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) → (Edg‘⟨𝑣, 𝑒⟩) = ran 𝑒)
5453rabeqdv 3463 . . . . . . . . . 10 (((𝑦 + 1) ∈ ℕ0 ∧ (⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) → {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐} = {𝑐 ∈ ran 𝑒𝑛𝑐})
5554fveq2d 6650 . . . . . . . . 9 (((𝑦 + 1) ∈ ℕ0 ∧ (⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) → (♯‘{𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐}) = (♯‘{𝑐 ∈ ran 𝑒𝑛𝑐}))
5652, 55syl5eq 2867 . . . . . . . 8 (((𝑦 + 1) ∈ ℕ0 ∧ (⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) → (♯‘ran ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})) = (♯‘{𝑐 ∈ ran 𝑒𝑛𝑐}))
5756eqeq1d 2822 . . . . . . 7 (((𝑦 + 1) ∈ ℕ0 ∧ (⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) → ((♯‘ran ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})) = ((♯‘(𝑣 ∖ {𝑛}))C2) ↔ (♯‘{𝑐 ∈ ran 𝑒𝑛𝑐}) = ((♯‘(𝑣 ∖ {𝑛}))C2)))
5857biimpd 231 . . . . . 6 (((𝑦 + 1) ∈ ℕ0 ∧ (⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) → ((♯‘ran ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})) = ((♯‘(𝑣 ∖ {𝑛}))C2) → (♯‘{𝑐 ∈ ran 𝑒𝑛𝑐}) = ((♯‘(𝑣 ∖ {𝑛}))C2)))
5958imdistani 571 . . . . 5 ((((𝑦 + 1) ∈ ℕ0 ∧ (⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) ∧ (♯‘ran ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})) = ((♯‘(𝑣 ∖ {𝑛}))C2)) → (((𝑦 + 1) ∈ ℕ0 ∧ (⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) ∧ (♯‘{𝑐 ∈ ran 𝑒𝑛𝑐}) = ((♯‘(𝑣 ∖ {𝑛}))C2)))
6041eqcomi 2829 . . . . . . 7 ran 𝑒 = (Edg‘⟨𝑣, 𝑒⟩)
61 eqid 2820 . . . . . . 7 {𝑐 ∈ ran 𝑒𝑛𝑐} = {𝑐 ∈ ran 𝑒𝑛𝑐}
6228, 60, 61cusgrsize2inds 27222 . . . . . 6 ((𝑦 + 1) ∈ ℕ0 → ((⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣) → ((♯‘{𝑐 ∈ ran 𝑒𝑛𝑐}) = ((♯‘(𝑣 ∖ {𝑛}))C2) → (♯‘ran 𝑒) = ((♯‘𝑣)C2))))
6362imp31 420 . . . . 5 ((((𝑦 + 1) ∈ ℕ0 ∧ (⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) ∧ (♯‘{𝑐 ∈ ran 𝑒𝑛𝑐}) = ((♯‘(𝑣 ∖ {𝑛}))C2)) → (♯‘ran 𝑒) = ((♯‘𝑣)C2))
6459, 63syl 17 . . . 4 ((((𝑦 + 1) ∈ ℕ0 ∧ (⟨𝑣, 𝑒⟩ ∈ ComplUSGraph ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) ∧ (♯‘ran ( I ↾ {𝑐 ∈ (Edg‘⟨𝑣, 𝑒⟩) ∣ 𝑛𝑐})) = ((♯‘(𝑣 ∖ {𝑛}))C2)) → (♯‘ran 𝑒) = ((♯‘𝑣)C2))
6510, 14, 19, 24, 32, 39, 50, 64opfi1ind 13845 . . 3 ((⟨𝑉, (iEdg‘𝐺)⟩ ∈ ComplUSGraph ∧ 𝑉 ∈ Fin) → (♯‘ran (iEdg‘𝐺)) = ((♯‘𝑉)C2))
669, 65sylan 582 . 2 ((𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin) → (♯‘ran (iEdg‘𝐺)) = ((♯‘𝑉)C2))
675, 66eqtrd 2855 1 ((𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin) → (♯‘𝐸) = ((♯‘𝑉)C2))
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ∧ wa 398   ∧ w3a 1083   = wceq 1537   ∈ wcel 2114   ∉ wnel 3110  {crab 3129  Vcvv 3473   ∖ cdif 3910  {csn 4543  ⟨cop 4549   I cid 5435  ran crn 5532   ↾ cres 5533  ‘cfv 6331  (class class class)co 7133  Fincfn 8487  0cc0 10515  1c1 10516   + caddc 10518  2c2 11671  ℕ0cn0 11876  Ccbc 13647  ♯chash 13675  Vtxcvtx 26768  iEdgciedg 26769  Edgcedg 26819  UHGraphcuhgr 26828  USGraphcusgr 26921  ComplUSGraphccusgr 27179 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1911  ax-6 1970  ax-7 2015  ax-8 2116  ax-9 2124  ax-10 2145  ax-11 2161  ax-12 2177  ax-ext 2792  ax-rep 5166  ax-sep 5179  ax-nul 5186  ax-pow 5242  ax-pr 5306  ax-un 7439  ax-cnex 10571  ax-resscn 10572  ax-1cn 10573  ax-icn 10574  ax-addcl 10575  ax-addrcl 10576  ax-mulcl 10577  ax-mulrcl 10578  ax-mulcom 10579  ax-addass 10580  ax-mulass 10581  ax-distr 10582  ax-i2m1 10583  ax-1ne0 10584  ax-1rid 10585  ax-rnegex 10586  ax-rrecex 10587  ax-cnre 10588  ax-pre-lttri 10589  ax-pre-lttrn 10590  ax-pre-ltadd 10591  ax-pre-mulgt0 10592 This theorem depends on definitions:  df-bi 209  df-an 399  df-or 844  df-3or 1084  df-3an 1085  df-tru 1540  df-fal 1550  df-ex 1781  df-nf 1785  df-sb 2070  df-mo 2622  df-eu 2653  df-clab 2799  df-cleq 2813  df-clel 2891  df-nfc 2959  df-ne 3007  df-nel 3111  df-ral 3130  df-rex 3131  df-reu 3132  df-rmo 3133  df-rab 3134  df-v 3475  df-sbc 3753  df-csb 3861  df-dif 3916  df-un 3918  df-in 3920  df-ss 3930  df-pss 3932  df-nul 4270  df-if 4444  df-pw 4517  df-sn 4544  df-pr 4546  df-tp 4548  df-op 4550  df-uni 4815  df-int 4853  df-iun 4897  df-br 5043  df-opab 5105  df-mpt 5123  df-tr 5149  df-id 5436  df-eprel 5441  df-po 5450  df-so 5451  df-fr 5490  df-we 5492  df-xp 5537  df-rel 5538  df-cnv 5539  df-co 5540  df-dm 5541  df-rn 5542  df-res 5543  df-ima 5544  df-pred 6124  df-ord 6170  df-on 6171  df-lim 6172  df-suc 6173  df-iota 6290  df-fun 6333  df-fn 6334  df-f 6335  df-f1 6336  df-fo 6337  df-f1o 6338  df-fv 6339  df-riota 7091  df-ov 7136  df-oprab 7137  df-mpo 7138  df-om 7559  df-1st 7667  df-2nd 7668  df-wrecs 7925  df-recs 7986  df-rdg 8024  df-1o 8080  df-2o 8081  df-oadd 8084  df-er 8267  df-en 8488  df-dom 8489  df-sdom 8490  df-fin 8491  df-dju 9308  df-card 9346  df-pnf 10655  df-mnf 10656  df-xr 10657  df-ltxr 10658  df-le 10659  df-sub 10850  df-neg 10851  df-div 11276  df-nn 11617  df-2 11679  df-n0 11877  df-xnn0 11947  df-z 11961  df-uz 12223  df-rp 12369  df-fz 12877  df-seq 13354  df-fac 13619  df-bc 13648  df-hash 13676  df-vtx 26770  df-iedg 26771  df-edg 26820  df-uhgr 26830  df-upgr 26854  df-umgr 26855  df-uspgr 26922  df-usgr 26923  df-fusgr 27086  df-nbgr 27102  df-uvtx 27155  df-cplgr 27180  df-cusgr 27181 This theorem is referenced by:  fusgrmaxsize  27233
 Copyright terms: Public domain W3C validator