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

Theorem eupath 25707
Description: A graph with an Eulerian path has either zero or two vertices of odd degree. (Contributed by Mario Carneiro, 7-Apr-2015.)
Assertion
Ref Expression
eupath  |-  ( ( V EulPaths  E )  =/=  (/)  ->  ( # `
 { x  e.  V  |  -.  2  ||  ( ( V VDeg  E
) `  x ) } )  e.  {
0 ,  2 } )
Distinct variable groups:    x, E    x, V

Proof of Theorem eupath
Dummy variables  f  p  y are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 releupa 25690 . . . . 5  |-  Rel  ( V EulPaths  E )
2 reldm0 5071 . . . . 5  |-  ( Rel  ( V EulPaths  E )  ->  ( ( V EulPaths  E )  =  (/)  <->  dom  ( V EulPaths  E )  =  (/) ) )
31, 2ax-mp 5 . . . 4  |-  ( ( V EulPaths  E )  =  (/)  <->  dom  ( V EulPaths  E )  =  (/) )
43necon3bii 2688 . . 3  |-  ( ( V EulPaths  E )  =/=  (/)  <->  dom  ( V EulPaths  E )  =/=  (/) )
5 n0 3771 . . 3  |-  ( dom  ( V EulPaths  E )  =/=  (/)  <->  E. f  f  e. 
dom  ( V EulPaths  E ) )
64, 5bitri 252 . 2  |-  ( ( V EulPaths  E )  =/=  (/)  <->  E. f 
f  e.  dom  ( V EulPaths  E ) )
7 vex 3083 . . . . 5  |-  f  e. 
_V
87eldm 5051 . . . 4  |-  ( f  e.  dom  ( V EulPaths  E )  <->  E. p  f ( V EulPaths  E ) p )
9 eupagra 25692 . . . . . . . . 9  |-  ( f ( V EulPaths  E )
p  ->  V UMGrph  E )
10 umgraf2 25042 . . . . . . . . 9  |-  ( V UMGrph  E  ->  E : dom  E --> { y  e.  ( ~P V  \  { (/)
} )  |  (
# `  y )  <_  2 } )
11 ffn 5746 . . . . . . . . 9  |-  ( E : dom  E --> { y  e.  ( ~P V  \  { (/) } )  |  ( # `  y
)  <_  2 }  ->  E  Fn  dom  E
)
129, 10, 113syl 18 . . . . . . . 8  |-  ( f ( V EulPaths  E )
p  ->  E  Fn  dom  E )
13 id 22 . . . . . . . 8  |-  ( f ( V EulPaths  E )
p  ->  f ( V EulPaths  E ) p )
1412, 13eupath2 25706 . . . . . . 7  |-  ( f ( V EulPaths  E )
p  ->  { x  e.  V  |  -.  2  ||  ( ( V VDeg 
E ) `  x
) }  =  if ( ( p ` 
0 )  =  ( p `  ( # `  f ) ) ,  (/) ,  { ( p `
 0 ) ,  ( p `  ( # `
 f ) ) } ) )
1514fveq2d 5885 . . . . . 6  |-  ( f ( V EulPaths  E )
p  ->  ( # `  {
x  e.  V  |  -.  2  ||  ( ( V VDeg  E ) `  x ) } )  =  ( # `  if ( ( p ` 
0 )  =  ( p `  ( # `  f ) ) ,  (/) ,  { ( p `
 0 ) ,  ( p `  ( # `
 f ) ) } ) ) )
