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

Theorem cusgrsize2inds 26405
 Description: Induction step in cusgrsize 26406. If the size of the complete graph with 𝑛 vertices reduced by one vertex is "(𝑛 − 1) choose 2", the size of the complete graph with 𝑛 vertices is "𝑛 choose 2". (Contributed by Alexander van der Vekens, 11-Jan-2018.) (Revised by AV, 9-Nov-2020.)
Hypotheses
Ref Expression
cusgrsizeindb0.v 𝑉 = (Vtx‘𝐺)
cusgrsizeindb0.e 𝐸 = (Edg‘𝐺)
cusgrsizeinds.f 𝐹 = {𝑒𝐸𝑁𝑒}
Assertion
Ref Expression
cusgrsize2inds (𝑌 ∈ ℕ0 → ((𝐺 ∈ ComplUSGraph ∧ (#‘𝑉) = 𝑌𝑁𝑉) → ((#‘𝐹) = ((#‘(𝑉 ∖ {𝑁}))C2) → (#‘𝐸) = ((#‘𝑉)C2))))
Distinct variable groups:   𝑒,𝐸   𝑒,𝐺   𝑒,𝑁   𝑒,𝑉
Allowed substitution hints:   𝐹(𝑒)   𝑌(𝑒)

Proof of Theorem cusgrsize2inds
StepHypRef Expression
1 cusgrsizeindb0.v . . . . 5 𝑉 = (Vtx‘𝐺)
2 fvex 6239 . . . . 5 (Vtx‘𝐺) ∈ V
31, 2eqeltri 2726 . . . 4 𝑉 ∈ V
4 hashnn0n0nn 13218 . . . . . . . 8 (((𝑉 ∈ V ∧ 𝑌 ∈ ℕ0) ∧ ((#‘𝑉) = 𝑌𝑁𝑉)) → 𝑌 ∈ ℕ)
54anassrs 681 . . . . . . 7 ((((𝑉 ∈ V ∧ 𝑌 ∈ ℕ0) ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) → 𝑌 ∈ ℕ)
6 simplll 813 . . . . . . . . . . 11 ((((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) ∧ 𝑌 ∈ ℕ) → 𝑉 ∈ V)
7 simplr 807 . . . . . . . . . . 11 ((((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) ∧ 𝑌 ∈ ℕ) → 𝑁𝑉)
8 eleq1 2718 . . . . . . . . . . . . . . 15 (𝑌 = (#‘𝑉) → (𝑌 ∈ ℕ ↔ (#‘𝑉) ∈ ℕ))
98eqcoms 2659 . . . . . . . . . . . . . 14 ((#‘𝑉) = 𝑌 → (𝑌 ∈ ℕ ↔ (#‘𝑉) ∈ ℕ))
10 nnm1nn0 11372 . . . . . . . . . . . . . 14 ((#‘𝑉) ∈ ℕ → ((#‘𝑉) − 1) ∈ ℕ0)
119, 10syl6bi 243 . . . . . . . . . . . . 13 ((#‘𝑉) = 𝑌 → (𝑌 ∈ ℕ → ((#‘𝑉) − 1) ∈ ℕ0))
1211ad2antlr 763 . . . . . . . . . . . 12 (((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) → (𝑌 ∈ ℕ → ((#‘𝑉) − 1) ∈ ℕ0))
1312imp 444 . . . . . . . . . . 11 ((((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) ∧ 𝑌 ∈ ℕ) → ((#‘𝑉) − 1) ∈ ℕ0)
14 nncn 11066 . . . . . . . . . . . . . . . 16 ((#‘𝑉) ∈ ℕ → (#‘𝑉) ∈ ℂ)
15 1cnd 10094 . . . . . . . . . . . . . . . 16 ((#‘𝑉) ∈ ℕ → 1 ∈ ℂ)
1614, 15npcand 10434 . . . . . . . . . . . . . . 15 ((#‘𝑉) ∈ ℕ → (((#‘𝑉) − 1) + 1) = (#‘𝑉))
1716eqcomd 2657 . . . . . . . . . . . . . 14 ((#‘𝑉) ∈ ℕ → (#‘𝑉) = (((#‘𝑉) − 1) + 1))
189, 17syl6bi 243 . . . . . . . . . . . . 13 ((#‘𝑉) = 𝑌 → (𝑌 ∈ ℕ → (#‘𝑉) = (((#‘𝑉) − 1) + 1)))
1918ad2antlr 763 . . . . . . . . . . . 12 (((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) → (𝑌 ∈ ℕ → (#‘𝑉) = (((#‘𝑉) − 1) + 1)))
2019imp 444 . . . . . . . . . . 11 ((((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) ∧ 𝑌 ∈ ℕ) → (#‘𝑉) = (((#‘𝑉) − 1) + 1))
21 brfi1indlem 13316 . . . . . . . . . . . 12 ((𝑉 ∈ V ∧ 𝑁𝑉 ∧ ((#‘𝑉) − 1) ∈ ℕ0) → ((#‘𝑉) = (((#‘𝑉) − 1) + 1) → (#‘(𝑉 ∖ {𝑁})) = ((#‘𝑉) − 1)))
2221imp 444 . . . . . . . . . . 11 (((𝑉 ∈ V ∧ 𝑁𝑉 ∧ ((#‘𝑉) − 1) ∈ ℕ0) ∧ (#‘𝑉) = (((#‘𝑉) − 1) + 1)) → (#‘(𝑉 ∖ {𝑁})) = ((#‘𝑉) − 1))
236, 7, 13, 20, 22syl31anc 1369 . . . . . . . . . 10 ((((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) ∧ 𝑌 ∈ ℕ) → (#‘(𝑉 ∖ {𝑁})) = ((#‘𝑉) − 1))
24 oveq1 6697 . . . . . . . . . . . . 13 ((#‘(𝑉 ∖ {𝑁})) = ((#‘𝑉) − 1) → ((#‘(𝑉 ∖ {𝑁}))C2) = (((#‘𝑉) − 1)C2))
2524eqeq2d 2661 . . . . . . . . . . . 12 ((#‘(𝑉 ∖ {𝑁})) = ((#‘𝑉) − 1) → ((#‘𝐹) = ((#‘(𝑉 ∖ {𝑁}))C2) ↔ (#‘𝐹) = (((#‘𝑉) − 1)C2)))
269ad2antlr 763 . . . . . . . . . . . . . . 15 (((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) → (𝑌 ∈ ℕ ↔ (#‘𝑉) ∈ ℕ))
27 nnnn0 11337 . . . . . . . . . . . . . . . . . . . 20 ((#‘𝑉) ∈ ℕ → (#‘𝑉) ∈ ℕ0)
28 hashclb 13187 . . . . . . . . . . . . . . . . . . . 20 (𝑉 ∈ V → (𝑉 ∈ Fin ↔ (#‘𝑉) ∈ ℕ0))
2927, 28syl5ibrcom 237 . . . . . . . . . . . . . . . . . . 19 ((#‘𝑉) ∈ ℕ → (𝑉 ∈ V → 𝑉 ∈ Fin))
30 cusgrsizeindb0.e . . . . . . . . . . . . . . . . . . . . . . 23 𝐸 = (Edg‘𝐺)
31 cusgrsizeinds.f . . . . . . . . . . . . . . . . . . . . . . 23 𝐹 = {𝑒𝐸𝑁𝑒}
321, 30, 31cusgrsizeinds 26404 . . . . . . . . . . . . . . . . . . . . . 22 ((𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ∧ 𝑁𝑉) → (#‘𝐸) = (((#‘𝑉) − 1) + (#‘𝐹)))
33 oveq2 6698 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((#‘𝐹) = (((#‘𝑉) − 1)C2) → (((#‘𝑉) − 1) + (#‘𝐹)) = (((#‘𝑉) − 1) + (((#‘𝑉) − 1)C2)))
3433eqeq2d 2661 . . . . . . . . . . . . . . . . . . . . . . . . . 26 ((#‘𝐹) = (((#‘𝑉) − 1)C2) → ((#‘𝐸) = (((#‘𝑉) − 1) + (#‘𝐹)) ↔ (#‘𝐸) = (((#‘𝑉) − 1) + (((#‘𝑉) − 1)C2))))
3534adantl 481 . . . . . . . . . . . . . . . . . . . . . . . . 25 (((#‘𝑉) ∈ ℕ ∧ (#‘𝐹) = (((#‘𝑉) − 1)C2)) → ((#‘𝐸) = (((#‘𝑉) − 1) + (#‘𝐹)) ↔ (#‘𝐸) = (((#‘𝑉) − 1) + (((#‘𝑉) − 1)C2))))
36 bcn2m1 13151 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ((#‘𝑉) ∈ ℕ → (((#‘𝑉) − 1) + (((#‘𝑉) − 1)C2)) = ((#‘𝑉)C2))
3736eqeq2d 2661 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((#‘𝑉) ∈ ℕ → ((#‘𝐸) = (((#‘𝑉) − 1) + (((#‘𝑉) − 1)C2)) ↔ (#‘𝐸) = ((#‘𝑉)C2)))
3837biimpd 219 . . . . . . . . . . . . . . . . . . . . . . . . . 26 ((#‘𝑉) ∈ ℕ → ((#‘𝐸) = (((#‘𝑉) − 1) + (((#‘𝑉) − 1)C2)) → (#‘𝐸) = ((#‘𝑉)C2)))
3938adantr 480 . . . . . . . . . . . . . . . . . . . . . . . . 25 (((#‘𝑉) ∈ ℕ ∧ (#‘𝐹) = (((#‘𝑉) − 1)C2)) → ((#‘𝐸) = (((#‘𝑉) − 1) + (((#‘𝑉) − 1)C2)) → (#‘𝐸) = ((#‘𝑉)C2)))
4035, 39sylbid 230 . . . . . . . . . . . . . . . . . . . . . . . 24 (((#‘𝑉) ∈ ℕ ∧ (#‘𝐹) = (((#‘𝑉) − 1)C2)) → ((#‘𝐸) = (((#‘𝑉) − 1) + (#‘𝐹)) → (#‘𝐸) = ((#‘𝑉)C2)))
4140ex 449 . . . . . . . . . . . . . . . . . . . . . . 23 ((#‘𝑉) ∈ ℕ → ((#‘𝐹) = (((#‘𝑉) − 1)C2) → ((#‘𝐸) = (((#‘𝑉) − 1) + (#‘𝐹)) → (#‘𝐸) = ((#‘𝑉)C2))))
4241com3r 87 . . . . . . . . . . . . . . . . . . . . . 22 ((#‘𝐸) = (((#‘𝑉) − 1) + (#‘𝐹)) → ((#‘𝑉) ∈ ℕ → ((#‘𝐹) = (((#‘𝑉) − 1)C2) → (#‘𝐸) = ((#‘𝑉)C2))))
4332, 42syl 17 . . . . . . . . . . . . . . . . . . . . 21 ((𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ∧ 𝑁𝑉) → ((#‘𝑉) ∈ ℕ → ((#‘𝐹) = (((#‘𝑉) − 1)C2) → (#‘𝐸) = ((#‘𝑉)C2))))
44433exp 1283 . . . . . . . . . . . . . . . . . . . 20 (𝐺 ∈ ComplUSGraph → (𝑉 ∈ Fin → (𝑁𝑉 → ((#‘𝑉) ∈ ℕ → ((#‘𝐹) = (((#‘𝑉) − 1)C2) → (#‘𝐸) = ((#‘𝑉)C2))))))
4544com14 96 . . . . . . . . . . . . . . . . . . 19 ((#‘𝑉) ∈ ℕ → (𝑉 ∈ Fin → (𝑁𝑉 → (𝐺 ∈ ComplUSGraph → ((#‘𝐹) = (((#‘𝑉) − 1)C2) → (#‘𝐸) = ((#‘𝑉)C2))))))
4629, 45syldc 48 . . . . . . . . . . . . . . . . . 18 (𝑉 ∈ V → ((#‘𝑉) ∈ ℕ → (𝑁𝑉 → (𝐺 ∈ ComplUSGraph → ((#‘𝐹) = (((#‘𝑉) − 1)C2) → (#‘𝐸) = ((#‘𝑉)C2))))))
4746com23 86 . . . . . . . . . . . . . . . . 17 (𝑉 ∈ V → (𝑁𝑉 → ((#‘𝑉) ∈ ℕ → (𝐺 ∈ ComplUSGraph → ((#‘𝐹) = (((#‘𝑉) − 1)C2) → (#‘𝐸) = ((#‘𝑉)C2))))))
4847adantr 480 . . . . . . . . . . . . . . . 16 ((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) → (𝑁𝑉 → ((#‘𝑉) ∈ ℕ → (𝐺 ∈ ComplUSGraph → ((#‘𝐹) = (((#‘𝑉) − 1)C2) → (#‘𝐸) = ((#‘𝑉)C2))))))
4948imp 444 . . . . . . . . . . . . . . 15 (((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) → ((#‘𝑉) ∈ ℕ → (𝐺 ∈ ComplUSGraph → ((#‘𝐹) = (((#‘𝑉) − 1)C2) → (#‘𝐸) = ((#‘𝑉)C2)))))
5026, 49sylbid 230 . . . . . . . . . . . . . 14 (((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) → (𝑌 ∈ ℕ → (𝐺 ∈ ComplUSGraph → ((#‘𝐹) = (((#‘𝑉) − 1)C2) → (#‘𝐸) = ((#‘𝑉)C2)))))
5150imp 444 . . . . . . . . . . . . 13 ((((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) ∧ 𝑌 ∈ ℕ) → (𝐺 ∈ ComplUSGraph → ((#‘𝐹) = (((#‘𝑉) − 1)C2) → (#‘𝐸) = ((#‘𝑉)C2))))
5251com13 88 . . . . . . . . . . . 12 ((#‘𝐹) = (((#‘𝑉) − 1)C2) → (𝐺 ∈ ComplUSGraph → ((((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) ∧ 𝑌 ∈ ℕ) → (#‘𝐸) = ((#‘𝑉)C2))))
5325, 52syl6bi 243 . . . . . . . . . . 11 ((#‘(𝑉 ∖ {𝑁})) = ((#‘𝑉) − 1) → ((#‘𝐹) = ((#‘(𝑉 ∖ {𝑁}))C2) → (𝐺 ∈ ComplUSGraph → ((((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) ∧ 𝑌 ∈ ℕ) → (#‘𝐸) = ((#‘𝑉)C2)))))
5453com24 95 . . . . . . . . . 10 ((#‘(𝑉 ∖ {𝑁})) = ((#‘𝑉) − 1) → ((((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) ∧ 𝑌 ∈ ℕ) → (𝐺 ∈ ComplUSGraph → ((#‘𝐹) = ((#‘(𝑉 ∖ {𝑁}))C2) → (#‘𝐸) = ((#‘𝑉)C2)))))
5523, 54mpcom 38 . . . . . . . . 9 ((((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) ∧ 𝑌 ∈ ℕ) → (𝐺 ∈ ComplUSGraph → ((#‘𝐹) = ((#‘(𝑉 ∖ {𝑁}))C2) → (#‘𝐸) = ((#‘𝑉)C2))))
5655ex 449 . . . . . . . 8 (((𝑉 ∈ V ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) → (𝑌 ∈ ℕ → (𝐺 ∈ ComplUSGraph → ((#‘𝐹) = ((#‘(𝑉 ∖ {𝑁}))C2) → (#‘𝐸) = ((#‘𝑉)C2)))))
5756adantllr 755 . . . . . . 7 ((((𝑉 ∈ V ∧ 𝑌 ∈ ℕ0) ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) → (𝑌 ∈ ℕ → (𝐺 ∈ ComplUSGraph → ((#‘𝐹) = ((#‘(𝑉 ∖ {𝑁}))C2) → (#‘𝐸) = ((#‘𝑉)C2)))))
585, 57mpd 15 . . . . . 6 ((((𝑉 ∈ V ∧ 𝑌 ∈ ℕ0) ∧ (#‘𝑉) = 𝑌) ∧ 𝑁𝑉) → (𝐺 ∈ ComplUSGraph → ((#‘𝐹) = ((#‘(𝑉 ∖ {𝑁}))C2) → (#‘𝐸) = ((#‘𝑉)C2))))
5958exp41 637 . . . . 5 (𝑉 ∈ V → (𝑌 ∈ ℕ0 → ((#‘𝑉) = 𝑌 → (𝑁𝑉 → (𝐺 ∈ ComplUSGraph → ((#‘𝐹) = ((#‘(𝑉 ∖ {𝑁}))C2) → (#‘𝐸) = ((#‘𝑉)C2)))))))
6059com25 99 . . . 4 (𝑉 ∈ V → (𝐺 ∈ ComplUSGraph → ((#‘𝑉) = 𝑌 → (𝑁𝑉 → (𝑌 ∈ ℕ0 → ((#‘𝐹) = ((#‘(𝑉 ∖ {𝑁}))C2) → (#‘𝐸) = ((#‘𝑉)C2)))))))
613, 60ax-mp 5 . . 3 (𝐺 ∈ ComplUSGraph → ((#‘𝑉) = 𝑌 → (𝑁𝑉 → (𝑌 ∈ ℕ0 → ((#‘𝐹) = ((#‘(𝑉 ∖ {𝑁}))C2) → (#‘𝐸) = ((#‘𝑉)C2))))))
62613imp 1275 . 2 ((𝐺 ∈ ComplUSGraph ∧ (#‘𝑉) = 𝑌𝑁𝑉) → (𝑌 ∈ ℕ0 → ((#‘𝐹) = ((#‘(𝑉 ∖ {𝑁}))C2) → (#‘𝐸) = ((#‘𝑉)C2))))
6362com12 32 1 (𝑌 ∈ ℕ0 → ((𝐺 ∈ ComplUSGraph ∧ (#‘𝑉) = 𝑌𝑁𝑉) → ((#‘𝐹) = ((#‘(𝑉 ∖ {𝑁}))C2) → (#‘𝐸) = ((#‘𝑉)C2))))
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ↔ wb 196   ∧ wa 383   ∧ w3a 1054   = wceq 1523   ∈ wcel 2030   ∉ wnel 2926  {crab 2945  Vcvv 3231   ∖ cdif 3604  {csn 4210  ‘cfv 5926  (class class class)co 6690  Fincfn 7997  1c1 9975   + caddc 9977   − cmin 10304  ℕcn 11058  2c2 11108  ℕ0cn0 11330  Ccbc 13129  #chash 13157  Vtxcvtx 25919  Edgcedg 25984  ComplUSGraphccusgr 26361 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1762  ax-4 1777  ax-5 1879  ax-6 1945  ax-7 1981  ax-8 2032  ax-9 2039  ax-10 2059  ax-11 2074  ax-12 2087  ax-13 2282  ax-ext 2631  ax-rep 4804  ax-sep 4814  ax-nul 4822  ax-pow 4873  ax-pr 4936  ax-un 6991  ax-cnex 10030  ax-resscn 10031  ax-1cn 10032  ax-icn 10033  ax-addcl 10034  ax-addrcl 10035  ax-mulcl 10036  ax-mulrcl 10037  ax-mulcom 10038  ax-addass 10039  ax-mulass 10040  ax-distr 10041  ax-i2m1 10042  ax-1ne0 10043  ax-1rid 10044  ax-rnegex 10045  ax-rrecex 10046  ax-cnre 10047  ax-pre-lttri 10048  ax-pre-lttrn 10049  ax-pre-ltadd 10050  ax-pre-mulgt0 10051 This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3or 1055  df-3an 1056  df-tru 1526  df-fal 1529  df-ex 1745  df-nf 1750  df-sb 1938  df-eu 2502  df-mo 2503  df-clab 2638  df-cleq 2644  df-clel 2647  df-nfc 2782  df-ne 2824  df-nel 2927  df-ral 2946  df-rex 2947  df-reu 2948  df-rmo 2949  df-rab 2950  df-v 3233  df-sbc 3469  df-csb 3567  df-dif 3610  df-un 3612  df-in 3614  df-ss 3621  df-pss 3623  df-nul 3949  df-if 4120  df-pw 4193  df-sn 4211  df-pr 4213  df-tp 4215  df-op 4217  df-uni 4469  df-int 4508  df-iun 4554  df-br 4686  df-opab 4746  df-mpt 4763  df-tr 4786  df-id 5053  df-eprel 5058  df-po 5064  df-so 5065  df-fr 5102  df-we 5104  df-xp 5149  df-rel 5150  df-cnv 5151  df-co 5152  df-dm 5153  df-rn 5154  df-res 5155  df-ima 5156  df-pred 5718  df-ord 5764  df-on 5765  df-lim 5766  df-suc 5767  df-iota 5889  df-fun 5928  df-fn 5929  df-f 5930  df-f1 5931  df-fo 5932  df-f1o 5933  df-fv 5934  df-riota 6651  df-ov 6693  df-oprab 6694  df-mpt2 6695  df-om 7108  df-1st 7210  df-2nd 7211  df-wrecs 7452  df-recs 7513  df-rdg 7551  df-1o 7605  df-2o 7606  df-oadd 7609  df-er 7787  df-en 7998  df-dom 7999  df-sdom 8000  df-fin 8001  df-card 8803  df-cda 9028  df-pnf 10114  df-mnf 10115  df-xr 10116  df-ltxr 10117  df-le 10118  df-sub 10306  df-neg 10307  df-div 10723  df-nn 11059  df-2 11117  df-n0 11331  df-xnn0 11402  df-z 11416  df-uz 11726  df-rp 11871  df-fz 12365  df-seq 12842  df-fac 13101  df-bc 13130  df-hash 13158  df-vtx 25921  df-iedg 25922  df-edg 25985  df-uhgr 25998  df-upgr 26022  df-umgr 26023  df-uspgr 26090  df-usgr 26091  df-fusgr 26254  df-nbgr 26270  df-uvtx 26332  df-cplgr 26362  df-cusgr 26363 This theorem is referenced by:  cusgrsize  26406
 Copyright terms: Public domain W3C validator