Mathbox for BTernaryTau < Previous   Next > Nearby theorems Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  umgr2cycllem Structured version   Visualization version   GIF version

Theorem umgr2cycllem 32566
 Description: Lemma for umgr2cycl 32567. (Contributed by BTernaryTau, 17-Oct-2023.)
Hypotheses
Ref Expression
umgr2cycllem.1 𝐹 = ⟨“𝐽𝐾”⟩
umgr2cycllem.2 𝐼 = (iEdg‘𝐺)
umgr2cycllem.3 (𝜑𝐺 ∈ UMGraph)
umgr2cycllem.4 (𝜑𝐽 ∈ dom 𝐼)
umgr2cycllem.5 (𝜑𝐽𝐾)
umgr2cycllem.6 (𝜑 → (𝐼𝐽) = (𝐼𝐾))
Assertion
Ref Expression
umgr2cycllem (𝜑 → ∃𝑝 𝐹(Cycles‘𝐺)𝑝)
Distinct variable groups:   𝐹,𝑝   𝐺,𝑝
Allowed substitution hints:   𝜑(𝑝)   𝐼(𝑝)   𝐽(𝑝)   𝐾(𝑝)

Proof of Theorem umgr2cycllem
Dummy variables 𝑎 𝑏 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 umgr2cycllem.3 . . 3 (𝜑𝐺 ∈ UMGraph)
2 umgruhgr 26941 . . . . 5 (𝐺 ∈ UMGraph → 𝐺 ∈ UHGraph)
3 umgr2cycllem.2 . . . . . 6 𝐼 = (iEdg‘𝐺)
43uhgrfun 26903 . . . . 5 (𝐺 ∈ UHGraph → Fun 𝐼)
51, 2, 43syl 18 . . . 4 (𝜑 → Fun 𝐼)
6 umgr2cycllem.4 . . . 4 (𝜑𝐽 ∈ dom 𝐼)
73iedgedg 26887 . . . 4 ((Fun 𝐼𝐽 ∈ dom 𝐼) → (𝐼𝐽) ∈ (Edg‘𝐺))
85, 6, 7syl2anc 587 . . 3 (𝜑 → (𝐼𝐽) ∈ (Edg‘𝐺))
9 eqid 2798 . . . 4 (Vtx‘𝐺) = (Vtx‘𝐺)
10 eqid 2798 . . . 4 (Edg‘𝐺) = (Edg‘𝐺)
119, 10umgredg 26975 . . 3 ((𝐺 ∈ UMGraph ∧ (𝐼𝐽) ∈ (Edg‘𝐺)) → ∃𝑎 ∈ (Vtx‘𝐺)∃𝑏 ∈ (Vtx‘𝐺)(𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏}))
121, 8, 11syl2anc 587 . 2 (𝜑 → ∃𝑎 ∈ (Vtx‘𝐺)∃𝑏 ∈ (Vtx‘𝐺)(𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏}))
13 ax-5 1911 . . . . . . 7 (𝑎 ∈ (Vtx‘𝐺) → ∀𝑏 𝑎 ∈ (Vtx‘𝐺))
14 alral 3122 . . . . . . 7 (∀𝑏 𝑎 ∈ (Vtx‘𝐺) → ∀𝑏 ∈ (Vtx‘𝐺)𝑎 ∈ (Vtx‘𝐺))
1513, 14syl 17 . . . . . 6 (𝑎 ∈ (Vtx‘𝐺) → ∀𝑏 ∈ (Vtx‘𝐺)𝑎 ∈ (Vtx‘𝐺))
16 r19.29 3217 . . . . . 6 ((∀𝑏 ∈ (Vtx‘𝐺)𝑎 ∈ (Vtx‘𝐺) ∧ ∃𝑏 ∈ (Vtx‘𝐺)(𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → ∃𝑏 ∈ (Vtx‘𝐺)(𝑎 ∈ (Vtx‘𝐺) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})))
1715, 16sylan 583 . . . . 5 ((𝑎 ∈ (Vtx‘𝐺) ∧ ∃𝑏 ∈ (Vtx‘𝐺)(𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → ∃𝑏 ∈ (Vtx‘𝐺)(𝑎 ∈ (Vtx‘𝐺) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})))
18 eqid 2798 . . . . . . . . . . . 12 ⟨“𝑎𝑏𝑎”⟩ = ⟨“𝑎𝑏𝑎”⟩
19 umgr2cycllem.1 . . . . . . . . . . . 12 𝐹 = ⟨“𝐽𝐾”⟩
20 simp2 1134 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)))
21 simp3l 1198 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → 𝑎𝑏)
22 eqimss2 3974 . . . . . . . . . . . . . . 15 ((𝐼𝐽) = {𝑎, 𝑏} → {𝑎, 𝑏} ⊆ (𝐼𝐽))
2322adantl 485 . . . . . . . . . . . . . 14 ((𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏}) → {𝑎, 𝑏} ⊆ (𝐼𝐽))
24233ad2ant3 1132 . . . . . . . . . . . . 13 ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → {𝑎, 𝑏} ⊆ (𝐼𝐽))
25 umgr2cycllem.6 . . . . . . . . . . . . . . . . . 18 (𝜑 → (𝐼𝐽) = (𝐼𝐾))
2625sseq2d 3949 . . . . . . . . . . . . . . . . 17 (𝜑 → ({𝑎, 𝑏} ⊆ (𝐼𝐽) ↔ {𝑎, 𝑏} ⊆ (𝐼𝐾)))
2722, 26syl5ib 247 . . . . . . . . . . . . . . . 16 (𝜑 → ((𝐼𝐽) = {𝑎, 𝑏} → {𝑎, 𝑏} ⊆ (𝐼𝐾)))
2827adantld 494 . . . . . . . . . . . . . . 15 (𝜑 → ((𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏}) → {𝑎, 𝑏} ⊆ (𝐼𝐾)))
2928adantld 494 . . . . . . . . . . . . . 14 (𝜑 → (((𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → {𝑎, 𝑏} ⊆ (𝐼𝐾)))
30293impib 1113 . . . . . . . . . . . . 13 ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → {𝑎, 𝑏} ⊆ (𝐼𝐾))
3124, 30jca 515 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → ({𝑎, 𝑏} ⊆ (𝐼𝐽) ∧ {𝑎, 𝑏} ⊆ (𝐼𝐾)))
32 umgr2cycllem.5 . . . . . . . . . . . . 13 (𝜑𝐽𝐾)
33323ad2ant1 1130 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → 𝐽𝐾)
3418, 19, 20, 21, 31, 9, 3, 332cycl2d 32565 . . . . . . . . . . 11 ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → 𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩)
35343expib 1119 . . . . . . . . . 10 (𝜑 → (((𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → 𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩))
3635exp4c 436 . . . . . . . . 9 (𝜑 → (𝑎 ∈ (Vtx‘𝐺) → (𝑏 ∈ (Vtx‘𝐺) → ((𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏}) → 𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩))))
3736com23 86 . . . . . . . 8 (𝜑 → (𝑏 ∈ (Vtx‘𝐺) → (𝑎 ∈ (Vtx‘𝐺) → ((𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏}) → 𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩))))
3837imp4a 426 . . . . . . 7 (𝜑 → (𝑏 ∈ (Vtx‘𝐺) → ((𝑎 ∈ (Vtx‘𝐺) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → 𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩)))
39 s3cli 14254 . . . . . . . . 9 ⟨“𝑎𝑏𝑎”⟩ ∈ Word V
40 breq2 5038 . . . . . . . . . 10 (𝑝 = ⟨“𝑎𝑏𝑎”⟩ → (𝐹(Cycles‘𝐺)𝑝𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩))
4140rspcev 3572 . . . . . . . . 9 ((⟨“𝑎𝑏𝑎”⟩ ∈ Word V ∧ 𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩) → ∃𝑝 ∈ Word V𝐹(Cycles‘𝐺)𝑝)
4239, 41mpan 689 . . . . . . . 8 (𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩ → ∃𝑝 ∈ Word V𝐹(Cycles‘𝐺)𝑝)
43 rexex 3203 . . . . . . . 8 (∃𝑝 ∈ Word V𝐹(Cycles‘𝐺)𝑝 → ∃𝑝 𝐹(Cycles‘𝐺)𝑝)
4442, 43syl 17 . . . . . . 7 (𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩ → ∃𝑝 𝐹(Cycles‘𝐺)𝑝)
4538, 44syl8 76 . . . . . 6 (𝜑 → (𝑏 ∈ (Vtx‘𝐺) → ((𝑎 ∈ (Vtx‘𝐺) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → ∃𝑝 𝐹(Cycles‘𝐺)𝑝)))
4645rexlimdv 3243 . . . . 5 (𝜑 → (∃𝑏 ∈ (Vtx‘𝐺)(𝑎 ∈ (Vtx‘𝐺) ∧ (𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → ∃𝑝 𝐹(Cycles‘𝐺)𝑝))
4717, 46syl5 34 . . . 4 (𝜑 → ((𝑎 ∈ (Vtx‘𝐺) ∧ ∃𝑏 ∈ (Vtx‘𝐺)(𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏})) → ∃𝑝 𝐹(Cycles‘𝐺)𝑝))
4847expd 419 . . 3 (𝜑 → (𝑎 ∈ (Vtx‘𝐺) → (∃𝑏 ∈ (Vtx‘𝐺)(𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏}) → ∃𝑝 𝐹(Cycles‘𝐺)𝑝)))
4948rexlimdv 3243 . 2 (𝜑 → (∃𝑎 ∈ (Vtx‘𝐺)∃𝑏 ∈ (Vtx‘𝐺)(𝑎𝑏 ∧ (𝐼𝐽) = {𝑎, 𝑏}) → ∃𝑝 𝐹(Cycles‘𝐺)𝑝))
5012, 49mpd 15 1 (𝜑 → ∃𝑝 𝐹(Cycles‘𝐺)𝑝)
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ∧ wa 399   ∧ w3a 1084  ∀wal 1536   = wceq 1538  ∃wex 1781   ∈ wcel 2111   ≠ wne 2987  ∀wral 3106  ∃wrex 3107  Vcvv 3442   ⊆ wss 3883  {cpr 4530   class class class wbr 5034  dom cdm 5523  Fun wfun 6326  ‘cfv 6332  Word cword 13877  ⟨“cs2 14214  ⟨“cs3 14215  Vtxcvtx 26833  iEdgciedg 26834  Edgcedg 26884  UHGraphcuhgr 26893  UMGraphcumgr 26918  Cyclesccycls 27618 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1911  ax-6 1970  ax-7 2015  ax-8 2113  ax-9 2121  ax-10 2142  ax-11 2158  ax-12 2175  ax-ext 2770  ax-rep 5158  ax-sep 5171  ax-nul 5178  ax-pow 5235  ax-pr 5299  ax-un 7454  ax-cnex 10600  ax-resscn 10601  ax-1cn 10602  ax-icn 10603  ax-addcl 10604  ax-addrcl 10605  ax-mulcl 10606  ax-mulrcl 10607  ax-mulcom 10608  ax-addass 10609  ax-mulass 10610  ax-distr 10611  ax-i2m1 10612  ax-1ne0 10613  ax-1rid 10614  ax-rnegex 10615  ax-rrecex 10616  ax-cnre 10617  ax-pre-lttri 10618  ax-pre-lttrn 10619  ax-pre-ltadd 10620  ax-pre-mulgt0 10621 This theorem depends on definitions:  df-bi 210  df-an 400  df-or 845  df-ifp 1059  df-3or 1085  df-3an 1086  df-tru 1541  df-ex 1782  df-nf 1786  df-sb 2070  df-mo 2598  df-eu 2629  df-clab 2777  df-cleq 2791  df-clel 2870  df-nfc 2938  df-ne 2988  df-nel 3092  df-ral 3111  df-rex 3112  df-reu 3113  df-rab 3115  df-v 3444  df-sbc 3723  df-csb 3831  df-dif 3886  df-un 3888  df-in 3890  df-ss 3900  df-pss 3902  df-nul 4247  df-if 4429  df-pw 4502  df-sn 4529  df-pr 4531  df-tp 4533  df-op 4535  df-uni 4805  df-int 4843  df-iun 4887  df-br 5035  df-opab 5097  df-mpt 5115  df-tr 5141  df-id 5429  df-eprel 5434  df-po 5442  df-so 5443  df-fr 5482  df-we 5484  df-xp 5529  df-rel 5530  df-cnv 5531  df-co 5532  df-dm 5533  df-rn 5534  df-res 5535  df-ima 5536  df-pred 6123  df-ord 6169  df-on 6170  df-lim 6171  df-suc 6172  df-iota 6291  df-fun 6334  df-fn 6335  df-f 6336  df-f1 6337  df-fo 6338  df-f1o 6339  df-fv 6340  df-riota 7103  df-ov 7148  df-oprab 7149  df-mpo 7150  df-om 7574  df-1st 7684  df-2nd 7685  df-wrecs 7948  df-recs 8009  df-rdg 8047  df-1o 8103  df-2o 8104  df-oadd 8107  df-er 8290  df-map 8409  df-en 8511  df-dom 8512  df-sdom 8513  df-fin 8514  df-dju 9332  df-card 9370  df-pnf 10684  df-mnf 10685  df-xr 10686  df-ltxr 10687  df-le 10688  df-sub 10879  df-neg 10880  df-nn 11644  df-2 11706  df-3 11707  df-n0 11904  df-z 11990  df-uz 12252  df-fz 12906  df-fzo 13049  df-hash 13707  df-word 13878  df-concat 13934  df-s1 13961  df-s2 14221  df-s3 14222  df-edg 26885  df-uhgr 26895  df-upgr 26919  df-umgr 26920  df-wlks 27433  df-trls 27526  df-pths 27549  df-cycls 27620 This theorem is referenced by:  umgr2cycl  32567
 Copyright terms: Public domain W3C validator