16 fveq2 5881 . . . . . . . 8  |-  ( (/)  =  if ( ( p `
 0 )  =  ( p `  ( # `
 f ) ) ,  (/) ,  { ( p `  0 ) ,  ( p `  ( # `  f ) ) } )  -> 
( # `  (/) )  =  ( # `  if ( ( p ` 
0 )  =  ( p `  ( # `  f ) ) ,  (/) ,  { ( p `
 0 ) ,  ( p `  ( # `
 f ) ) } ) ) )
1716eleq1d 2491 . . . . . . 7  |-  ( (/)  =  if ( ( p `
 0 )  =  ( p `  ( # `
 f ) ) ,  (/) ,  { ( p `  0 ) ,  ( p `  ( # `  f ) ) } )  -> 
( ( # `  (/) )  e. 
{ 0 ,  2 }  <->  ( # `  if ( ( p ` 
0 )  =  ( p `  ( # `  f ) ) ,  (/) ,  { ( p `
 0 ) ,  ( p `  ( # `
 f ) ) } ) )  e. 
{ 0 ,  2 } ) )
18 fveq2 5881 . . . . . . . 8  |-  ( { ( p `  0
) ,  ( p `
 ( # `  f
) ) }  =  if ( ( p ` 
0 )  =  ( p `  ( # `  f ) ) ,  (/) ,  { ( p `
 0 ) ,  ( p `  ( # `
 f ) ) } )  ->  ( # `
 { ( p `
 0 ) ,  ( p `  ( # `
 f ) ) } )  =  (
# `  if (
( p `  0
)  =  ( p `
 ( # `  f
) ) ,  (/) ,  { ( p ` 
0 ) ,  ( p `  ( # `  f ) ) } ) ) )
1918eleq1d 2491 . . . . . . 7  |-  ( { ( p `  0
) ,  ( p `
 ( # `  f
) ) }  =  if ( ( p ` 
0 )  =  ( p `  ( # `  f ) ) ,  (/) ,  { ( p `
 0 ) ,  ( p `  ( # `
 f ) ) } )  ->  (
( # `  { ( p `  0 ) ,  ( p `  ( # `  f ) ) } )  e. 
{ 0 ,  2 }  <->  ( # `  if ( ( p ` 
0 )  =  ( p `  ( # `  f ) ) ,  (/) ,  { ( p `
 0 ) ,  ( p `  ( # `
 f ) ) } ) )  e. 
{ 0 ,  2 } ) )
20 hash0 12554 . . . . . . . . 9  |-  ( # `  (/) )  =  0
21 c0ex 9644 . . . . . . . . . 10  |-  0  e.  _V
2221prid1 4108 . . . . . . . . 9  |-  0  e.  { 0 ,  2 }
2320, 22eqeltri 2503 . . . . . . . 8  |-  ( # `  (/) )  e.  {
0 ,  2 }
2423a1i 11 . . . . . . 7  |-  ( ( f ( V EulPaths  E ) p  /\  ( p `
 0 )  =  ( p `  ( # `
 f ) ) )  ->  ( # `  (/) )  e. 
{ 0 ,  2 } )
25 simpr 462 . . . . . . . . . 10  |-  ( ( f ( V EulPaths  E ) p  /\  -.  (
p `  0 )  =  ( p `  ( # `  f ) ) )  ->  -.  ( p `  0
)  =  ( p `
 ( # `  f
) ) )
2625neqned 2623 . . . . . . . . 9  |-  ( ( f ( V EulPaths  E ) p  /\  -.  (
p `  0 )  =  ( p `  ( # `  f ) ) )  ->  (
p `  0 )  =/=  ( p `  ( # `
 f ) ) )
27 fvex 5891 . . . . . . . . . 10  |-  ( p `
 0 )  e. 
_V
28 fvex 5891 . . . . . . . . . 10  |-  ( p `
 ( # `  f
) )  e.  _V
29 hashprg 12578 . . . . . . . . . 10  |-  ( ( ( p `  0
)  e.  _V  /\  ( p `  ( # `
 f ) )  e.  _V )  -> 
( ( p ` 
0 )  =/=  (
p `  ( # `  f
) )  <->  ( # `  {
( p `  0
) ,  ( p `
 ( # `  f
) ) } )  =  2 ) )
3027, 28, 29mp2an 676 . . . . . . . . 9  |-  ( ( p `  0 )  =/=  ( p `  ( # `  f ) )  <->  ( # `  {
( p `  0
) ,  ( p `
 ( # `  f
) ) } )  =  2 )
3126, 30sylib 199 . . . . . . . 8  |-  ( ( f ( V EulPaths  E ) p  /\  -.  (
p `  0 )  =  ( p `  ( # `  f ) ) )  ->  ( # `
 { ( p `
 0 ) ,  ( p `  ( # `
 f ) ) } )  =  2 )
32 2ex 10688 . . . . . . . . 9  |-  2  e.  _V
3332prid2 4109 . . . . . . . 8  |-  2  e.  { 0 ,  2 }
3431, 33syl6eqel 2515 . . . . . . 7  |-  ( ( f ( V EulPaths  E ) p  /\  -.  (
p `  0 )  =  ( p `  ( # `  f ) ) )  ->  ( # `
 { ( p `
 0 ) ,  ( p `  ( # `
 f ) ) } )  e.  {
0 ,  2 } )
3517, 19, 24, 34ifbothda 3946 . . . . . 6  |-  ( f ( V EulPaths  E )
p  ->  ( # `  if ( ( p ` 
0 )  =  ( p `  ( # `  f ) ) ,  (/) ,  { ( p `
 0 ) ,  ( p `  ( # `
 f ) ) } ) )  e. 
{ 0 ,  2 } )
3615, 35eqeltrd 2507 . . . . 5  |-  ( f ( V EulPaths  E )
p  ->  ( # `  {
x  e.  V  |  -.  2  ||  ( ( V VDeg  E ) `  x ) } )  e.  { 0 ,  2 } )
3736exlimiv 1770 . . . 4  |-  ( E. p  f ( V EulPaths  E ) p  -> 
( # `  { x  e.  V  |  -.  2  ||  ( ( V VDeg 
E ) `  x
) } )  e. 
{ 0 ,  2 } )
388, 37sylbi 198 . . 3  |-  ( f  e.  dom  ( V EulPaths  E )  ->  ( # `
 { x  e.  V  |  -.  2  ||  ( ( V VDeg  E
) `  x ) } )  e.  {
0 ,  2 } )
3938exlimiv 1770 . 2  |-  ( E. f  f  e.  dom  ( V EulPaths  E )  -> 
( # `  { x  e.  V  |  -.  2  ||  ( ( V VDeg 
E ) `  x
) } )  e. 
{ 0 ,  2 } )
406, 39sylbi 198 1  |-  ( ( V EulPaths  E )  =/=  (/)  ->  ( # `
 { x  e.  V  |  -.  2  ||  ( ( V VDeg  E
) `  x ) } )  e.  {
0 ,  2 } )
Colors of variables: wff setvar class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 187    /\ wa 370    = wceq 1437   E.wex 1657    e. wcel 1872    =/= wne 2614   {crab 2775   _Vcvv 3080    \ cdif 3433   (/)c0 3761   ifcif 3911   ~Pcpw 3981   {csn 3998   {cpr 4000   class class class wbr 4423   dom cdm 4853   Rel wrel 4858    Fn wfn 5596   -->wf 5597   ` cfv 5601  (class class class)co 6305   0cc0 9546    <_ cle 9683   2c2 10666   #chash 12521    || cdvds 14304   UMGrph cumg 25037   VDeg cvdg 25619   EulPaths ceup 25688
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1663  ax-4 1676  ax-5 1752  ax-6 1798  ax-7 1843  ax-8 1874  ax-9 1876  ax-10 1891  ax-11 1896  ax-12 1909  ax-13 2057  ax-ext 2401  ax-rep 4536  ax-sep 4546  ax-nul 4555  ax-pow 4602  ax-pr 4660  ax-un 6597  ax-cnex 9602  ax-resscn 9603  ax-1cn 9604  ax-icn 9605  ax-addcl 9606  ax-addrcl 9607  ax-mulcl 9608  ax-mulrcl 9609  ax-mulcom 9610  ax-addass 9611  ax-mulass 9612  ax-distr 9613  ax-i2m1 9614  ax-1ne0 9615  ax-1rid 9616  ax-rnegex 9617  ax-rrecex 9618  ax-cnre 9619  ax-pre-lttri 9620  ax-pre-lttrn 9621  ax-pre-ltadd 9622  ax-pre-mulgt0 9623  ax-pre-sup 9624
This theorem depends on definitions:  df-bi 188  df-or 371  df-an 372  df-3or 983  df-3an 984  df-tru 1440  df-ex 1658  df-nf 1662  df-sb 1791  df-eu 2273  df-mo 2274  df-clab 2408  df-cleq 2414  df-clel 2417  df-nfc 2568  df-ne 2616  df-nel 2617  df-ral 2776  df-rex 2777  df-reu 2778  df-rmo 2779  df-rab 2780  df-v 3082  df-sbc 3300  df-csb 3396  df-dif 3439  df-un 3441  df-in 3443  df-ss 3450  df-pss 3452  df-nul 3762  df-if 3912  df-pw 3983  df-sn 3999  df-pr 4001  df-tp 4003  df-op 4005  df-uni 4220  df-int 4256  df-iun 4301  df-br 4424  df-opab 4483  df-mpt 4484  df-tr 4519  df-eprel 4764  df-id 4768  df-po 4774  df-so 4775  df-fr 4812  df-we 4814  df-xp 4859  df-rel 4860  df-cnv 4861  df-co 4862  df-dm 4863  df-rn 4864  df-res 4865  df-ima 4866  df-pred 5399  df-ord 5445  df-on 5446  df-lim 5447  df-suc 5448  df-iota 5565  df-fun 5603  df-fn 5604  df-f 5605  df-f1 5606  df-fo 5607  df-f1o 5608  df-fv 5609  df-riota 6267  df-ov 6308  df-oprab 6309  df-mpt2 6310  df-om 6707  df-1st 6807  df-2nd 6808  df-wrecs 7039  df-recs 7101  df-rdg 7139  df-1o 7193  df-oadd 7197  df-er 7374  df-pm 7486  df-en 7581  df-dom 7582  df-sdom 7583  df-fin 7584  df-sup 7965  df-inf 7966  df-card 8381  df-cda 8605  df-pnf 9684  df-mnf 9685  df-xr 9686  df-ltxr 9687  df-le 9688  df-sub 9869  df-neg 9870  df-div 10277  df-nn 10617  df-2 10675  df-3 10676  df-n0 10877  df-z 10945  df-uz 11167  df-rp 11310  df-xadd 11417  df-fz 11792  df-seq 12220  df-exp 12279  df-hash 12522  df-cj 13162  df-re 13163  df-im 13164  df-sqrt 13298  df-abs 13299  df-dvds 14305  df-umgra 25038  df-vdgr 25620  df-eupa 25689
This theorem is referenced by:  konigsberg  25713
  Copyright terms: Public domain W3C validator