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

Theorem 1pthon2v 27324
Description: For each pair of adjacent vertices there is a path of length 1 from one vertex to the other in a hypergraph. (Contributed by Alexander van der Vekens, 4-Dec-2017.) (Revised by AV, 22-Jan-2021.)
Hypotheses
Ref Expression
1pthon2v.v 𝑉 = (Vtx‘𝐺)
1pthon2v.e 𝐸 = (Edg‘𝐺)
Assertion
Ref Expression
1pthon2v ((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ ∃𝑒𝐸 {𝐴, 𝐵} ⊆ 𝑒) → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝)
Distinct variable groups:   𝐴,𝑒,𝑓,𝑝   𝐵,𝑒,𝑓,𝑝   𝑒,𝐺,𝑓,𝑝   𝑒,𝑉
Allowed substitution hints:   𝐸(𝑒,𝑓,𝑝)   𝑉(𝑓,𝑝)

Proof of Theorem 1pthon2v
Dummy variable 𝑖 is distinct from all other variables.
StepHypRef Expression
1 simpl 470 . . . . . . . 8 ((𝐴𝑉𝐵𝑉) → 𝐴𝑉)
21anim2i 605 . . . . . . 7 ((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉)) → (𝐺 ∈ UHGraph ∧ 𝐴𝑉))
323adant3 1155 . . . . . 6 ((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ ∃𝑒𝐸 {𝐴, 𝐵} ⊆ 𝑒) → (𝐺 ∈ UHGraph ∧ 𝐴𝑉))
43adantl 469 . . . . 5 ((𝐴 = 𝐵 ∧ (𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ ∃𝑒𝐸 {𝐴, 𝐵} ⊆ 𝑒)) → (𝐺 ∈ UHGraph ∧ 𝐴𝑉))
5 1pthon2v.v . . . . . . 7 𝑉 = (Vtx‘𝐺)
650pthonv 27300 . . . . . 6 (𝐴𝑉 → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐴)𝑝)
76adantl 469 . . . . 5 ((𝐺 ∈ UHGraph ∧ 𝐴𝑉) → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐴)𝑝)
84, 7syl 17 . . . 4 ((𝐴 = 𝐵 ∧ (𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ ∃𝑒𝐸 {𝐴, 𝐵} ⊆ 𝑒)) → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐴)𝑝)
9 oveq2 6880 . . . . . . . 8 (𝐵 = 𝐴 → (𝐴(PathsOn‘𝐺)𝐵) = (𝐴(PathsOn‘𝐺)𝐴))
109eqcoms 2812 . . . . . . 7 (𝐴 = 𝐵 → (𝐴(PathsOn‘𝐺)𝐵) = (𝐴(PathsOn‘𝐺)𝐴))
1110breqd 4853 . . . . . 6 (𝐴 = 𝐵 → (𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝𝑓(𝐴(PathsOn‘𝐺)𝐴)𝑝))
12112exbidv 2015 . . . . 5 (𝐴 = 𝐵 → (∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝 ↔ ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐴)𝑝))
1312adantr 468 . . . 4 ((𝐴 = 𝐵 ∧ (𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ ∃𝑒𝐸 {𝐴, 𝐵} ⊆ 𝑒)) → (∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝 ↔ ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐴)𝑝))
148, 13mpbird 248 . . 3 ((𝐴 = 𝐵 ∧ (𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ ∃𝑒𝐸 {𝐴, 𝐵} ⊆ 𝑒)) → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝)
1514ex 399 . 2 (𝐴 = 𝐵 → ((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ ∃𝑒𝐸 {𝐴, 𝐵} ⊆ 𝑒) → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝))
16 1pthon2v.e . . . . . . . . . . 11 𝐸 = (Edg‘𝐺)
1716eleq2i 2875 . . . . . . . . . 10 (𝑒𝐸𝑒 ∈ (Edg‘𝐺))
18 eqid 2804 . . . . . . . . . . 11 (iEdg‘𝐺) = (iEdg‘𝐺)
1918uhgredgiedgb 26233 . . . . . . . . . 10 (𝐺 ∈ UHGraph → (𝑒 ∈ (Edg‘𝐺) ↔ ∃𝑖 ∈ dom (iEdg‘𝐺)𝑒 = ((iEdg‘𝐺)‘𝑖)))
2017, 19syl5bb 274 . . . . . . . . 9 (𝐺 ∈ UHGraph → (𝑒𝐸 ↔ ∃𝑖 ∈ dom (iEdg‘𝐺)𝑒 = ((iEdg‘𝐺)‘𝑖)))
21203ad2ant1 1156 . . . . . . . 8 ((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) → (𝑒𝐸 ↔ ∃𝑖 ∈ dom (iEdg‘𝐺)𝑒 = ((iEdg‘𝐺)‘𝑖)))
22 s1cli 13598 . . . . . . . . . . . 12 ⟨“𝑖”⟩ ∈ Word V
23 s2cli 13847 . . . . . . . . . . . 12 ⟨“𝐴𝐵”⟩ ∈ Word V
2422, 23pm3.2i 458 . . . . . . . . . . 11 (⟨“𝑖”⟩ ∈ Word V ∧ ⟨“𝐴𝐵”⟩ ∈ Word V)
25 eqid 2804 . . . . . . . . . . . 12 ⟨“𝐴𝐵”⟩ = ⟨“𝐴𝐵”⟩
26 eqid 2804 . . . . . . . . . . . 12 ⟨“𝑖”⟩ = ⟨“𝑖”⟩
27 simpl2l 1290 . . . . . . . . . . . 12 (((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) ∧ ((𝑖 ∈ dom (iEdg‘𝐺) ∧ 𝑒 = ((iEdg‘𝐺)‘𝑖)) ∧ {𝐴, 𝐵} ⊆ 𝑒)) → 𝐴𝑉)
28 simpl2r 1292 . . . . . . . . . . . 12 (((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) ∧ ((𝑖 ∈ dom (iEdg‘𝐺) ∧ 𝑒 = ((iEdg‘𝐺)‘𝑖)) ∧ {𝐴, 𝐵} ⊆ 𝑒)) → 𝐵𝑉)
29 eqneqall 2987 . . . . . . . . . . . . . . . 16 (𝐴 = 𝐵 → (𝐴𝐵 → ((iEdg‘𝐺)‘𝑖) = {𝐴}))
3029com12 32 . . . . . . . . . . . . . . 15 (𝐴𝐵 → (𝐴 = 𝐵 → ((iEdg‘𝐺)‘𝑖) = {𝐴}))
31303ad2ant3 1158 . . . . . . . . . . . . . 14 ((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) → (𝐴 = 𝐵 → ((iEdg‘𝐺)‘𝑖) = {𝐴}))
3231adantr 468 . . . . . . . . . . . . 13 (((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) ∧ ((𝑖 ∈ dom (iEdg‘𝐺) ∧ 𝑒 = ((iEdg‘𝐺)‘𝑖)) ∧ {𝐴, 𝐵} ⊆ 𝑒)) → (𝐴 = 𝐵 → ((iEdg‘𝐺)‘𝑖) = {𝐴}))
3332imp 395 . . . . . . . . . . . 12 ((((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) ∧ ((𝑖 ∈ dom (iEdg‘𝐺) ∧ 𝑒 = ((iEdg‘𝐺)‘𝑖)) ∧ {𝐴, 𝐵} ⊆ 𝑒)) ∧ 𝐴 = 𝐵) → ((iEdg‘𝐺)‘𝑖) = {𝐴})
34 sseq2 3822 . . . . . . . . . . . . . . . 16 (𝑒 = ((iEdg‘𝐺)‘𝑖) → ({𝐴, 𝐵} ⊆ 𝑒 ↔ {𝐴, 𝐵} ⊆ ((iEdg‘𝐺)‘𝑖)))
3534adantl 469 . . . . . . . . . . . . . . 15 ((𝑖 ∈ dom (iEdg‘𝐺) ∧ 𝑒 = ((iEdg‘𝐺)‘𝑖)) → ({𝐴, 𝐵} ⊆ 𝑒 ↔ {𝐴, 𝐵} ⊆ ((iEdg‘𝐺)‘𝑖)))
3635biimpa 464 . . . . . . . . . . . . . 14 (((𝑖 ∈ dom (iEdg‘𝐺) ∧ 𝑒 = ((iEdg‘𝐺)‘𝑖)) ∧ {𝐴, 𝐵} ⊆ 𝑒) → {𝐴, 𝐵} ⊆ ((iEdg‘𝐺)‘𝑖))
3736adantl 469 . . . . . . . . . . . . 13 (((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) ∧ ((𝑖 ∈ dom (iEdg‘𝐺) ∧ 𝑒 = ((iEdg‘𝐺)‘𝑖)) ∧ {𝐴, 𝐵} ⊆ 𝑒)) → {𝐴, 𝐵} ⊆ ((iEdg‘𝐺)‘𝑖))
3837adantr 468 . . . . . . . . . . . 12 ((((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) ∧ ((𝑖 ∈ dom (iEdg‘𝐺) ∧ 𝑒 = ((iEdg‘𝐺)‘𝑖)) ∧ {𝐴, 𝐵} ⊆ 𝑒)) ∧ 𝐴𝐵) → {𝐴, 𝐵} ⊆ ((iEdg‘𝐺)‘𝑖))
3925, 26, 27, 28, 33, 38, 5, 181pthond 27315 . . . . . . . . . . 11 (((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) ∧ ((𝑖 ∈ dom (iEdg‘𝐺) ∧ 𝑒 = ((iEdg‘𝐺)‘𝑖)) ∧ {𝐴, 𝐵} ⊆ 𝑒)) → ⟨“𝑖”⟩(𝐴(PathsOn‘𝐺)𝐵)⟨“𝐴𝐵”⟩)
40 breq12 4847 . . . . . . . . . . . 12 ((𝑓 = ⟨“𝑖”⟩ ∧ 𝑝 = ⟨“𝐴𝐵”⟩) → (𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝 ↔ ⟨“𝑖”⟩(𝐴(PathsOn‘𝐺)𝐵)⟨“𝐴𝐵”⟩))
4140spc2egv 3486 . . . . . . . . . . 11 ((⟨“𝑖”⟩ ∈ Word V ∧ ⟨“𝐴𝐵”⟩ ∈ Word V) → (⟨“𝑖”⟩(𝐴(PathsOn‘𝐺)𝐵)⟨“𝐴𝐵”⟩ → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝))
4224, 39, 41mpsyl 68 . . . . . . . . . 10 (((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) ∧ ((𝑖 ∈ dom (iEdg‘𝐺) ∧ 𝑒 = ((iEdg‘𝐺)‘𝑖)) ∧ {𝐴, 𝐵} ⊆ 𝑒)) → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝)
4342exp44 426 . . . . . . . . 9 ((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) → (𝑖 ∈ dom (iEdg‘𝐺) → (𝑒 = ((iEdg‘𝐺)‘𝑖) → ({𝐴, 𝐵} ⊆ 𝑒 → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝))))
4443rexlimdv 3216 . . . . . . . 8 ((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) → (∃𝑖 ∈ dom (iEdg‘𝐺)𝑒 = ((iEdg‘𝐺)‘𝑖) → ({𝐴, 𝐵} ⊆ 𝑒 → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝)))
4521, 44sylbid 231 . . . . . . 7 ((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) → (𝑒𝐸 → ({𝐴, 𝐵} ⊆ 𝑒 → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝)))
4645rexlimdv 3216 . . . . . 6 ((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ 𝐴𝐵) → (∃𝑒𝐸 {𝐴, 𝐵} ⊆ 𝑒 → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝))
47463exp 1141 . . . . 5 (𝐺 ∈ UHGraph → ((𝐴𝑉𝐵𝑉) → (𝐴𝐵 → (∃𝑒𝐸 {𝐴, 𝐵} ⊆ 𝑒 → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝))))
4847com34 91 . . . 4 (𝐺 ∈ UHGraph → ((𝐴𝑉𝐵𝑉) → (∃𝑒𝐸 {𝐴, 𝐵} ⊆ 𝑒 → (𝐴𝐵 → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝))))
49483imp 1130 . . 3 ((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ ∃𝑒𝐸 {𝐴, 𝐵} ⊆ 𝑒) → (𝐴𝐵 → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝))
5049com12 32 . 2 (𝐴𝐵 → ((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ ∃𝑒𝐸 {𝐴, 𝐵} ⊆ 𝑒) → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝))
5115, 50pm2.61ine 3059 1 ((𝐺 ∈ UHGraph ∧ (𝐴𝑉𝐵𝑉) ∧ ∃𝑒𝐸 {𝐴, 𝐵} ⊆ 𝑒) → ∃𝑓𝑝 𝑓(𝐴(PathsOn‘𝐺)𝐵)𝑝)
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 197  wa 384  w3a 1100   = wceq 1637  wex 1859  wcel 2156  wne 2976  wrex 3095  Vcvv 3389  wss 3767  {csn 4368  {cpr 4370   class class class wbr 4842  dom cdm 5309  cfv 6099  (class class class)co 6872  Word cword 13500  ⟨“cs1 13503  ⟨“cs2 13808  Vtxcvtx 26086  iEdgciedg 26087  Edgcedg 26151  UHGraphcuhgr 26163  PathsOncpthson 26836
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1877  ax-4 1894  ax-5 2001  ax-6 2068  ax-7 2104  ax-8 2158  ax-9 2165  ax-10 2185  ax-11 2201  ax-12 2214  ax-13 2420  ax-ext 2782  ax-rep 4962  ax-sep 4973  ax-nul 4981  ax-pow 5033  ax-pr 5094  ax-un 7177  ax-cnex 10275  ax-resscn 10276  ax-1cn 10277  ax-icn 10278  ax-addcl 10279  ax-addrcl 10280  ax-mulcl 10281  ax-mulrcl 10282  ax-mulcom 10283  ax-addass 10284  ax-mulass 10285  ax-distr 10286  ax-i2m1 10287  ax-1ne0 10288  ax-1rid 10289  ax-rnegex 10290  ax-rrecex 10291  ax-cnre 10292  ax-pre-lttri 10293  ax-pre-lttrn 10294  ax-pre-ltadd 10295  ax-pre-mulgt0 10296
This theorem depends on definitions:  df-bi 198  df-an 385  df-or 866  df-ifp 1079  df-3or 1101  df-3an 1102  df-tru 1641  df-ex 1860  df-nf 1864  df-sb 2061  df-eu 2634  df-mo 2635  df-clab 2791  df-cleq 2797  df-clel 2800  df-nfc 2935  df-ne 2977  df-nel 3080  df-ral 3099  df-rex 3100  df-reu 3101  df-rab 3103  df-v 3391  df-sbc 3632  df-csb 3727  df-dif 3770  df-un 3772  df-in 3774  df-ss 3781  df-pss 3783  df-nul 4115  df-if 4278  df-pw 4351  df-sn 4369  df-pr 4371  df-tp 4373  df-op 4375  df-uni 4629  df-int 4668  df-iun 4712  df-br 4843  df-opab 4905  df-mpt 4922  df-tr 4945  df-id 5217  df-eprel 5222  df-po 5230  df-so 5231  df-fr 5268  df-we 5270  df-xp 5315  df-rel 5316  df-cnv 5317  df-co 5318  df-dm 5319  df-rn 5320  df-res 5321  df-ima 5322  df-pred 5891  df-ord 5937  df-on 5938  df-lim 5939  df-suc 5940  df-iota 6062  df-fun 6101  df-fn 6102  df-f 6103  df-f1 6104  df-fo 6105  df-f1o 6106  df-fv 6107  df-riota 6833  df-ov 6875  df-oprab 6876  df-mpt2 6877  df-om 7294  df-1st 7396  df-2nd 7397  df-wrecs 7640  df-recs 7702  df-rdg 7740  df-1o 7794  df-oadd 7798  df-er 7977  df-map 8092  df-pm 8093  df-en 8191  df-dom 8192  df-sdom 8193  df-fin 8194  df-card 9046  df-pnf 10359  df-mnf 10360  df-xr 10361  df-ltxr 10362  df-le 10363  df-sub 10551  df-neg 10552  df-nn 11304  df-2 11362  df-n0 11558  df-z 11642  df-uz 11903  df-fz 12548  df-fzo 12688  df-hash 13336  df-word 13508  df-concat 13510  df-s1 13511  df-s2 13815  df-edg 26152  df-uhgr 26165  df-wlks 26721  df-wlkson 26722  df-trls 26815  df-trlson 26816  df-pths 26838  df-pthson 26840
This theorem is referenced by:  1pthon2ve  27325  cusconngr  27362
  Copyright terms: Public domain W3C validator