MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  eulerpathpr Structured version   Visualization version   GIF version

Theorem eulerpathpr 27414
Description: A graph with an Eulerian path has either zero or two vertices of odd degree. (Contributed by Mario Carneiro, 7-Apr-2015.) (Revised by AV, 26-Feb-2021.)
Hypothesis
Ref Expression
eulerpathpr.v 𝑉 = (Vtx‘𝐺)
Assertion
Ref Expression
eulerpathpr ((𝐺 ∈ UPGraph ∧ 𝐹(EulerPaths‘𝐺)𝑃) → (♯‘{𝑥𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘𝐺)‘𝑥)}) ∈ {0, 2})
Distinct variable groups:   𝑥,𝐹   𝑥,𝐺   𝑥,𝑃   𝑥,𝑉

Proof of Theorem eulerpathpr
StepHypRef Expression
1 eulerpathpr.v . . . 4 𝑉 = (Vtx‘𝐺)
2 eqid 2761 . . . 4 (iEdg‘𝐺) = (iEdg‘𝐺)
3 simpl 474 . . . 4 ((𝐺 ∈ UPGraph ∧ 𝐹(EulerPaths‘𝐺)𝑃) → 𝐺 ∈ UPGraph)
4 upgruhgr 26218 . . . . . 6 (𝐺 ∈ UPGraph → 𝐺 ∈ UHGraph)
52uhgrfun 26182 . . . . . 6 (𝐺 ∈ UHGraph → Fun (iEdg‘𝐺))
64, 5syl 17 . . . . 5 (𝐺 ∈ UPGraph → Fun (iEdg‘𝐺))
76adantr 472 . . . 4 ((𝐺 ∈ UPGraph ∧ 𝐹(EulerPaths‘𝐺)𝑃) → Fun (iEdg‘𝐺))
8 simpr 479 . . . 4 ((𝐺 ∈ UPGraph ∧ 𝐹(EulerPaths‘𝐺)𝑃) → 𝐹(EulerPaths‘𝐺)𝑃)
91, 2, 3, 7, 8eupth2 27413 . . 3 ((𝐺 ∈ UPGraph ∧ 𝐹(EulerPaths‘𝐺)𝑃) → {𝑥𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘𝐺)‘𝑥)} = if((𝑃‘0) = (𝑃‘(♯‘𝐹)), ∅, {(𝑃‘0), (𝑃‘(♯‘𝐹))}))
109fveq2d 6358 . 2 ((𝐺 ∈ UPGraph ∧ 𝐹(EulerPaths‘𝐺)𝑃) → (♯‘{𝑥𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘𝐺)‘𝑥)}) = (♯‘if((𝑃‘0) = (𝑃‘(♯‘𝐹)), ∅, {(𝑃‘0), (𝑃‘(♯‘𝐹))})))
11 fveq2 6354 . . . 4 (∅ = if((𝑃‘0) = (𝑃‘(♯‘𝐹)), ∅, {(𝑃‘0), (𝑃‘(♯‘𝐹))}) → (♯‘∅) = (♯‘if((𝑃‘0) = (𝑃‘(♯‘𝐹)), ∅, {(𝑃‘0), (𝑃‘(♯‘𝐹))})))
1211eleq1d 2825 . . 3 (∅ = if((𝑃‘0) = (𝑃‘(♯‘𝐹)), ∅, {(𝑃‘0), (𝑃‘(♯‘𝐹))}) → ((♯‘∅) ∈ {0, 2} ↔ (♯‘if((𝑃‘0) = (𝑃‘(♯‘𝐹)), ∅, {(𝑃‘0), (𝑃‘(♯‘𝐹))})) ∈ {0, 2}))
13 fveq2 6354 . . . 4 ({(𝑃‘0), (𝑃‘(♯‘𝐹))} = if((𝑃‘0) = (𝑃‘(♯‘𝐹)), ∅, {(𝑃‘0), (𝑃‘(♯‘𝐹))}) → (♯‘{(𝑃‘0), (𝑃‘(♯‘𝐹))}) = (♯‘if((𝑃‘0) = (𝑃‘(♯‘𝐹)), ∅, {(𝑃‘0), (𝑃‘(♯‘𝐹))})))
1413eleq1d 2825 . . 3 ({(𝑃‘0), (𝑃‘(♯‘𝐹))} = if((𝑃‘0) = (𝑃‘(♯‘𝐹)), ∅, {(𝑃‘0), (𝑃‘(♯‘𝐹))}) → ((♯‘{(𝑃‘0), (𝑃‘(♯‘𝐹))}) ∈ {0, 2} ↔ (♯‘if((𝑃‘0) = (𝑃‘(♯‘𝐹)), ∅, {(𝑃‘0), (𝑃‘(♯‘𝐹))})) ∈ {0, 2}))
15 hash0 13371 . . . . 5 (♯‘∅) = 0
16 c0ex 10247 . . . . . 6 0 ∈ V
1716prid1 4442 . . . . 5 0 ∈ {0, 2}
1815, 17eqeltri 2836 . . . 4 (♯‘∅) ∈ {0, 2}
1918a1i 11 . . 3 (((𝐺 ∈ UPGraph ∧ 𝐹(EulerPaths‘𝐺)𝑃) ∧ (𝑃‘0) = (𝑃‘(♯‘𝐹))) → (♯‘∅) ∈ {0, 2})
20 simpr 479 . . . . . 6 (((𝐺 ∈ UPGraph ∧ 𝐹(EulerPaths‘𝐺)𝑃) ∧ ¬ (𝑃‘0) = (𝑃‘(♯‘𝐹))) → ¬ (𝑃‘0) = (𝑃‘(♯‘𝐹)))
2120neqned 2940 . . . . 5 (((𝐺 ∈ UPGraph ∧ 𝐹(EulerPaths‘𝐺)𝑃) ∧ ¬ (𝑃‘0) = (𝑃‘(♯‘𝐹))) → (𝑃‘0) ≠ (𝑃‘(♯‘𝐹)))
22 fvex 6364 . . . . . 6 (𝑃‘0) ∈ V
23 fvex 6364 . . . . . 6 (𝑃‘(♯‘𝐹)) ∈ V
24 hashprg 13395 . . . . . 6 (((𝑃‘0) ∈ V ∧ (𝑃‘(♯‘𝐹)) ∈ V) → ((𝑃‘0) ≠ (𝑃‘(♯‘𝐹)) ↔ (♯‘{(𝑃‘0), (𝑃‘(♯‘𝐹))}) = 2))
2522, 23, 24mp2an 710 . . . . 5 ((𝑃‘0) ≠ (𝑃‘(♯‘𝐹)) ↔ (♯‘{(𝑃‘0), (𝑃‘(♯‘𝐹))}) = 2)
2621, 25sylib 208 . . . 4 (((𝐺 ∈ UPGraph ∧ 𝐹(EulerPaths‘𝐺)𝑃) ∧ ¬ (𝑃‘0) = (𝑃‘(♯‘𝐹))) → (♯‘{(𝑃‘0), (𝑃‘(♯‘𝐹))}) = 2)
27 2ex 11305 . . . . 5 2 ∈ V
2827prid2 4443 . . . 4 2 ∈ {0, 2}
2926, 28syl6eqel 2848 . . 3 (((𝐺 ∈ UPGraph ∧ 𝐹(EulerPaths‘𝐺)𝑃) ∧ ¬ (𝑃‘0) = (𝑃‘(♯‘𝐹))) → (♯‘{(𝑃‘0), (𝑃‘(♯‘𝐹))}) ∈ {0, 2})
3012, 14, 19, 29ifbothda 4268 . 2 ((𝐺 ∈ UPGraph ∧ 𝐹(EulerPaths‘𝐺)𝑃) → (♯‘if((𝑃‘0) = (𝑃‘(♯‘𝐹)), ∅, {(𝑃‘0), (𝑃‘(♯‘𝐹))})) ∈ {0, 2})
3110, 30eqeltrd 2840 1 ((𝐺 ∈ UPGraph ∧ 𝐹(EulerPaths‘𝐺)𝑃) → (♯‘{𝑥𝑉 ∣ ¬ 2 ∥ ((VtxDeg‘𝐺)‘𝑥)}) ∈ {0, 2})
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 196  wa 383   = wceq 1632  wcel 2140  wne 2933  {crab 3055  Vcvv 3341  c0 4059  ifcif 4231  {cpr 4324   class class class wbr 4805  Fun wfun 6044  cfv 6050  0cc0 10149  2c2 11283  chash 13332  cdvds 15203  Vtxcvtx 26095  iEdgciedg 26096  UHGraphcuhgr 26172  UPGraphcupgr 26196  VtxDegcvtxdg 26593  EulerPathsceupth 27371
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1871  ax-4 1886  ax-5 1989  ax-6 2055  ax-7 2091  ax-8 2142  ax-9 2149  ax-10 2169  ax-11 2184  ax-12 2197  ax-13 2392  ax-ext 2741  ax-rep 4924  ax-sep 4934  ax-nul 4942  ax-pow 4993  ax-pr 5056  ax-un 7116  ax-cnex 10205  ax-resscn 10206  ax-1cn 10207  ax-icn 10208  ax-addcl 10209  ax-addrcl 10210  ax-mulcl 10211  ax-mulrcl 10212  ax-mulcom 10213  ax-addass 10214  ax-mulass 10215  ax-distr 10216  ax-i2m1 10217  ax-1ne0 10218  ax-1rid 10219  ax-rnegex 10220  ax-rrecex 10221  ax-cnre 10222  ax-pre-lttri 10223  ax-pre-lttrn 10224  ax-pre-ltadd 10225  ax-pre-mulgt0 10226  ax-pre-sup 10227
This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-ifp 1051  df-3or 1073  df-3an 1074  df-tru 1635  df-ex 1854  df-nf 1859  df-sb 2048  df-eu 2612  df-mo 2613  df-clab 2748  df-cleq 2754  df-clel 2757  df-nfc 2892  df-ne 2934  df-nel 3037  df-ral 3056  df-rex 3057  df-reu 3058  df-rmo 3059  df-rab 3060  df-v 3343  df-sbc 3578  df-csb 3676  df-dif 3719  df-un 3721  df-in 3723  df-ss 3730  df-pss 3732  df-nul 4060  df-if 4232  df-pw 4305  df-sn 4323  df-pr 4325  df-tp 4327  df-op 4329  df-uni 4590  df-int 4629  df-iun 4675  df-br 4806  df-opab 4866  df-mpt 4883  df-tr 4906  df-id 5175  df-eprel 5180  df-po 5188  df-so 5189  df-fr 5226  df-we 5228  df-xp 5273  df-rel 5274  df-cnv 5275  df-co 5276  df-dm 5277  df-rn 5278  df-res 5279  df-ima 5280  df-pred 5842  df-ord 5888  df-on 5889  df-lim 5890  df-suc 5891  df-iota 6013  df-fun 6052  df-fn 6053  df-f 6054  df-f1 6055  df-fo 6056  df-f1o 6057  df-fv 6058  df-riota 6776  df-ov 6818  df-oprab 6819  df-mpt2 6820  df-om 7233  df-1st 7335  df-2nd 7336  df-wrecs 7578  df-recs 7639  df-rdg 7677  df-1o 7731  df-2o 7732  df-oadd 7735  df-er 7914  df-map 8028  df-pm 8029  df-en 8125  df-dom 8126  df-sdom 8127  df-fin 8128  df-sup 8516  df-inf 8517  df-card 8976  df-cda 9203  df-pnf 10289  df-mnf 10290  df-xr 10291  df-ltxr 10292  df-le 10293  df-sub 10481  df-neg 10482  df-div 10898  df-nn 11234  df-2 11292  df-3 11293  df-n0 11506  df-xnn0 11577  df-z 11591  df-uz 11901  df-rp 12047  df-xadd 12161  df-fz 12541  df-fzo 12681  df-seq 13017  df-exp 13076  df-hash 13333  df-word 13506  df-cj 14059  df-re 14060  df-im 14061  df-sqrt 14195  df-abs 14196  df-dvds 15204  df-vtx 26097  df-iedg 26098  df-edg 26161  df-uhgr 26174  df-ushgr 26175  df-upgr 26198  df-uspgr 26266  df-vtxdg 26594  df-wlks 26727  df-trls 26821  df-eupth 27372
This theorem is referenced by:  eulerpath  27415
  Copyright terms: Public domain W3C validator