Mathbox for Mario Carneiro < Previous   Next > Nearby theorems Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  konigsberg Unicode version

Theorem konigsberg 24315
 Description: The Konigsberg Bridge problem. If is the graph on four vertices , with edges , then vertices each have degree three, and has degree five, so there are four vertices of odd degree and thus by eupath 24309 the graph cannot have an Eulerian path. (Contributed by Mario Carneiro, 11-Mar-2015.) (Revised by Mario Carneiro, 28-Feb-2016.)
Hypotheses
Ref Expression
konigsberg.v
konigsberg.e
Assertion
Ref Expression
konigsberg EulPaths

Proof of Theorem konigsberg
Dummy variable is distinct from all other variables.
StepHypRef Expression
1 prfi 7221 . . . . . 6
2 3ne0 9921 . . . . . . 7
3 1re 8927 . . . . . . . 8
4 1lt3 9980 . . . . . . . 8
53, 4gtneii 9020 . . . . . . 7
62, 5nelpri 3737 . . . . . 6
7 3nn0 10075 . . . . . . 7
8 hashunsng 11463 . . . . . . 7
97, 8ax-mp 8 . . . . . 6
101, 6, 9mp2an 653 . . . . 5
11 df-3 9895 . . . . . 6
12 ax-1ne0 8896 . . . . . . . . 9
1312necomi 2603 . . . . . . . 8
14 0nn0 10072 . . . . . . . . 9
15 1nn0 10073 . . . . . . . . 9
16 hashprg 11464 . . . . . . . . 9
1714, 15, 16mp2an 653 . . . . . . . 8
1813, 17mpbi 199 . . . . . . 7
1918oveq1i 5955 . . . . . 6
2011, 19eqtr4i 2381 . . . . 5
2110, 20eqtr4i 2381 . . . 4
22 konigsberg.v . . . . . . . 8
23 fzfi 11126 . . . . . . . 8
2422, 23eqeltri 2428 . . . . . . 7
25 ssrab2 3334 . . . . . . 7 VDeg
26 ssfi 7171 . . . . . . 7 VDeg VDeg
2724, 25, 26mp2an 653 . . . . . 6 VDeg
28 nn0uz 10354 . . . . . . . . . . . 12
297, 28eleqtri 2430 . . . . . . . . . . 11
30 eluzfz1 10895 . . . . . . . . . . 11
3129, 30ax-mp 8 . . . . . . . . . 10
3231, 22eleqtrri 2431 . . . . . . . . 9
33 2nn 9969 . . . . . . . . . 10
34 1nn 9847 . . . . . . . . . 10
35 2cn 9906 . . . . . . . . . . . . 13
3635mulid1i 8929 . . . . . . . . . . . 12
3736oveq1i 5955 . . . . . . . . . . 11
3837, 11eqtr4i 2381 . . . . . . . . . 10
39 1lt2 9978 . . . . . . . . . 10
4033, 15, 34, 38, 39ndvdsi 12706 . . . . . . . . 9
41 fveq2 5608 . . . . . . . . . . . . 13 VDeg VDeg
4224elexi 2873 . . . . . . . . . . . . . 14
43 df-s6 11598 . . . . . . . . . . . . . . 15 concat
44 df-s5 11597 . . . . . . . . . . . . . . . 16 concat
45 df-s4 11596 . . . . . . . . . . . . . . . . 17 concat
46 df-s3 11595 . . . . . . . . . . . . . . . . . 18 concat
47 df-s2 11594 . . . . . . . . . . . . . . . . . . 19 concat
48 3re 9907 . . . . . . . . . . . . . . . . . . . . . . . 24
493, 48, 4ltleii 9031 . . . . . . . . . . . . . . . . . . . . . . 23
5015, 28eleqtri 2430 . . . . . . . . . . . . . . . . . . . . . . . 24
517nn0zi 10140 . . . . . . . . . . . . . . . . . . . . . . . 24
52 elfz5 10882 . . . . . . . . . . . . . . . . . . . . . . . 24
5350, 51, 52mp2an 653 . . . . . . . . . . . . . . . . . . . . . . 23
5449, 53mpbir 200 . . . . . . . . . . . . . . . . . . . . . 22
5554, 22eleqtrri 2431 . . . . . . . . . . . . . . . . . . . . 21
5642, 32, 55umgrabi 24311 . . . . . . . . . . . . . . . . . . . 20
5756s1cld 11538 . . . . . . . . . . . . . . . . . . 19 Word
58 2re 9905 . . . . . . . . . . . . . . . . . . . . . . 23
59 2lt3 9979 . . . . . . . . . . . . . . . . . . . . . . 23
6058, 48, 59ltleii 9031 . . . . . . . . . . . . . . . . . . . . . 22
61 2nn0 10074 . . . . . . . . . . . . . . . . . . . . . . . 24
6261, 28eleqtri 2430 . . . . . . . . . . . . . . . . . . . . . . 23
63 elfz5 10882 . . . . . . . . . . . . . . . . . . . . . . 23
6462, 51, 63mp2an 653 . . . . . . . . . . . . . . . . . . . . . 22
6560, 64mpbir 200 . . . . . . . . . . . . . . . . . . . . 21
6665, 22eleqtrri 2431 . . . . . . . . . . . . . . . . . . . 20
6742, 32, 66umgrabi 24311 . . . . . . . . . . . . . . . . . . 19
6847, 57, 67cats1cld 11601 . . . . . . . . . . . . . . . . . 18 Word
69 eluzfz2 10896 . . . . . . . . . . . . . . . . . . . . 21
7029, 69ax-mp 8 . . . . . . . . . . . . . . . . . . . 20
7170, 22eleqtrri 2431 . . . . . . . . . . . . . . . . . . 19
7242, 32, 71umgrabi 24311 . . . . . . . . . . . . . . . . . 18
7346, 68, 72cats1cld 11601 . . . . . . . . . . . . . . . . 17 Word
7442, 55, 66umgrabi 24311 . . . . . . . . . . . . . . . . 17
7545, 73, 74cats1cld 11601 . . . . . . . . . . . . . . . 16 Word
7644, 75, 74cats1cld 11601 . . . . . . . . . . . . . . 15 Word
7742, 66, 71umgrabi 24311 . . . . . . . . . . . . . . 15
7843, 76, 77cats1cld 11601 . . . . . . . . . . . . . 14 Word
79 wrd0 11514 . . . . . . . . . . . . . . . . . . . . 21 Word
8079a1i 10 . . . . . . . . . . . . . . . . . . . 20 Word
8142, 32vdeg0i 24310 . . . . . . . . . . . . . . . . . . . 20 VDeg
82 1e0p1 10244 . . . . . . . . . . . . . . . . . . . 20
83 s0s1 11645 . . . . . . . . . . . . . . . . . . . 20 concat
8442, 80, 32, 81, 82, 55, 12, 83vdegp1bi 24313 . . . . . . . . . . . . . . . . . . 19 VDeg
85 df-2 9894 . . . . . . . . . . . . . . . . . . 19
86 2ne0 9919 . . . . . . . . . . . . . . . . . . 19
8742, 57, 32, 84, 85, 66, 86, 47vdegp1bi 24313 . . . . . . . . . . . . . . . . . 18 VDeg
8842, 68, 32, 87, 11, 71, 2, 46vdegp1bi 24313 . . . . . . . . . . . . . . . . 17 VDeg
8942, 73, 32, 88, 55, 12, 66, 86, 45vdegp1ai 24312 . . . . . . . . . . . . . . . 16 VDeg
9042, 75, 32, 89, 55, 12, 66, 86, 44vdegp1ai 24312 . . . . . . . . . . . . . . 15 VDeg
9142, 76, 32, 90, 66, 86, 71, 2, 43vdegp1ai 24312 . . . . . . . . . . . . . 14 VDeg
92 konigsberg.e . . . . . . . . . . . . . . 15
93 df-s7 11599 . . . . . . . . . . . . . . 15 concat
9492, 93eqtri 2378 . . . . . . . . . . . . . 14 concat
9542, 78, 32, 91, 66, 86, 71, 2, 94vdegp1ai 24312 . . . . . . . . . . . . 13 VDeg
9641, 95syl6eq 2406 . . . . . . . . . . . 12 VDeg
9796breq2d 4116 . . . . . . . . . . 11 VDeg
9897notbid 285 . . . . . . . . . 10 VDeg
9998elrab 2999 . . . . . . . . 9 VDeg
10032, 40, 99mpbir2an 886 . . . . . . . 8 VDeg
101 fveq2 5608 . . . . . . . . . . . . 13 VDeg VDeg
10242, 55vdeg0i 24310 . . . . . . . . . . . . . . . . . . . 20 VDeg
10342, 80, 55, 102, 82, 32, 13, 83vdegp1ci 24314 . . . . . . . . . . . . . . . . . . 19 VDeg
1043, 39gtneii 9020 . . . . . . . . . . . . . . . . . . 19
10542, 57, 55, 103, 32, 13, 66, 104, 47vdegp1ai 24312 . . . . . . . . . . . . . . . . . 18 VDeg
10642, 68, 55, 105, 32, 13, 71, 5, 46vdegp1ai 24312 . . . . . . . . . . . . . . . . 17 VDeg
10742, 73, 55, 106, 85, 66, 104, 45vdegp1bi 24313 . . . . . . . . . . . . . . . 16 VDeg
10842, 75, 55, 107, 11, 66, 104, 44vdegp1bi 24313 . . . . . . . . . . . . . . 15 VDeg
10942, 76, 55, 108, 66, 104, 71, 5, 43vdegp1ai 24312 . . . . . . . . . . . . . 14 VDeg
11042, 78, 55, 109, 66, 104, 71, 5, 94vdegp1ai 24312 . . . . . . . . . . . . 13 VDeg
111101, 110syl6eq 2406 . . . . . . . . . . . 12 VDeg
112111breq2d 4116 . . . . . . . . . . 11 VDeg
113112notbid 285 . . . . . . . . . 10 VDeg
114113elrab 2999 . . . . . . . . 9 VDeg
11555, 40, 114mpbir2an 886 . . . . . . . 8 VDeg
116 prssi 3850 . . . . . . . 8 VDeg VDeg VDeg
117100, 115, 116mp2an 653 . . . . . . 7 VDeg
118 fveq2 5608 . . . . . . . . . . . . 13 VDeg VDeg
11942, 71vdeg0i 24310 . . . . . . . . . . . . . . . . . . . 20 VDeg
120 0re 8928 . . . . . . . . . . . . . . . . . . . . 21
121 3pos 9920 . . . . . . . . . . . . . . . . . . . . 21
122120, 121ltneii 9021 . . . . . . . . . . . . . . . . . . . 20
1233, 4ltneii 9021 . . . . . . . . . . . . . . . . . . . 20
12442, 80, 71, 119, 32, 122, 55, 123, 83vdegp1ai 24312 . . . . . . . . . . . . . . . . . . 19 VDeg
12558, 59ltneii 9021 . . . . . . . . . . . . . . . . . . 19
12642, 57, 71, 124, 32, 122, 66, 125, 47vdegp1ai 24312 . . . . . . . . . . . . . . . . . 18 VDeg
12742, 68, 71, 126, 82, 32, 122, 46vdegp1ci 24314 . . . . . . . . . . . . . . . . 17 VDeg
12842, 73, 71, 127, 55, 123, 66, 125, 45vdegp1ai 24312 . . . . . . . . . . . . . . . 16 VDeg
12942, 75, 71, 128, 55, 123, 66, 125, 44vdegp1ai 24312 . . . . . . . . . . . . . . 15 VDeg
13042, 76, 71, 129, 85, 66, 125, 43vdegp1ci 24314 . . . . . . . . . . . . . 14 VDeg
13142, 78, 71, 130, 11, 66, 125, 94vdegp1ci 24314 . . . . . . . . . . . . 13 VDeg
132118, 131syl6eq 2406 . . . . . . . . . . . 12 VDeg
133132breq2d 4116 . . . . . . . . . . 11 VDeg
134133notbid 285 . . . . . . . . . 10 VDeg
135134elrab 2999 . . . . . . . . 9 VDeg
13671, 40, 135mpbir2an 886 . . . . . . . 8 VDeg
137 snssi 3838 . . . . . . . 8 VDeg VDeg
138136, 137ax-mp 8 . . . . . . 7 VDeg
139117, 138unssi 3426 . . . . . 6 VDeg
140 ssdomg 6995 . . . . . 6 VDeg VDeg VDeg
14127, 139, 140mp2 17 . . . . 5 VDeg
142 snfi 7029 . . . . . . 7
143 unfi 7214 . . . . . . 7
1441, 142, 143mp2an 653 . . . . . 6
145 hashdom 11454 . . . . . 6 VDeg VDeg VDeg
146144, 27, 145mp2an 653 . . . . 5 VDeg VDeg
147141, 146mpbir 200 . . . 4 VDeg
14821, 147eqbrtrri 4125 . . 3 VDeg
149 hashcl 11443 . . . . . 6 VDeg VDeg
15027, 149ax-mp 8 . . . . 5 VDeg
151150nn0rei 10068 . . . 4 VDeg
15248, 151lenlti 9028 . . 3 VDeg VDeg
153148, 152mpbi 199 . 2 VDeg
154 eupath 24309 . . . 4 EulPaths VDeg
155 elpri 3736 . . . 4 VDeg VDeg VDeg
156 id 19 . . . . . 6 VDeg VDeg
157156, 121syl6eqbr 4141 . . . . 5 VDeg VDeg
158 id 19 . . . . . 6 VDeg VDeg
159158, 59syl6eqbr 4141 . . . . 5 VDeg VDeg
160157, 159jaoi 368 . . . 4 VDeg VDeg VDeg
161154, 155, 1603syl 18 . . 3 EulPaths VDeg
162161necon1bi 2564 . 2 VDeg EulPaths
163153, 162ax-mp 8 1 EulPaths
 Colors of variables: wff set class Syntax hints:   wn 3   wi 4   wb 176   wo 357   wa 358   wtru 1316   wceq 1642   wcel 1710   wne 2521  crab 2623   cdif 3225   cun 3226   wss 3228  c0 3531  cpw 3701  csn 3716  cpr 3717   class class class wbr 4104  cfv 5337  (class class class)co 5945   cdom 6949  cfn 6951  cc0 8827  c1 8828   caddc 8830   cmul 8832   clt 8957   cle 8958  c2 9885  c3 9886  cn0 10057  cz 10116  cuz 10322  cfz 10874  chash 11430  Word cword 11499   concat cconcat 11500  cs1 11501  cs2 11587  cs3 11588  cs4 11589  cs5 11590  cs6 11591  cs7 11592   cdivides 12628   EulPaths ceup 24265   VDeg cvdg 24266 This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1546  ax-5 1557  ax-17 1616  ax-9 1654  ax-8 1675  ax-13 1712  ax-14 1714  ax-6 1729  ax-7 1734  ax-11 1746  ax-12 1930  ax-ext 2339  ax-rep 4212  ax-sep 4222  ax-nul 4230  ax-pow 4269  ax-pr 4295  ax-un 4594  ax-cnex 8883  ax-resscn 8884  ax-1cn 8885  ax-icn 8886  ax-addcl 8887  ax-addrcl 8888  ax-mulcl 8889  ax-mulrcl 8890  ax-mulcom 8891  ax-addass 8892  ax-mulass 8893  ax-distr 8894  ax-i2m1 8895  ax-1ne0 8896  ax-1rid 8897  ax-rnegex 8898  ax-rrecex 8899  ax-cnre 8900  ax-pre-lttri 8901  ax-pre-lttrn 8902  ax-pre-ltadd 8903  ax-pre-mulgt0 8904  ax-pre-sup 8905 This theorem depends on definitions:  df-bi 177  df-or 359  df-an 360  df-3or 935  df-3an 936  df-tru 1319  df-ex 1542  df-nf 1545  df-sb 1649  df-eu 2213  df-mo 2214  df-clab 2345  df-cleq 2351  df-clel 2354  df-nfc 2483  df-ne 2523  df-nel 2524  df-ral 2624  df-rex 2625  df-reu 2626  df-rmo 2627  df-rab 2628  df-v 2866  df-sbc 3068  df-csb 3158  df-dif 3231  df-un 3233  df-in 3235  df-ss 3242  df-pss 3244  df-nul 3532  df-if 3642  df-pw 3703  df-sn 3722  df-pr 3723  df-tp 3724  df-op 3725  df-uni 3909  df-int 3944  df-iun 3988  df-br 4105  df-opab 4159  df-mpt 4160  df-tr 4195  df-eprel 4387  df-id 4391  df-po 4396  df-so 4397  df-fr 4434  df-we 4436  df-ord 4477  df-on 4478  df-lim 4479  df-suc 4480  df-om 4739  df-xp 4777  df-rel 4778  df-cnv 4779  df-co 4780  df-dm 4781  df-rn 4782  df-res 4783  df-ima 4784  df-iota 5301  df-fun 5339  df-fn 5340  df-f 5341  df-f1 5342  df-fo 5343  df-f1o 5344  df-fv 5345  df-ov 5948  df-oprab 5949  df-mpt2 5950  df-1st 6209  df-2nd 6210  df-riota 6391  df-recs 6475  df-rdg 6510  df-1o 6566  df-2o 6567  df-oadd 6570  df-er 6747  df-pm 6863  df-en 6952  df-dom 6953  df-sdom 6954  df-fin 6955  df-sup 7284  df-card 7662  df-cda 7884  df-pnf 8959  df-mnf 8960  df-xr 8961  df-ltxr 8962  df-le 8963  df-sub 9129  df-neg 9130  df-div 9514  df-nn 9837  df-2 9894  df-3 9895  df-n0 10058  df-z 10117  df-uz 10323  df-rp 10447  df-fz 10875  df-fzo 10963  df-seq 11139  df-exp 11198  df-hash 11431  df-word 11505  df-concat 11506  df-s1 11507  df-s2 11594  df-s3 11595  df-s4 11596  df-s5 11597  df-s6 11598  df-s7 11599  df-cj 11680  df-re 11681  df-im 11682  df-sqr 11816  df-abs 11817  df-dvds 12629  df-prm 12856  df-umgra 24267  df-eupa 24268  df-vdgr 24269
 Copyright terms: Public domain W3C validator