Citat:
Ursprungligen postat av Offsure
Sådana är väldigt lätta att bevisa eller motbevisa med lite grafteori. Avancerade grafteoretiska problem kan dock vara svåra att lösa. Ett problem som jag kommer att tänka på är hur många färger man behöver för att måla en karta av godtyckliga sammanhängande områden, om angränsande områden inte ska ha samma färg. Jag har dock för mig att det löstes, och att det krävdes endast 4 färger. Inte säker, dock. Men något som är svårt är
http://sv.wikipedia.org/wiki/Handelsresandeproblemet.
Fyrfärgsproblemet påstås tydligen vara löst, men när jag hörde om det för några år sedan så var det tydligen inte direkt någon vacker eller för den delen kort lösning, och jag tror inte den genomgått tillräcklig granskning.
EDIT: wikipedia säger att det skedde redan på 70-talet, och att en del av beviset bestod att bevisa det för 1936 specifika grafer, därav det flera hundra sidor långa beviset. " their proof was not accepted by all mathematicians because the
computer-assisted proof was infeasible for a human to check by hand (
Swart 1980). Since then the proof has gained wider acceptance, although doubts remain", dock bevisades det på nytt 2005.