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

Theorem iseupth 30859
Description: The property "⟨𝐹, 𝑃⟩ is an Eulerian path on the graph 𝐺". An Eulerian path is defined as bijection 𝐹 from the edges to a set 0...(𝑁 − 1) and a function 𝑃:(0...𝑁)⟶𝑉 into the vertices such that for each 0 ≤ 𝑘 < 𝑁, 𝐹(𝑘) is an edge from 𝑃(𝑘) to 𝑃(𝑘 + 1). (Since the edges are undirected and there are possibly many edges between any two given vertices, we need to list both the edges and the vertices of the path separately.) (Contributed by Mario Carneiro, 12-Mar-2015.) (Revised by Mario Carneiro, 3-May-2015.) (Revised by AV, 18-Feb-2021.) (Revised by AV, 30-Oct-2021.)
Hypothesis
Ref Expression
eupths.i 𝐼 = (iEdg‘𝐺)
Assertion
Ref Expression
iseupth (𝐹(EulerPaths‘𝐺)𝑃 ↔ (𝐹(Trails‘𝐺)𝑃 ∧ 𝐹:(0..^(♯‘𝐹))⟶ontodom 𝐼))

Proof of Theorem iseupth
Dummy variables 𝑓 𝑝 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 eupths.i . . 3 𝐼 = (iEdg‘𝐺)
21eupths 30858 . 2 (EulerPaths‘𝐺) = {⟨𝑓, 𝑝⟩ ∣ (𝑓(Trails‘𝐺)𝑝 ∧ 𝑓:(0..^(♯‘𝑓))⟶ontodom 𝐼)}
3 simpl 488 . . 3 ((𝑓 = 𝐹 ∧ 𝑝 = 𝑃) → 𝑓 = 𝐹)
4 fveq2 6916 . . . . 5 (𝑓 = 𝐹 → (♯‘𝑓) = (♯‘𝐹))
54oveq2d 7467 . . . 4 (𝑓 = 𝐹 → (0..^(♯‘𝑓)) = (0..^(♯‘𝐹)))
65adantr 486 . . 3 ((𝑓 = 𝐹 ∧ 𝑝 = 𝑃) → (0..^(♯‘𝑓)) = (0..^(♯‘𝐹)))
7 eqidd 2764 . . 3 ((𝑓 = 𝐹 ∧ 𝑝 = 𝑃) → dom 𝐼 = dom 𝐼)
83, 6, 7foeq123d 6847 . 2 ((𝑓 = 𝐹 ∧ 𝑝 = 𝑃) → (𝑓:(0..^(♯‘𝑓))⟶ontodom 𝐼 ↔ 𝐹:(0..^(♯‘𝐹))⟶ontodom 𝐼))
9 reltrls 30334 . 2 Rel (Trails‘𝐺)
102, 8, 9brfvopabrbr 7021 1 (𝐹(EulerPaths‘𝐺)𝑃 ↔ (𝐹(Trails‘𝐺)𝑃 ∧ 𝐹:(0..^(♯‘𝐹))⟶ontodom 𝐼))
Colors of variables:    wff setvar class
This proof depends on syntax axioms:   ↔ wb 209   ∧ wa 401   = wceq 1570   class class class wbr 5108  dom cdm 5658  ⟶ontowfo 6564  ‘cfv 6566  (class class class)co 7451  0cc0 11239  ..^cfzo 13828  ♯chash 14515  iEdgciedg 29632  Trailsctrls 30330  EulerPathsceupth 30855
This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1828  ax-4 1842  ax-5 1945  ax-6 2002  ax-7 2043  ax-8 2149  ax-9 2157  ax-10 2180  ax-11 2197  ax-12 2216  ax-ext 2735  ax-sep 5255  ax-nul 5266  ax-pr 5398
This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-3an 1105  df-tru 1573  df-fal 1583  df-ex 1813  df-nf 1817  df-sb 2102  df-mo 2567  df-eu 2597  df-clab 2742  df-cleq 2755  df-clel 2839  df-nfc 2913  df-ne 2960  df-ral 3081  df-rex 3091  df-rab 3417  df-v 3456  df-sbc 3743  df-csb 3852  df-ss 3901  df-dif 4050  df-in 4094  df-un 4154  df-nul 4282  df-if 4486  df-sn 4589  df-pr 4591  df-op 4841  df-uni 4873  df-br 5109  df-opab 5174  df-mpt 5193  df-id 5553  df-xp 5664  df-rel 5665  df-cnv 5666  df-co 5667  df-dm 5668  df-rn 5669  df-res 5670  df-ima 5671  df-iota 6520  df-fun 6568  df-fn 6569  df-fo 6572  df-fv 6574  df-ov 7454  df-trls 30332  df-eupth 30856
This theorem is used by:  iseupthf1o  30860  eupthistrl  30869  eucrctshift  30901
  Copyright terms: Public domain W3C validator