![]() |
Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > iseupthf1o | 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 |
---|---|
iseupthf1o | ⊢ (𝐹(EulerPaths‘𝐺)𝑃 ↔ (𝐹(Walks‘𝐺)𝑃 ∧ 𝐹:(0..^(♯‘𝐹))–1-1-onto→dom 𝐼)) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | eupths.i | . . 3 ⊢ 𝐼 = (iEdg‘𝐺) | |
2 | 1 | iseupth 28974 | . 2 ⊢ (𝐹(EulerPaths‘𝐺)𝑃 ↔ (𝐹(Trails‘𝐺)𝑃 ∧ 𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼)) |
3 | istrl 28473 | . . . 4 ⊢ (𝐹(Trails‘𝐺)𝑃 ↔ (𝐹(Walks‘𝐺)𝑃 ∧ Fun ◡𝐹)) | |
4 | 3 | anbi1i 625 | . . 3 ⊢ ((𝐹(Trails‘𝐺)𝑃 ∧ 𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼) ↔ ((𝐹(Walks‘𝐺)𝑃 ∧ Fun ◡𝐹) ∧ 𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼)) |
5 | anass 470 | . . 3 ⊢ (((𝐹(Walks‘𝐺)𝑃 ∧ Fun ◡𝐹) ∧ 𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼) ↔ (𝐹(Walks‘𝐺)𝑃 ∧ (Fun ◡𝐹 ∧ 𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼))) | |
6 | ancom 462 | . . . 4 ⊢ ((Fun ◡𝐹 ∧ 𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼) ↔ (𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼 ∧ Fun ◡𝐹)) | |
7 | 6 | anbi2i 624 | . . 3 ⊢ ((𝐹(Walks‘𝐺)𝑃 ∧ (Fun ◡𝐹 ∧ 𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼)) ↔ (𝐹(Walks‘𝐺)𝑃 ∧ (𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼 ∧ Fun ◡𝐹))) |
8 | 4, 5, 7 | 3bitri 297 | . 2 ⊢ ((𝐹(Trails‘𝐺)𝑃 ∧ 𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼) ↔ (𝐹(Walks‘𝐺)𝑃 ∧ (𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼 ∧ Fun ◡𝐹))) |
9 | dff1o3 6788 | . . . 4 ⊢ (𝐹:(0..^(♯‘𝐹))–1-1-onto→dom 𝐼 ↔ (𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼 ∧ Fun ◡𝐹)) | |
10 | 9 | bicomi 223 | . . 3 ⊢ ((𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼 ∧ Fun ◡𝐹) ↔ 𝐹:(0..^(♯‘𝐹))–1-1-onto→dom 𝐼) |
11 | 10 | anbi2i 624 | . 2 ⊢ ((𝐹(Walks‘𝐺)𝑃 ∧ (𝐹:(0..^(♯‘𝐹))–onto→dom 𝐼 ∧ Fun ◡𝐹)) ↔ (𝐹(Walks‘𝐺)𝑃 ∧ 𝐹:(0..^(♯‘𝐹))–1-1-onto→dom 𝐼)) |
12 | 2, 8, 11 | 3bitri 297 | 1 ⊢ (𝐹(EulerPaths‘𝐺)𝑃 ↔ (𝐹(Walks‘𝐺)𝑃 ∧ 𝐹:(0..^(♯‘𝐹))–1-1-onto→dom 𝐼)) |
Colors of variables: wff setvar class |
Syntax hints: ↔ wb 205 ∧ wa 397 = wceq 1542 class class class wbr 5104 ◡ccnv 5631 dom cdm 5632 Fun wfun 6488 –onto→wfo 6492 –1-1-onto→wf1o 6493 ‘cfv 6494 (class class class)co 7352 0cc0 11010 ..^cfzo 13522 ♯chash 14184 iEdgciedg 27777 Walkscwlks 28373 Trailsctrls 28467 EulerPathsceupth 28970 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1798 ax-4 1812 ax-5 1914 ax-6 1972 ax-7 2012 ax-8 2109 ax-9 2117 ax-10 2138 ax-11 2155 ax-12 2172 ax-ext 2709 ax-sep 5255 ax-nul 5262 ax-pr 5383 |
This theorem depends on definitions: df-bi 206 df-an 398 df-or 847 df-3an 1090 df-tru 1545 df-fal 1555 df-ex 1783 df-nf 1787 df-sb 2069 df-mo 2540 df-eu 2569 df-clab 2716 df-cleq 2730 df-clel 2816 df-nfc 2888 df-ne 2943 df-ral 3064 df-rex 3073 df-rab 3407 df-v 3446 df-sbc 3739 df-csb 3855 df-dif 3912 df-un 3914 df-in 3916 df-ss 3926 df-nul 4282 df-if 4486 df-sn 4586 df-pr 4588 df-op 4592 df-uni 4865 df-br 5105 df-opab 5167 df-mpt 5188 df-id 5530 df-xp 5638 df-rel 5639 df-cnv 5640 df-co 5641 df-dm 5642 df-rn 5643 df-res 5644 df-ima 5645 df-iota 6446 df-fun 6496 df-fn 6497 df-f 6498 df-f1 6499 df-fo 6500 df-f1o 6501 df-fv 6502 df-ov 7355 df-wlks 28376 df-trls 28469 df-eupth 28971 |
This theorem is referenced by: eupthi 28976 upgriseupth 28980 eupth0 28987 eupthres 28988 eupthp1 28989 |
Copyright terms: Public domain | W3C validator |