Theorem iseupth 16573

Description: The property " <. F , P >. is an Eulerian path on the graph G". An Eulerian path is defined as bijection F from the edges to a set 0 ... ( N - 1 ) and a function P : ( 0 ... N ) --> V into the vertices such that for each 0 <_ k < N, F ( k ) is an edge from P ( k ) to P ( k + 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
iseupth.i	|- I = (iEdg ` G )

Assertion

Ref	Expression
iseupth	|- ( F (EulerPaths ` G ) P <-> ( F (Trails ` G ) P /\ F : ( 0..^ (♯ ` F ) ) -onto-> dom I ) )

Proof of Theorem iseupth

Dummy variables f p are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		eupthv 16572	. 2 |- ( F (EulerPaths ` G ) P -> ( G e. _V /\ F e. _V /\ P e. _V ) )
2		trlsv 16510	. . 3 |- ( F (Trails ` G ) P -> ( G e. _V /\ F e. _V /\ P e. _V ) )
3	2	adantr 276	. 2 |- ( ( F (Trails ` G ) P /\ F : ( 0..^ (♯ ` F ) ) -onto-> dom I ) -> ( G e. _V /\ F e. _V /\ P e. _V ) )
4		df-br 4116	. . . 4 |- ( F (EulerPaths ` G ) P <-> <. F , P >. e. (EulerPaths ` G ) )
5		iseupth.i	. . . . . . 7 |- I = (iEdg ` G )
6	5	eupthsg 16571	. . . . . 6 |- ( G e. _V -> (EulerPaths ` G ) = { <. f , p >. | ( f (Trails ` G ) p /\ f : ( 0..^ (♯ ` f ) ) -onto-> dom I ) } )
7	6	3ad2ant1 1045	. . . . 5 |- ( ( G e. _V /\ F e. _V /\ P e. _V ) -> (EulerPaths ` G ) = { <. f , p >. | ( f (Trails ` G ) p /\ f : ( 0..^ (♯ ` f ) ) -onto-> dom I ) } )
8	7	eleq2d 2304	. . . 4 |- ( ( G e. _V /\ F e. _V /\ P e. _V ) -> ( <. F , P >. e. (EulerPaths ` G ) <-> <. F , P >. e. { <. f , p >. | ( f (Trails ` G ) p /\ f : ( 0..^ (♯ ` f ) ) -onto-> dom I ) } ) )
9	4, 8	bitrid 192	. . 3 |- ( ( G e. _V /\ F e. _V /\ P e. _V ) -> ( F (EulerPaths ` G ) P <-> <. F , P >. e. { <. f , p >. | ( f (Trails ` G ) p /\ f : ( 0..^ (♯ ` f ) ) -onto-> dom I ) } ) )
10		breq1 4118	. . . . . 6 |- ( f = F -> ( f (Trails ` G ) p <-> F (Trails ` G ) p ) )
11		id 19	. . . . . . 7 |- ( f = F -> f = F )
12		fveq2 5676	. . . . . . . 8 |- ( f = F -> (♯ ` f ) = (♯ ` F ) )
13	12	oveq2d 6075	. . . . . . 7 |- ( f = F -> ( 0..^ (♯ ` f ) ) = ( 0..^ (♯ ` F ) ) )
14		eqidd 2235	. . . . . . 7 |- ( f = F -> dom I = dom I )
15	11, 13, 14	foeq123d 5613	. . . . . 6 |- ( f = F -> ( f : ( 0..^ (♯ ` f ) ) -onto-> dom I <-> F : ( 0..^ (♯ ` F ) ) -onto-> dom I ) )
16	10, 15	anbi12d 473	. . . . 5 |- ( f = F -> ( ( f (Trails ` G ) p /\ f : ( 0..^ (♯ ` f ) ) -onto-> dom I ) <-> ( F (Trails ` G ) p /\ F : ( 0..^ (♯ ` F ) ) -onto-> dom I ) ) )
17		breq2 4119	. . . . . 6 |- ( p = P -> ( F (Trails ` G ) p <-> F (Trails ` G ) P ) )
18	17	anbi1d 465	. . . . 5 |- ( p = P -> ( ( F (Trails ` G ) p /\ F : ( 0..^ (♯ ` F ) ) -onto-> dom I ) <-> ( F (Trails ` G ) P /\ F : ( 0..^ (♯ ` F ) ) -onto-> dom I ) ) )
19	16, 18	opelopabg 4392	. . . 4 |- ( ( F e. _V /\ P e. _V ) -> ( <. F , P >. e. { <. f , p >. | ( f (Trails ` G ) p /\ f : ( 0..^ (♯ ` f ) ) -onto-> dom I ) } <-> ( F (Trails ` G ) P /\ F : ( 0..^ (♯ ` F ) ) -onto-> dom I ) ) )
20	19	3adant1 1042	. . 3 |- ( ( G e. _V /\ F e. _V /\ P e. _V ) -> ( <. F , P >. e. { <. f , p >. | ( f (Trails ` G ) p /\ f : ( 0..^ (♯ ` f ) ) -onto-> dom I ) } <-> ( F (Trails ` G ) P /\ F : ( 0..^ (♯ ` F ) ) -onto-> dom I ) ) )
21	9, 20	bitrd 188	. 2 |- ( ( G e. _V /\ F e. _V /\ P e. _V ) -> ( F (EulerPaths ` G ) P <-> ( F (Trails ` G ) P /\ F : ( 0..^ (♯ ` F ) ) -onto-> dom I ) ) )
22	1, 3, 21	pm5.21nii 712	1 |- ( F (EulerPaths ` G ) P <-> ( F (Trails ` G ) P /\ F : ( 0..^ (♯ ` F ) ) -onto-> dom I ) )

Syntax hints:   /\ wa 104   <-> wb 105   /\ w3a 1005   = wceq 1398   e. wcel 2205   _Vcvv 2815   <.cop 3698   class class class wbr 4115   {copab 4176   dom cdm 4755   -onto->wfo 5356   ` cfv 5358  (class class class)co 6059   0cc0 8144  ..^cfzo 10502  ♯chash 11167  iEdgciedg 16139  Trailsctrls 16506  EulerPathsceupth 16568

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 619  ax-in2 620  ax-io 717  ax-5 1496  ax-7 1497  ax-gen 1498  ax-ie1 1542  ax-ie2 1543  ax-8 1553  ax-10 1554  ax-11 1555  ax-i12 1556  ax-bndl 1558  ax-4 1559  ax-17 1575  ax-i9 1579  ax-ial 1583  ax-i5r 1584  ax-13 2207  ax-14 2208  ax-ext 2216  ax-coll 4231  ax-sep 4234  ax-nul 4242  ax-pow 4293  ax-pr 4328  ax-un 4560  ax-setind 4665  ax-iinf 4716  ax-cnex 8235  ax-resscn 8236  ax-1cn 8237  ax-1re 8238  ax-icn 8239  ax-addcl 8240  ax-addrcl 8241  ax-mulcl 8242  ax-addcom 8244  ax-mulcom 8245  ax-addass 8246  ax-mulass 8247  ax-distr 8248  ax-i2m1 8249  ax-0lt1 8250  ax-1rid 8251  ax-0id 8252  ax-rnegex 8253  ax-cnre 8255  ax-pre-ltirr 8256  ax-pre-ltwlin 8257  ax-pre-lttrn 8258  ax-pre-apti 8259  ax-pre-ltadd 8260

This theorem depends on definitions:  df-bi 117  df-dc 843  df-ifp 987  df-3or 1006  df-3an 1007  df-tru 1401  df-fal 1404  df-nf 1510  df-sb 1812  df-eu 2085  df-mo 2086  df-clab 2221  df-cleq 2227  df-clel 2230  df-nfc 2375  df-ne 2415  df-nel 2510  df-ral 2527  df-rex 2528  df-reu 2529  df-rab 2531  df-v 2817  df-sbc 3046  df-csb 3142  df-dif 3216  df-un 3218  df-in 3220  df-ss 3227  df-nul 3513  df-if 3626  df-pw 3677  df-sn 3701  df-pr 3702  df-op 3704  df-uni 3921  df-int 3956  df-iun 3999  df-br 4116  df-opab 4178  df-mpt 4179  df-tr 4215  df-id 4420  df-iord 4493  df-on 4495  df-ilim 4496  df-suc 4498  df-iom 4719  df-xp 4761  df-rel 4762  df-cnv 4763  df-co 4764  df-dm 4765  df-rn 4766  df-res 4767  df-ima 4768  df-iota 5318  df-fun 5360  df-fn 5361  df-f 5362  df-f1 5363  df-fo 5364  df-f1o 5365  df-fv 5366  df-riota 6012  df-ov 6062  df-oprab 6063  df-mpo 6064  df-1st 6348  df-2nd 6349  df-recs 6550  df-frec 6636  df-1o 6661  df-er 6781  df-map 6898  df-en 6990  df-dom 6991  df-fin 6992  df-pnf 8327  df-mnf 8328  df-xr 8329  df-ltxr 8330  df-le 8331  df-sub 8464  df-neg 8465  df-inn 9259  df-2 9317  df-3 9318  df-4 9319  df-5 9320  df-6 9321  df-7 9322  df-8 9323  df-9 9324  df-n0 9518  df-z 9599  df-dec 9732  df-uz 9876  df-fz 10366  df-fzo 10503  df-ihash 11168  df-word 11254  df-ndx 13304  df-slot 13305  df-base 13307  df-edgf 16131  df-vtx 16140  df-iedg 16141  df-wlks 16444  df-trls 16507  df-eupth 16569

This theorem is referenced by:  iseupthf1o  16574  eupthfi  16577  eupthistrl  16580