![]() |
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 29963 | . 2 โข (๐น(EulerPathsโ๐บ)๐ โ (๐น(Trailsโ๐บ)๐ โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ)) |
3 | istrl 29462 | . . . 4 โข (๐น(Trailsโ๐บ)๐ โ (๐น(Walksโ๐บ)๐ โง Fun โก๐น)) | |
4 | 3 | anbi1i 623 | . . 3 โข ((๐น(Trailsโ๐บ)๐ โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ) โ ((๐น(Walksโ๐บ)๐ โง Fun โก๐น) โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ)) |
5 | anass 468 | . . 3 โข (((๐น(Walksโ๐บ)๐ โง Fun โก๐น) โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ) โ (๐น(Walksโ๐บ)๐ โง (Fun โก๐น โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ))) | |
6 | ancom 460 | . . . 4 โข ((Fun โก๐น โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ) โ (๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ โง Fun โก๐น)) | |
7 | 6 | anbi2i 622 | . . 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 6833 | . . . 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 622 | . 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 395 = wceq 1533 class class class wbr 5141 โกccnv 5668 dom cdm 5669 Fun wfun 6531 โontoโwfo 6535 โ1-1-ontoโwf1o 6536 โcfv 6537 (class class class)co 7405 0cc0 11112 ..^cfzo 13633 โฏchash 14295 iEdgciedg 28765 Walkscwlks 29362 Trailsctrls 29456 EulerPathsceupth 29959 |
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 2163 ax-ext 2697 ax-sep 5292 ax-nul 5299 ax-pr 5420 |
This theorem depends on definitions: df-bi 206 df-an 396 df-or 845 df-3an 1086 df-tru 1536 df-fal 1546 df-ex 1774 df-nf 1778 df-sb 2060 df-mo 2528 df-eu 2557 df-clab 2704 df-cleq 2718 df-clel 2804 df-nfc 2879 df-ne 2935 df-ral 3056 df-rex 3065 df-rab 3427 df-v 3470 df-sbc 3773 df-csb 3889 df-dif 3946 df-un 3948 df-in 3950 df-ss 3960 df-nul 4318 df-if 4524 df-sn 4624 df-pr 4626 df-op 4630 df-uni 4903 df-br 5142 df-opab 5204 df-mpt 5225 df-id 5567 df-xp 5675 df-rel 5676 df-cnv 5677 df-co 5678 df-dm 5679 df-rn 5680 df-res 5681 df-ima 5682 df-iota 6489 df-fun 6539 df-fn 6540 df-f 6541 df-f1 6542 df-fo 6543 df-f1o 6544 df-fv 6545 df-ov 7408 df-wlks 29365 df-trls 29458 df-eupth 29960 |
This theorem is referenced by: eupthi 29965 upgriseupth 29969 eupth0 29976 eupthres 29977 eupthp1 29978 |
Copyright terms: Public domain | W3C validator |