Metamath Proof Explorer < Previous   Next > Nearby theorems Mirrors  >  Home  >  MPE Home  >  Th. List  >  eupath2 Structured version   Unicode version

Theorem eupath2 21695
 Description: The only vertices of odd degree in a graph with an Eulerian path are the endpoints, and then only if the endpoints are distinct. (Contributed by Mario Carneiro, 8-Apr-2015.)
Hypotheses
Ref Expression
eupath2.1
eupath2.3 EulPaths
Assertion
Ref Expression
eupath2 VDeg
Distinct variable groups:   ,   ,   ,   ,
Allowed substitution hints:   ()   ()

Proof of Theorem eupath2
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 eupath2.3 . . . . . . . . . . 11 EulPaths
2 eupath2.1 . . . . . . . . . . 11
3 eupaf1o 21685 . . . . . . . . . . 11 EulPaths
41, 2, 3syl2anc 643 . . . . . . . . . 10
5 f1ofo 5674 . . . . . . . . . 10
6 foima 5651 . . . . . . . . . 10
74, 5, 63syl 19 . . . . . . . . 9
87reseq2d 5139 . . . . . . . 8
9 fnresdm 5547 . . . . . . . . 9
102, 9syl 16 . . . . . . . 8
118, 10eqtrd 2468 . . . . . . 7
1211oveq2d 6090 . . . . . 6 VDeg VDeg
1312fveq1d 5723 . . . . 5 VDeg VDeg
1413breq2d 4217 . . . 4 VDeg VDeg
1514notbid 286 . . 3 VDeg VDeg
1615rabbidv 2941 . 2 VDeg VDeg
17 eupacl 21684 . . . . 5 EulPaths
18 nn0re 10223 . . . . 5
191, 17, 183syl 19 . . . 4
2019leidd 9586 . . 3
211, 17syl 16 . . . 4
22 breq1 4208 . . . . . . 7
23 oveq2 6082 . . . . . . . . . . . . . . . . . 18
24 fz10 11068 . . . . . . . . . . . . . . . . . 18
2523, 24syl6eq 2484 . . . . . . . . . . . . . . . . 17
2625imaeq2d 5196 . . . . . . . . . . . . . . . 16
27 ima0 5214 . . . . . . . . . . . . . . . 16
2826, 27syl6eq 2484 . . . . . . . . . . . . . . 15
2928reseq2d 5139 . . . . . . . . . . . . . 14
30 res0 5143 . . . . . . . . . . . . . 14
3129, 30syl6eq 2484 . . . . . . . . . . . . 13
3231oveq2d 6090 . . . . . . . . . . . 12 VDeg VDeg
3332fveq1d 5723 . . . . . . . . . . 11 VDeg VDeg
3433breq2d 4217 . . . . . . . . . 10 VDeg VDeg
3534notbid 286 . . . . . . . . 9 VDeg VDeg
3635rabbidv 2941 . . . . . . . 8 VDeg VDeg
37 fveq2 5721 . . . . . . . . . 10
3837eqcomd 2441 . . . . . . . . 9
39 iftrue 3738 . . . . . . . . 9
4038, 39syl 16 . . . . . . . 8
4136, 40eqeq12d 2450 . . . . . . 7 VDeg VDeg
4222, 41imbi12d 312 . . . . . 6 VDeg VDeg
4342imbi2d 308 . . . . 5 VDeg VDeg
44 breq1 4208 . . . . . . 7
45 oveq2 6082 . . . . . . . . . . . . . . 15
4645imaeq2d 5196 . . . . . . . . . . . . . 14
4746reseq2d 5139 . . . . . . . . . . . . 13
4847oveq2d 6090 . . . . . . . . . . . 12 VDeg VDeg
4948fveq1d 5723 . . . . . . . . . . 11 VDeg VDeg
5049breq2d 4217 . . . . . . . . . 10 VDeg VDeg
5150notbid 286 . . . . . . . . 9 VDeg VDeg
5251rabbidv 2941 . . . . . . . 8 VDeg VDeg
53 fveq2 5721 . . . . . . . . . 10
5453eqeq2d 2447 . . . . . . . . 9
5553preq2d 3883 . . . . . . . . 9
5654, 55ifbieq2d 3752 . . . . . . . 8
5752, 56eqeq12d 2450 . . . . . . 7 VDeg VDeg
5844, 57imbi12d 312 . . . . . 6 VDeg VDeg
5958imbi2d 308 . . . . 5 VDeg VDeg
60 breq1 4208 . . . . . . 7
61 oveq2 6082 . . . . . . . . . . . . . . 15
6261imaeq2d 5196 . . . . . . . . . . . . . 14
6362reseq2d 5139 . . . . . . . . . . . . 13
6463oveq2d 6090 . . . . . . . . . . . 12 VDeg VDeg
6564fveq1d 5723 . . . . . . . . . . 11 VDeg VDeg
6665breq2d 4217 . . . . . . . . . 10 VDeg VDeg
6766notbid 286 . . . . . . . . 9 VDeg VDeg
6867rabbidv 2941 . . . . . . . 8 VDeg VDeg
69 fveq2 5721 . . . . . . . . . 10
7069eqeq2d 2447 . . . . . . . . 9
7169preq2d 3883 . . . . . . . . 9
7270, 71ifbieq2d 3752 . . . . . . . 8
7368, 72eqeq12d 2450 . . . . . . 7 VDeg VDeg
7460, 73imbi12d 312 . . . . . 6 VDeg VDeg
7574imbi2d 308 . . . . 5 VDeg VDeg
76 breq1 4208 . . . . . . 7
77 oveq2 6082 . . . . . . . . . . . . . . 15
7877imaeq2d 5196 . . . . . . . . . . . . . 14
7978reseq2d 5139 . . . . . . . . . . . . 13
8079oveq2d 6090 . . . . . . . . . . . 12 VDeg VDeg
8180fveq1d 5723 . . . . . . . . . . 11 VDeg VDeg
8281breq2d 4217 . . . . . . . . . 10 VDeg VDeg
8382notbid 286 . . . . . . . . 9 VDeg VDeg
8483rabbidv 2941 . . . . . . . 8 VDeg VDeg
85 fveq2 5721 . . . . . . . . . 10
8685eqeq2d 2447 . . . . . . . . 9
8785preq2d 3883 . . . . . . . . 9
8886, 87ifbieq2d 3752 . . . . . . . 8
8984, 88eqeq12d 2450 . . . . . . 7 VDeg VDeg
9076, 89imbi12d 312 . . . . . 6 VDeg VDeg
9190imbi2d 308 . . . . 5 VDeg VDeg
92 2z 10305 . . . . . . . . . . 11
93 dvds0 12858 . . . . . . . . . . 11
9492, 93ax-mp 8 . . . . . . . . . 10
95 eupagra 21681 . . . . . . . . . . . 12 EulPaths UMGrph
96 relumgra 21342 . . . . . . . . . . . . 13 UMGrph
9796brrelexi 4911 . . . . . . . . . . . 12 UMGrph
981, 95, 973syl 19 . . . . . . . . . . 11
99 vdgr0 21664 . . . . . . . . . . 11 VDeg
10098, 99sylan 458 . . . . . . . . . 10 VDeg
10194, 100syl5breqr 4241 . . . . . . . . 9 VDeg
102 notnot1 116 . . . . . . . . 9 VDeg VDeg
103101, 102syl 16 . . . . . . . 8 VDeg
104103ralrimiva 2782 . . . . . . 7 VDeg
105 rabeq0 3642 . . . . . . 7 VDeg VDeg
106104, 105sylibr 204 . . . . . 6 VDeg
107106a1d 23 . . . . 5 VDeg
108 nn0re 10223 . . . . . . . . . . . 12
109108adantl 453 . . . . . . . . . . 11
110109lep1d 9935 . . . . . . . . . 10
111 peano2re 9232 . . . . . . . . . . . 12
112109, 111syl 16 . . . . . . . . . . 11
11319adantr 452 . . . . . . . . . . 11
114 letr 9160 . . . . . . . . . . 11
115109, 112, 113, 114syl3anc 1184 . . . . . . . . . 10
116110, 115mpand 657 . . . . . . . . 9
117116imim1d 71 . . . . . . . 8 VDeg VDeg
118 fveq2 5721 . . . . . . . . . . . . . . 15 VDeg VDeg
119118breq2d 4217 . . . . . . . . . . . . . 14 VDeg VDeg
120119notbid 286 . . . . . . . . . . . . 13 VDeg VDeg
121120elrab 3085 . . . . . . . . . . . 12 VDeg VDeg
1222ad3antrrr 711 . . . . . . . . . . . . . . 15 VDeg
1231ad3antrrr 711 . . . . . . . . . . . . . . 15 VDeg EulPaths
124 simpllr 736 . . . . . . . . . . . . . . 15 VDeg
125 simplrl 737 . . . . . . . . . . . . . . 15 VDeg
126 simpr 448 . . . . . . . . . . . . . . 15 VDeg
127 simplrr 738 . . . . . . . . . . . . . . 15 VDeg VDeg
128122, 123, 124, 125, 126, 127eupath2lem3 21694 . . . . . . . . . . . . . 14 VDeg VDeg
129128pm5.32da 623 . . . . . . . . . . . . 13 VDeg VDeg
130 0elpw 4362 . . . . . . . . . . . . . . . . 17
131 eupapf 21687 . . . . . . . . . . . . . . . . . . . . . 22 EulPaths
1321, 131syl 16 . . . . . . . . . . . . . . . . . . . . 21
133132ad2antrr 707 . . . . . . . . . . . . . . . . . . . 20 VDeg
13421ad2antrr 707 . . . . . . . . . . . . . . . . . . . . . 22 VDeg
135 nn0uz 10513 . . . . . . . . . . . . . . . . . . . . . 22
136134, 135syl6eleq 2526 . . . . . . . . . . . . . . . . . . . . 21 VDeg
137 eluzfz1 11057 . . . . . . . . . . . . . . . . . . . . 21
138136, 137syl 16 . . . . . . . . . . . . . . . . . . . 20 VDeg
139133, 138ffvelrnd 5864 . . . . . . . . . . . . . . . . . . 19 VDeg
140 simprl 733 . . . . . . . . . . . . . . . . . . . . 21 VDeg
141 peano2nn0 10253 . . . . . . . . . . . . . . . . . . . . . . . 24
142141ad2antlr 708 . . . . . . . . . . . . . . . . . . . . . . 23 VDeg
143142, 135syl6eleq 2526 . . . . . . . . . . . . . . . . . . . . . 22 VDeg
144134nn0zd 10366 . . . . . . . . . . . . . . . . . . . . . 22 VDeg
145 elfz5 11044 . . . . . . . . . . . . . . . . . . . . . 22
146143, 144, 145syl2anc 643 . . . . . . . . . . . . . . . . . . . . 21 VDeg
147140, 146mpbird 224 . . . . . . . . . . . . . . . . . . . 20 VDeg
148133, 147ffvelrnd 5864 . . . . . . . . . . . . . . . . . . 19 VDeg
149 prssi 3947 . . . . . . . . . . . . . . . . . . 19
150139, 148, 149syl2anc 643 . . . . . . . . . . . . . . . . . 18 VDeg
151 prex 4399 . . . . . . . . . . . . . . . . . . 19
152151elpw 3798 . . . . . . . . . . . . . . . . . 18
153150, 152sylibr 204 . . . . . . . . . . . . . . . . 17 VDeg
154 ifcl 3768 . . . . . . . . . . . . . . . . 17
155130, 153, 154sylancr 645 . . . . . . . . . . . . . . . 16 VDeg
156155elpwid 3801 . . . . . . . . . . . . . . 15 VDeg
157156sseld 3340 . . . . . . . . . . . . . 14 VDeg
158157pm4.71rd 617 . . . . . . . . . . . . 13 VDeg
159129, 158bitr4d 248 . . . . . . . . . . . 12 VDeg VDeg
160121, 159syl5bb 249 . . . . . . . . . . 11 VDeg VDeg
161160eqrdv 2434 . . . . . . . . . 10 VDeg VDeg
162161exp32 589 . . . . . . . . 9 VDeg VDeg
163162a2d 24 . . . . . . . 8 VDeg VDeg
164117, 163syld 42 . . . . . . 7 VDeg VDeg
165164expcom 425 . . . . . 6 VDeg VDeg
166165a2d 24 . . . . 5 VDeg VDeg
16743, 59, 75, 91, 107, 166nn0ind 10359 . . . 4 VDeg
16821, 167mpcom 34 . . 3 VDeg
16920, 168mpd 15 . 2 VDeg
17016, 169eqtr3d 2470 1 VDeg
 Colors of variables: wff set class Syntax hints:   wn 3   wi 4   wb 177   wa 359   wceq 1652   wcel 1725  wral 2698  crab 2702  cvv 2949   wss 3313  c0 3621  cif 3732  cpw 3792  cpr 3808   class class class wbr 4205   cres 4873  cima 4874   wfn 5442  wf 5443  wfo 5445  wf1o 5446  cfv 5447  (class class class)co 6074  cr 8982  cc0 8983  c1 8984   caddc 8986   cle 9114  c2 10042  cn0 10214  cz 10275  cuz 10481  cfz 11036  chash 11611   cdivides 12845   UMGrph cumg 21340   VDeg cvdg 21657   EulPaths ceup 21677 This theorem is referenced by:  eupath  21696 This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1555  ax-5 1566  ax-17 1626  ax-9 1666  ax-8 1687  ax-13 1727  ax-14 1729  ax-6 1744  ax-7 1749  ax-11 1761  ax-12 1950  ax-ext 2417  ax-rep 4313  ax-sep 4323  ax-nul 4331  ax-pow 4370  ax-pr 4396  ax-un 4694  ax-cnex 9039  ax-resscn 9040  ax-1cn 9041  ax-icn 9042  ax-addcl 9043  ax-addrcl 9044  ax-mulcl 9045  ax-mulrcl 9046  ax-mulcom 9047  ax-addass 9048  ax-mulass 9049  ax-distr 9050  ax-i2m1 9051  ax-1ne0 9052  ax-1rid 9053  ax-rnegex 9054  ax-rrecex 9055  ax-cnre 9056  ax-pre-lttri 9057  ax-pre-lttrn 9058  ax-pre-ltadd 9059  ax-pre-mulgt0 9060  ax-pre-sup 9061 This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1328  df-ex 1551  df-nf 1554  df-sb 1659  df-eu 2285  df-mo 2286  df-clab 2423  df-cleq 2429  df-clel 2432  df-nfc 2561  df-ne 2601  df-nel 2602  df-ral 2703  df-rex 2704  df-reu 2705  df-rmo 2706  df-rab 2707  df-v 2951  df-sbc 3155  df-csb 3245  df-dif 3316  df-un 3318  df-in 3320  df-ss 3327  df-pss 3329  df-nul 3622  df-if 3733  df-pw 3794  df-sn 3813  df-pr 3814  df-tp 3815  df-op 3816  df-uni 4009  df-int 4044  df-iun 4088  df-br 4206  df-opab 4260  df-mpt 4261  df-tr 4296  df-eprel 4487  df-id 4491  df-po 4496  df-so 4497  df-fr 4534  df-we 4536  df-ord 4577  df-on 4578  df-lim 4579  df-suc 4580  df-om 4839  df-xp 4877  df-rel 4878  df-cnv 4879  df-co 4880  df-dm 4881  df-rn 4882  df-res 4883  df-ima 4884  df-iota 5411  df-fun 5449  df-fn 5450  df-f 5451  df-f1 5452  df-fo 5453  df-f1o 5454  df-fv 5455  df-ov 6077  df-oprab 6078  df-mpt2 6079  df-1st 6342  df-2nd 6343  df-riota 6542  df-recs 6626  df-rdg 6661  df-1o 6717  df-2o 6718  df-oadd 6721  df-er 6898  df-pm 7014  df-en 7103  df-dom 7104  df-sdom 7105  df-fin 7106  df-sup 7439  df-card 7819  df-cda 8041  df-pnf 9115  df-mnf 9116  df-xr 9117  df-ltxr 9118  df-le 9119  df-sub 9286  df-neg 9287  df-div 9671  df-nn 9994  df-2 10051  df-3 10052  df-n0 10215  df-z 10276  df-uz 10482  df-rp 10606  df-xadd 10704  df-fz 11037  df-seq 11317  df-exp 11376  df-hash 11612  df-cj 11897  df-re 11898  df-im 11899  df-sqr 12033  df-abs 12034  df-dvds 12846  df-prm 13073  df-umgra 21341  df-vdgr 21658  df-eupa 21678
 Copyright terms: Public domain W3C validator