![]() |
Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > iseupth | Structured version Visualization version GIF version |
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.) |
Ref | Expression |
---|---|
eupths.i | β’ πΌ = (iEdgβπΊ) |
Ref | Expression |
---|---|
iseupth | β’ (πΉ(EulerPathsβπΊ)π β (πΉ(TrailsβπΊ)π β§ πΉ:(0..^(β―βπΉ))βontoβdom πΌ)) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | eupths.i | . . 3 β’ πΌ = (iEdgβπΊ) | |
2 | 1 | eupths 30028 | . 2 β’ (EulerPathsβπΊ) = {β¨π, πβ© β£ (π(TrailsβπΊ)π β§ π:(0..^(β―βπ))βontoβdom πΌ)} |
3 | simpl 481 | . . 3 β’ ((π = πΉ β§ π = π) β π = πΉ) | |
4 | fveq2 6900 | . . . . 5 β’ (π = πΉ β (β―βπ) = (β―βπΉ)) | |
5 | 4 | oveq2d 7440 | . . . 4 β’ (π = πΉ β (0..^(β―βπ)) = (0..^(β―βπΉ))) |
6 | 5 | adantr 479 | . . 3 β’ ((π = πΉ β§ π = π) β (0..^(β―βπ)) = (0..^(β―βπΉ))) |
7 | eqidd 2728 | . . 3 β’ ((π = πΉ β§ π = π) β dom πΌ = dom πΌ) | |
8 | 3, 6, 7 | foeq123d 6835 | . 2 β’ ((π = πΉ β§ π = π) β (π:(0..^(β―βπ))βontoβdom πΌ β πΉ:(0..^(β―βπΉ))βontoβdom πΌ)) |
9 | reltrls 29526 | . 2 β’ Rel (TrailsβπΊ) | |
10 | 2, 8, 9 | brfvopabrbr 7005 | 1 β’ (πΉ(EulerPathsβπΊ)π β (πΉ(TrailsβπΊ)π β§ πΉ:(0..^(β―βπΉ))βontoβdom πΌ)) |
Colors of variables: wff setvar class |
Syntax hints: β wb 205 β§ wa 394 = wceq 1533 class class class wbr 5150 dom cdm 5680 βontoβwfo 6549 βcfv 6551 (class class class)co 7424 0cc0 11144 ..^cfzo 13665 β―chash 14327 iEdgciedg 28828 Trailsctrls 29522 EulerPathsceupth 30025 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1789 ax-4 1803 ax-5 1905 ax-6 1963 ax-7 2003 ax-8 2100 ax-9 2108 ax-10 2129 ax-11 2146 ax-12 2166 ax-ext 2698 ax-sep 5301 ax-nul 5308 ax-pr 5431 |
This theorem depends on definitions: df-bi 206 df-an 395 df-or 846 df-3an 1086 df-tru 1536 df-fal 1546 df-ex 1774 df-nf 1778 df-sb 2060 df-mo 2529 df-eu 2558 df-clab 2705 df-cleq 2719 df-clel 2805 df-nfc 2880 df-ne 2937 df-ral 3058 df-rex 3067 df-rab 3429 df-v 3473 df-sbc 3777 df-csb 3893 df-dif 3950 df-un 3952 df-in 3954 df-ss 3964 df-nul 4325 df-if 4531 df-sn 4631 df-pr 4633 df-op 4637 df-uni 4911 df-br 5151 df-opab 5213 df-mpt 5234 df-id 5578 df-xp 5686 df-rel 5687 df-cnv 5688 df-co 5689 df-dm 5690 df-rn 5691 df-res 5692 df-ima 5693 df-iota 6503 df-fun 6553 df-fn 6554 df-fo 6557 df-fv 6559 df-ov 7427 df-trls 29524 df-eupth 30026 |
This theorem is referenced by: iseupthf1o 30030 eupthistrl 30039 eucrctshift 30071 |
Copyright terms: Public domain | W3C validator |