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

Theorem conngrv2edg 28135
Description: A vertex in a connected graph with more than one vertex is incident with at least one edge. Formerly part of proof for vdgn0frgrv2 28235. (Contributed by Alexander van der Vekens, 9-Dec-2017.) (Revised by AV, 4-Apr-2021.)
Hypotheses
Ref Expression
conngrv2edg.v 𝑉 = (Vtx‘𝐺)
conngrv2edg.i 𝐼 = (iEdg‘𝐺)
Assertion
Ref Expression
conngrv2edg ((𝐺 ∈ ConnGraph ∧ 𝑁𝑉 ∧ 1 < (♯‘𝑉)) → ∃𝑒 ∈ ran 𝐼 𝑁𝑒)
Distinct variable groups:   𝑒,𝐺   𝑒,𝐼   𝑒,𝑁
Allowed substitution hint:   𝑉(𝑒)

Proof of Theorem conngrv2edg
Dummy variables 𝑎 𝑏 𝑓 𝑝 𝑣 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 conngrv2edg.v . . . 4 𝑉 = (Vtx‘𝐺)
21fvexi 6691 . . 3 𝑉 ∈ V
3 simp3 1139 . . 3 ((𝐺 ∈ ConnGraph ∧ 𝑁𝑉 ∧ 1 < (♯‘𝑉)) → 1 < (♯‘𝑉))
4 simp2 1138 . . 3 ((𝐺 ∈ ConnGraph ∧ 𝑁𝑉 ∧ 1 < (♯‘𝑉)) → 𝑁𝑉)
5 hashgt12el2 13879 . . 3 ((𝑉 ∈ V ∧ 1 < (♯‘𝑉) ∧ 𝑁𝑉) → ∃𝑣𝑉 𝑁𝑣)
62, 3, 4, 5mp3an2i 1467 . 2 ((𝐺 ∈ ConnGraph ∧ 𝑁𝑉 ∧ 1 < (♯‘𝑉)) → ∃𝑣𝑉 𝑁𝑣)
71isconngr 28129 . . . . . . . 8 (𝐺 ∈ ConnGraph → (𝐺 ∈ ConnGraph ↔ ∀𝑎𝑉𝑏𝑉𝑓𝑝 𝑓(𝑎(PathsOn‘𝐺)𝑏)𝑝))
8 oveq1 7180 . . . . . . . . . . . . 13 (𝑎 = 𝑁 → (𝑎(PathsOn‘𝐺)𝑏) = (𝑁(PathsOn‘𝐺)𝑏))
98breqd 5042 . . . . . . . . . . . 12 (𝑎 = 𝑁 → (𝑓(𝑎(PathsOn‘𝐺)𝑏)𝑝𝑓(𝑁(PathsOn‘𝐺)𝑏)𝑝))
1092exbidv 1931 . . . . . . . . . . 11 (𝑎 = 𝑁 → (∃𝑓𝑝 𝑓(𝑎(PathsOn‘𝐺)𝑏)𝑝 ↔ ∃𝑓𝑝 𝑓(𝑁(PathsOn‘𝐺)𝑏)𝑝))
11 oveq2 7181 . . . . . . . . . . . . 13 (𝑏 = 𝑣 → (𝑁(PathsOn‘𝐺)𝑏) = (𝑁(PathsOn‘𝐺)𝑣))
1211breqd 5042 . . . . . . . . . . . 12 (𝑏 = 𝑣 → (𝑓(𝑁(PathsOn‘𝐺)𝑏)𝑝𝑓(𝑁(PathsOn‘𝐺)𝑣)𝑝))
13122exbidv 1931 . . . . . . . . . . 11 (𝑏 = 𝑣 → (∃𝑓𝑝 𝑓(𝑁(PathsOn‘𝐺)𝑏)𝑝 ↔ ∃𝑓𝑝 𝑓(𝑁(PathsOn‘𝐺)𝑣)𝑝))
1410, 13rspc2v 3537 . . . . . . . . . 10 ((𝑁𝑉𝑣𝑉) → (∀𝑎𝑉𝑏𝑉𝑓𝑝 𝑓(𝑎(PathsOn‘𝐺)𝑏)𝑝 → ∃𝑓𝑝 𝑓(𝑁(PathsOn‘𝐺)𝑣)𝑝))
1514ad2ant2r 747 . . . . . . . . 9 (((𝑁𝑉 ∧ 1 < (♯‘𝑉)) ∧ (𝑣𝑉𝑁𝑣)) → (∀𝑎𝑉𝑏𝑉𝑓𝑝 𝑓(𝑎(PathsOn‘𝐺)𝑏)𝑝 → ∃𝑓𝑝 𝑓(𝑁(PathsOn‘𝐺)𝑣)𝑝))
16 pthontrlon 27691 . . . . . . . . . . . 12 (𝑓(𝑁(PathsOn‘𝐺)𝑣)𝑝𝑓(𝑁(TrailsOn‘𝐺)𝑣)𝑝)
17 trlsonwlkon 27654 . . . . . . . . . . . 12 (𝑓(𝑁(TrailsOn‘𝐺)𝑣)𝑝𝑓(𝑁(WalksOn‘𝐺)𝑣)𝑝)
18 simpl 486 . . . . . . . . . . . . . 14 ((𝑓(𝑁(WalksOn‘𝐺)𝑣)𝑝 ∧ ((𝑁𝑉 ∧ 1 < (♯‘𝑉)) ∧ (𝑣𝑉𝑁𝑣))) → 𝑓(𝑁(WalksOn‘𝐺)𝑣)𝑝)
19 simprr 773 . . . . . . . . . . . . . . 15 (((𝑁𝑉 ∧ 1 < (♯‘𝑉)) ∧ (𝑣𝑉𝑁𝑣)) → 𝑁𝑣)
20 wlkon2n0 27611 . . . . . . . . . . . . . . 15 ((𝑓(𝑁(WalksOn‘𝐺)𝑣)𝑝𝑁𝑣) → (♯‘𝑓) ≠ 0)
2119, 20sylan2 596 . . . . . . . . . . . . . 14 ((𝑓(𝑁(WalksOn‘𝐺)𝑣)𝑝 ∧ ((𝑁𝑉 ∧ 1 < (♯‘𝑉)) ∧ (𝑣𝑉𝑁𝑣))) → (♯‘𝑓) ≠ 0)
2218, 21jca 515 . . . . . . . . . . . . 13 ((𝑓(𝑁(WalksOn‘𝐺)𝑣)𝑝 ∧ ((𝑁𝑉 ∧ 1 < (♯‘𝑉)) ∧ (𝑣𝑉𝑁𝑣))) → (𝑓(𝑁(WalksOn‘𝐺)𝑣)𝑝 ∧ (♯‘𝑓) ≠ 0))
2322ex 416 . . . . . . . . . . . 12 (𝑓(𝑁(WalksOn‘𝐺)𝑣)𝑝 → (((𝑁𝑉 ∧ 1 < (♯‘𝑉)) ∧ (𝑣𝑉𝑁𝑣)) → (𝑓(𝑁(WalksOn‘𝐺)𝑣)𝑝 ∧ (♯‘𝑓) ≠ 0)))
2416, 17, 233syl 18 . . . . . . . . . . 11 (𝑓(𝑁(PathsOn‘𝐺)𝑣)𝑝 → (((𝑁𝑉 ∧ 1 < (♯‘𝑉)) ∧ (𝑣𝑉𝑁𝑣)) → (𝑓(𝑁(WalksOn‘𝐺)𝑣)𝑝 ∧ (♯‘𝑓) ≠ 0)))
25 conngrv2edg.i . . . . . . . . . . . 12 𝐼 = (iEdg‘𝐺)
2625wlkonl1iedg 27610 . . . . . . . . . . 11 ((𝑓(𝑁(WalksOn‘𝐺)𝑣)𝑝 ∧ (♯‘𝑓) ≠ 0) → ∃𝑒 ∈ ran 𝐼 𝑁𝑒)
2724, 26syl6com 37 . . . . . . . . . 10 (((𝑁𝑉 ∧ 1 < (♯‘𝑉)) ∧ (𝑣𝑉𝑁𝑣)) → (𝑓(𝑁(PathsOn‘𝐺)𝑣)𝑝 → ∃𝑒 ∈ ran 𝐼 𝑁𝑒))
2827exlimdvv 1941 . . . . . . . . 9 (((𝑁𝑉 ∧ 1 < (♯‘𝑉)) ∧ (𝑣𝑉𝑁𝑣)) → (∃𝑓𝑝 𝑓(𝑁(PathsOn‘𝐺)𝑣)𝑝 → ∃𝑒 ∈ ran 𝐼 𝑁𝑒))
2915, 28syldc 48 . . . . . . . 8 (∀𝑎𝑉𝑏𝑉𝑓𝑝 𝑓(𝑎(PathsOn‘𝐺)𝑏)𝑝 → (((𝑁𝑉 ∧ 1 < (♯‘𝑉)) ∧ (𝑣𝑉𝑁𝑣)) → ∃𝑒 ∈ ran 𝐼 𝑁𝑒))
307, 29syl6bi 256 . . . . . . 7 (𝐺 ∈ ConnGraph → (𝐺 ∈ ConnGraph → (((𝑁𝑉 ∧ 1 < (♯‘𝑉)) ∧ (𝑣𝑉𝑁𝑣)) → ∃𝑒 ∈ ran 𝐼 𝑁𝑒)))
3130pm2.43i 52 . . . . . 6 (𝐺 ∈ ConnGraph → (((𝑁𝑉 ∧ 1 < (♯‘𝑉)) ∧ (𝑣𝑉𝑁𝑣)) → ∃𝑒 ∈ ran 𝐼 𝑁𝑒))
3231expd 419 . . . . 5 (𝐺 ∈ ConnGraph → ((𝑁𝑉 ∧ 1 < (♯‘𝑉)) → ((𝑣𝑉𝑁𝑣) → ∃𝑒 ∈ ran 𝐼 𝑁𝑒)))
33323impib 1117 . . . 4 ((𝐺 ∈ ConnGraph ∧ 𝑁𝑉 ∧ 1 < (♯‘𝑉)) → ((𝑣𝑉𝑁𝑣) → ∃𝑒 ∈ ran 𝐼 𝑁𝑒))
3433expd 419 . . 3 ((𝐺 ∈ ConnGraph ∧ 𝑁𝑉 ∧ 1 < (♯‘𝑉)) → (𝑣𝑉 → (𝑁𝑣 → ∃𝑒 ∈ ran 𝐼 𝑁𝑒)))
3534rexlimdv 3194 . 2 ((𝐺 ∈ ConnGraph ∧ 𝑁𝑉 ∧ 1 < (♯‘𝑉)) → (∃𝑣𝑉 𝑁𝑣 → ∃𝑒 ∈ ran 𝐼 𝑁𝑒))
366, 35mpd 15 1 ((𝐺 ∈ ConnGraph ∧ 𝑁𝑉 ∧ 1 < (♯‘𝑉)) → ∃𝑒 ∈ ran 𝐼 𝑁𝑒)
Colors of variables: wff setvar class
Syntax hints:  wi 4  wa 399  w3a 1088   = wceq 1542  wex 1786  wcel 2114  wne 2935  wral 3054  wrex 3055  Vcvv 3399   class class class wbr 5031  ran crn 5527  cfv 6340  (class class class)co 7173  0cc0 10618  1c1 10619   < clt 10756  chash 13785  Vtxcvtx 26944  iEdgciedg 26945  WalksOncwlkson 27542  TrailsOnctrlson 27636  PathsOncpthson 27658  ConnGraphcconngr 28126
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1802  ax-4 1816  ax-5 1917  ax-6 1975  ax-7 2020  ax-8 2116  ax-9 2124  ax-10 2145  ax-11 2162  ax-12 2179  ax-ext 2711  ax-rep 5155  ax-sep 5168  ax-nul 5175  ax-pow 5233  ax-pr 5297  ax-un 7482  ax-cnex 10674  ax-resscn 10675  ax-1cn 10676  ax-icn 10677  ax-addcl 10678  ax-addrcl 10679  ax-mulcl 10680  ax-mulrcl 10681  ax-mulcom 10682  ax-addass 10683  ax-mulass 10684  ax-distr 10685  ax-i2m1 10686  ax-1ne0 10687  ax-1rid 10688  ax-rnegex 10689  ax-rrecex 10690  ax-cnre 10691  ax-pre-lttri 10692  ax-pre-lttrn 10693  ax-pre-ltadd 10694  ax-pre-mulgt0 10695
This theorem depends on definitions:  df-bi 210  df-an 400  df-or 847  df-ifp 1063  df-3or 1089  df-3an 1090  df-tru 1545  df-fal 1555  df-ex 1787  df-nf 1791  df-sb 2075  df-mo 2541  df-eu 2571  df-clab 2718  df-cleq 2731  df-clel 2812  df-nfc 2882  df-ne 2936  df-nel 3040  df-ral 3059  df-rex 3060  df-reu 3061  df-rab 3063  df-v 3401  df-sbc 3682  df-csb 3792  df-dif 3847  df-un 3849  df-in 3851  df-ss 3861  df-pss 3863  df-nul 4213  df-if 4416  df-pw 4491  df-sn 4518  df-pr 4520  df-tp 4522  df-op 4524  df-uni 4798  df-int 4838  df-iun 4884  df-br 5032  df-opab 5094  df-mpt 5112  df-tr 5138  df-id 5430  df-eprel 5435  df-po 5443  df-so 5444  df-fr 5484  df-we 5486  df-xp 5532  df-rel 5533  df-cnv 5534  df-co 5535  df-dm 5536  df-rn 5537  df-res 5538  df-ima 5539  df-pred 6130  df-ord 6176  df-on 6177  df-lim 6178  df-suc 6179  df-iota 6298  df-fun 6342  df-fn 6343  df-f 6344  df-f1 6345  df-fo 6346  df-f1o 6347  df-fv 6348  df-riota 7130  df-ov 7176  df-oprab 7177  df-mpo 7178  df-om 7603  df-1st 7717  df-2nd 7718  df-wrecs 7979  df-recs 8040  df-rdg 8078  df-1o 8134  df-er 8323  df-map 8442  df-en 8559  df-dom 8560  df-sdom 8561  df-fin 8562  df-card 9444  df-pnf 10758  df-mnf 10759  df-xr 10760  df-ltxr 10761  df-le 10762  df-sub 10953  df-neg 10954  df-nn 11720  df-n0 11980  df-xnn0 12052  df-z 12066  df-uz 12328  df-fz 12985  df-fzo 13128  df-hash 13786  df-word 13959  df-wlks 27544  df-wlkson 27545  df-trls 27637  df-trlson 27638  df-pths 27660  df-pthson 27662  df-conngr 28127
This theorem is referenced by:  vdn0conngrumgrv2  28136
  Copyright terms: Public domain W3C validator