Theorem umgr2cycllem 33342

Description: Lemma for umgr2cycl 33343. (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.

Step	Hyp	Ref	Expression
1		umgr2cycllem.3	. . 3 ⊢ (𝜑 → 𝐺 ∈ UMGraph)
2		umgruhgr 27704	. . . . 5 ⊢ (𝐺 ∈ UMGraph → 𝐺 ∈ UHGraph)
3		umgr2cycllem.2	. . . . . 6 ⊢ 𝐼 = (iEdg‘𝐺)
4	3	uhgrfun 27666	. . . . 5 ⊢ (𝐺 ∈ UHGraph → Fun 𝐼)
5	1, 2, 4	3syl 18	. . . 4 ⊢ (𝜑 → Fun 𝐼)
6		umgr2cycllem.4	. . . 4 ⊢ (𝜑 → 𝐽 ∈ dom 𝐼)
7	3	iedgedg 27650	. . . 4 ⊢ ((Fun 𝐼 ∧ 𝐽 ∈ dom 𝐼) → (𝐼‘𝐽) ∈ (Edg‘𝐺))
8	5, 6, 7	syl2anc 584	. . 3 ⊢ (𝜑 → (𝐼‘𝐽) ∈ (Edg‘𝐺))
9		eqid 2736	. . . 4 ⊢ (Vtx‘𝐺) = (Vtx‘𝐺)
10		eqid 2736	. . . 4 ⊢ (Edg‘𝐺) = (Edg‘𝐺)
11	9, 10	umgredg 27738	. . 3 ⊢ ((𝐺 ∈ UMGraph ∧ (𝐼‘𝐽) ∈ (Edg‘𝐺)) → ∃𝑎 ∈ (Vtx‘𝐺)∃𝑏 ∈ (Vtx‘𝐺)(𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏}))
12	1, 8, 11	syl2anc 584	. 2 ⊢ (𝜑 → ∃𝑎 ∈ (Vtx‘𝐺)∃𝑏 ∈ (Vtx‘𝐺)(𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏}))
13		ax-5 1912	. . . . . . 7 ⊢ (𝑎 ∈ (Vtx‘𝐺) → ∀𝑏 𝑎 ∈ (Vtx‘𝐺))
14		alral 3075	. . . . . . 7 ⊢ (∀𝑏 𝑎 ∈ (Vtx‘𝐺) → ∀𝑏 ∈ (Vtx‘𝐺)𝑎 ∈ (Vtx‘𝐺))
15	13, 14	syl 17	. . . . . 6 ⊢ (𝑎 ∈ (Vtx‘𝐺) → ∀𝑏 ∈ (Vtx‘𝐺)𝑎 ∈ (Vtx‘𝐺))
16		r19.29 3113	. . . . . 6 ⊢ ((∀𝑏 ∈ (Vtx‘𝐺)𝑎 ∈ (Vtx‘𝐺) ∧ ∃𝑏 ∈ (Vtx‘𝐺)(𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → ∃𝑏 ∈ (Vtx‘𝐺)(𝑎 ∈ (Vtx‘𝐺) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})))
17	15, 16	sylan 580	. . . . 5 ⊢ ((𝑎 ∈ (Vtx‘𝐺) ∧ ∃𝑏 ∈ (Vtx‘𝐺)(𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → ∃𝑏 ∈ (Vtx‘𝐺)(𝑎 ∈ (Vtx‘𝐺) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})))
18		eqid 2736	. . . . . . . . . . . 12 ⊢ ⟨“𝑎𝑏𝑎”⟩ = ⟨“𝑎𝑏𝑎”⟩
19		umgr2cycllem.1	. . . . . . . . . . . 12 ⊢ 𝐹 = ⟨“𝐽𝐾”⟩
20		simp2 1136	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)))
21		simp3l 1200	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → 𝑎 ≠ 𝑏)
22		eqimss2 3988	. . . . . . . . . . . . . . 15 ⊢ ((𝐼‘𝐽) = {𝑎, 𝑏} → {𝑎, 𝑏} ⊆ (𝐼‘𝐽))
23	22	adantl 482	. . . . . . . . . . . . . 14 ⊢ ((𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏}) → {𝑎, 𝑏} ⊆ (𝐼‘𝐽))
24	23	3ad2ant3 1134	. . . . . . . . . . . . 13 ⊢ ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → {𝑎, 𝑏} ⊆ (𝐼‘𝐽))
25		umgr2cycllem.6	. . . . . . . . . . . . . . . . . 18 ⊢ (𝜑 → (𝐼‘𝐽) = (𝐼‘𝐾))
26	25	sseq2d 3963	. . . . . . . . . . . . . . . . 17 ⊢ (𝜑 → ({𝑎, 𝑏} ⊆ (𝐼‘𝐽) ↔ {𝑎, 𝑏} ⊆ (𝐼‘𝐾)))
27	22, 26	syl5ib 243	. . . . . . . . . . . . . . . 16 ⊢ (𝜑 → ((𝐼‘𝐽) = {𝑎, 𝑏} → {𝑎, 𝑏} ⊆ (𝐼‘𝐾)))
28	27	adantld 491	. . . . . . . . . . . . . . 15 ⊢ (𝜑 → ((𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏}) → {𝑎, 𝑏} ⊆ (𝐼‘𝐾)))
29	28	adantld 491	. . . . . . . . . . . . . 14 ⊢ (𝜑 → (((𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → {𝑎, 𝑏} ⊆ (𝐼‘𝐾)))
30	29	3impib 1115	. . . . . . . . . . . . 13 ⊢ ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → {𝑎, 𝑏} ⊆ (𝐼‘𝐾))
31	24, 30	jca 512	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → ({𝑎, 𝑏} ⊆ (𝐼‘𝐽) ∧ {𝑎, 𝑏} ⊆ (𝐼‘𝐾)))
32		umgr2cycllem.5	. . . . . . . . . . . . 13 ⊢ (𝜑 → 𝐽 ≠ 𝐾)
33	32	3ad2ant1 1132	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → 𝐽 ≠ 𝐾)
34	18, 19, 20, 21, 31, 9, 3, 33	2cycl2d 33341	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ (𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → 𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩)
35	34	3expib 1121	. . . . . . . . . 10 ⊢ (𝜑 → (((𝑎 ∈ (Vtx‘𝐺) ∧ 𝑏 ∈ (Vtx‘𝐺)) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → 𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩))
36	35	exp4c 433	. . . . . . . . 9 ⊢ (𝜑 → (𝑎 ∈ (Vtx‘𝐺) → (𝑏 ∈ (Vtx‘𝐺) → ((𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏}) → 𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩))))
37	36	com23 86	. . . . . . . 8 ⊢ (𝜑 → (𝑏 ∈ (Vtx‘𝐺) → (𝑎 ∈ (Vtx‘𝐺) → ((𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏}) → 𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩))))
38	37	imp4a 423	. . . . . . 7 ⊢ (𝜑 → (𝑏 ∈ (Vtx‘𝐺) → ((𝑎 ∈ (Vtx‘𝐺) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → 𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩)))
39		s3cli 14685	. . . . . . . . 9 ⊢ ⟨“𝑎𝑏𝑎”⟩ ∈ Word V
40		breq2 5093	. . . . . . . . . 10 ⊢ (𝑝 = ⟨“𝑎𝑏𝑎”⟩ → (𝐹(Cycles‘𝐺)𝑝 ↔ 𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩))
41	40	rspcev 3570	. . . . . . . . 9 ⊢ ((⟨“𝑎𝑏𝑎”⟩ ∈ Word V ∧ 𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩) → ∃𝑝 ∈ Word V𝐹(Cycles‘𝐺)𝑝)
42	39, 41	mpan 687	. . . . . . . 8 ⊢ (𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩ → ∃𝑝 ∈ Word V𝐹(Cycles‘𝐺)𝑝)
43		rexex 3076	. . . . . . . 8 ⊢ (∃𝑝 ∈ Word V𝐹(Cycles‘𝐺)𝑝 → ∃𝑝 𝐹(Cycles‘𝐺)𝑝)
44	42, 43	syl 17	. . . . . . 7 ⊢ (𝐹(Cycles‘𝐺)⟨“𝑎𝑏𝑎”⟩ → ∃𝑝 𝐹(Cycles‘𝐺)𝑝)
45	38, 44	syl8 76	. . . . . 6 ⊢ (𝜑 → (𝑏 ∈ (Vtx‘𝐺) → ((𝑎 ∈ (Vtx‘𝐺) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → ∃𝑝 𝐹(Cycles‘𝐺)𝑝)))
46	45	rexlimdv 3146	. . . . 5 ⊢ (𝜑 → (∃𝑏 ∈ (Vtx‘𝐺)(𝑎 ∈ (Vtx‘𝐺) ∧ (𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → ∃𝑝 𝐹(Cycles‘𝐺)𝑝))
47	17, 46	syl5 34	. . . 4 ⊢ (𝜑 → ((𝑎 ∈ (Vtx‘𝐺) ∧ ∃𝑏 ∈ (Vtx‘𝐺)(𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏})) → ∃𝑝 𝐹(Cycles‘𝐺)𝑝))
48	47	expd 416	. . 3 ⊢ (𝜑 → (𝑎 ∈ (Vtx‘𝐺) → (∃𝑏 ∈ (Vtx‘𝐺)(𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏}) → ∃𝑝 𝐹(Cycles‘𝐺)𝑝)))
49	48	rexlimdv 3146	. 2 ⊢ (𝜑 → (∃𝑎 ∈ (Vtx‘𝐺)∃𝑏 ∈ (Vtx‘𝐺)(𝑎 ≠ 𝑏 ∧ (𝐼‘𝐽) = {𝑎, 𝑏}) → ∃𝑝 𝐹(Cycles‘𝐺)𝑝))
50	12, 49	mpd 15	1 ⊢ (𝜑 → ∃𝑝 𝐹(Cycles‘𝐺)𝑝)

Syntax hints:   → wi 4   ∧ wa 396   ∧ w3a 1086  ∀wal 1538   = wceq 1540  ∃wex 1780   ∈ wcel 2105   ≠ wne 2940  ∀wral 3061  ∃wrex 3070  Vcvv 3441   ⊆ wss 3897  {cpr 4574   class class class wbr 5089  dom cdm 5614  Fun wfun 6467  ‘cfv 6473  Word cword 14309  ⟨“cs2 14645  ⟨“cs3 14646  Vtxcvtx 27596  iEdgciedg 27597  Edgcedg 27647  UHGraphcuhgr 27656  UMGraphcumgr 27681  Cyclesccycls 28382

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 1912  ax-6 1970  ax-7 2010  ax-8 2107  ax-9 2115  ax-10 2136  ax-11 2153  ax-12 2170  ax-ext 2707  ax-rep 5226  ax-sep 5240  ax-nul 5247  ax-pow 5305  ax-pr 5369  ax-un 7642  ax-cnex 11020  ax-resscn 11021  ax-1cn 11022  ax-icn 11023  ax-addcl 11024  ax-addrcl 11025  ax-mulcl 11026  ax-mulrcl 11027  ax-mulcom 11028  ax-addass 11029  ax-mulass 11030  ax-distr 11031  ax-i2m1 11032  ax-1ne0 11033  ax-1rid 11034  ax-rnegex 11035  ax-rrecex 11036  ax-cnre 11037  ax-pre-lttri 11038  ax-pre-lttrn 11039  ax-pre-ltadd 11040  ax-pre-mulgt0 11041

This theorem depends on definitions:  df-bi 206  df-an 397  df-or 845  df-ifp 1061  df-3or 1087  df-3an 1088  df-tru 1543  df-fal 1553  df-ex 1781  df-nf 1785  df-sb 2067  df-mo 2538  df-eu 2567  df-clab 2714  df-cleq 2728  df-clel 2814  df-nfc 2886  df-ne 2941  df-nel 3047  df-ral 3062  df-rex 3071  df-reu 3350  df-rab 3404  df-v 3443  df-sbc 3727  df-csb 3843  df-dif 3900  df-un 3902  df-in 3904  df-ss 3914  df-pss 3916  df-nul 4269  df-if 4473  df-pw 4548  df-sn 4573  df-pr 4575  df-tp 4577  df-op 4579  df-uni 4852  df-int 4894  df-iun 4940  df-br 5090  df-opab 5152  df-mpt 5173  df-tr 5207  df-id 5512  df-eprel 5518  df-po 5526  df-so 5527  df-fr 5569  df-we 5571  df-xp 5620  df-rel 5621  df-cnv 5622  df-co 5623  df-dm 5624  df-rn 5625  df-res 5626  df-ima 5627  df-pred 6232  df-ord 6299  df-on 6300  df-lim 6301  df-suc 6302  df-iota 6425  df-fun 6475  df-fn 6476  df-f 6477  df-f1 6478  df-fo 6479  df-f1o 6480  df-fv 6481  df-riota 7286  df-ov 7332  df-oprab 7333  df-mpo 7334  df-om 7773  df-1st 7891  df-2nd 7892  df-frecs 8159  df-wrecs 8190  df-recs 8264  df-rdg 8303  df-1o 8359  df-2o 8360  df-oadd 8363  df-er 8561  df-map 8680  df-en 8797  df-dom 8798  df-sdom 8799  df-fin 8800  df-dju 9750  df-card 9788  df-pnf 11104  df-mnf 11105  df-xr 11106  df-ltxr 11107  df-le 11108  df-sub 11300  df-neg 11301  df-nn 12067  df-2 12129  df-3 12130  df-n0 12327  df-z 12413  df-uz 12676  df-fz 13333  df-fzo 13476  df-hash 14138  df-word 14310  df-concat 14366  df-s1 14392  df-s2 14652  df-s3 14653  df-edg 27648  df-uhgr 27658  df-upgr 27682  df-umgr 27683  df-wlks 28196  df-trls 28289  df-pths 28313  df-cycls 28384

This theorem is referenced by:  umgr2cycl  33343