![]() |
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 30055 | . 2 โข (๐น(EulerPathsโ๐บ)๐ โ (๐น(Trailsโ๐บ)๐ โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ)) |
3 | istrl 29554 | . . . 4 โข (๐น(Trailsโ๐บ)๐ โ (๐น(Walksโ๐บ)๐ โง Fun โก๐น)) | |
4 | 3 | anbi1i 622 | . . 3 โข ((๐น(Trailsโ๐บ)๐ โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ) โ ((๐น(Walksโ๐บ)๐ โง Fun โก๐น) โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ)) |
5 | anass 467 | . . 3 โข (((๐น(Walksโ๐บ)๐ โง Fun โก๐น) โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ) โ (๐น(Walksโ๐บ)๐ โง (Fun โก๐น โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ))) | |
6 | ancom 459 | . . . 4 โข ((Fun โก๐น โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ) โ (๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ โง Fun โก๐น)) | |
7 | 6 | anbi2i 621 | . . 3 โข ((๐น(Walksโ๐บ)๐ โง (Fun โก๐น โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ)) โ (๐น(Walksโ๐บ)๐ โง (๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ โง Fun โก๐น))) |
8 | 4, 5, 7 | 3bitri 296 | . 2 โข ((๐น(Trailsโ๐บ)๐ โง ๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ) โ (๐น(Walksโ๐บ)๐ โง (๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ โง Fun โก๐น))) |
9 | dff1o3 6840 | . . . 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 621 | . 2 โข ((๐น(Walksโ๐บ)๐ โง (๐น:(0..^(โฏโ๐น))โontoโdom ๐ผ โง Fun โก๐น)) โ (๐น(Walksโ๐บ)๐ โง ๐น:(0..^(โฏโ๐น))โ1-1-ontoโdom ๐ผ)) |
12 | 2, 8, 11 | 3bitri 296 | 1 โข (๐น(EulerPathsโ๐บ)๐ โ (๐น(Walksโ๐บ)๐ โง ๐น:(0..^(โฏโ๐น))โ1-1-ontoโdom ๐ผ)) |
Colors of variables: wff setvar class |
Syntax hints: โ wb 205 โง wa 394 = wceq 1533 class class class wbr 5143 โกccnv 5671 dom cdm 5672 Fun wfun 6537 โontoโwfo 6541 โ1-1-ontoโwf1o 6542 โcfv 6543 (class class class)co 7416 0cc0 11138 ..^cfzo 13659 โฏchash 14321 iEdgciedg 28854 Walkscwlks 29454 Trailsctrls 29548 EulerPathsceupth 30051 |
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 2696 ax-sep 5294 ax-nul 5301 ax-pr 5423 |
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 2528 df-eu 2557 df-clab 2703 df-cleq 2717 df-clel 2802 df-nfc 2877 df-ne 2931 df-ral 3052 df-rex 3061 df-rab 3420 df-v 3465 df-sbc 3769 df-csb 3885 df-dif 3942 df-un 3944 df-in 3946 df-ss 3956 df-nul 4319 df-if 4525 df-sn 4625 df-pr 4627 df-op 4631 df-uni 4904 df-br 5144 df-opab 5206 df-mpt 5227 df-id 5570 df-xp 5678 df-rel 5679 df-cnv 5680 df-co 5681 df-dm 5682 df-rn 5683 df-res 5684 df-ima 5685 df-iota 6495 df-fun 6545 df-fn 6546 df-f 6547 df-f1 6548 df-fo 6549 df-f1o 6550 df-fv 6551 df-ov 7419 df-wlks 29457 df-trls 29550 df-eupth 30052 |
This theorem is referenced by: eupthi 30057 upgriseupth 30061 eupth0 30068 eupthres 30069 eupthp1 30070 |
Copyright terms: Public domain | W3C validator |