Computer Printout, Semi-critical Subsets of Colorings of the 6-Ring
date: label: Date made
content: 1988
name: label: maker
content: Haken, Wolfgang
notes: label: Description
content: This computer printout relates to the proof of the four color problem developed by Wolfgang Haken and Kenneth Appel of the University of Illinois in 1976. This was one of the first major mathematical proofs done with computer assistance.
label: Description
content: The four color problem states that, when drawing any kind of map on a two-dimensional surface (including but not limited to the map of the world), no more than four colors are needed in order to color every country and ensure that no two countries of the same color share a border. The only assumption made is that all countries are contiguous (countries are not divided into multiple disconnected parts, as is the case with the United States, including the states of Alaska and Hawaii).
label: Description
content: Haken and Appel discovered that all possible map layouts contained one or more particular smaller layouts called “unavoidable configurations.” They also discovered “reducible configurations” to which all larger maps could be mathematically “reduced.” A map containing a reducible configuration cannot be the smallest possible map to contradict the four color theorem; if it did, said map could be reduced to a smaller map also contradicting the four color theorem. Haken and Appel’s epiphany came when they identified 1,936 configurations (later shortened to 1,476) that were both reducible and formed an unavoidable set of configurations. Thus every possible map contained at least one reducible configuration and consequently no map could be the smallest map to contradict the four color theorem. This seeming logical absurdity led to the conclusion that no contradiction could exist and the four color theorem applied to all possible maps. This proof took over 1000 hours of computer processing to check all 1,936 configurations and required 400 pages to be double-checked by hand.
label: Description
content: Hakin and Appel published a complete and detailed proof in 1989 to counter rumors that their initial 1976 proof contained errors.
label: Description
content: This particular printout was made by Haken in January, 1988. It includes about 200 pages of hand tabulations. This is the second version of the proof. The computer-printed pages are bound in a beige report cover with metal and plastic binding, with many notations in pencil and red ink.
label: Description
content: Punch cards relating to the proof are part of non-accession 1999.3075.
label: Location
content: Currently not on view
topic: label: Subject
content: Mathematics
setName: label: See more items in
content: Medicine and Science: Mathematics
creditLine: label: Credit Line
content: Gift of Wolfgang Haken
dataSource: label: Data Source
content: National Museum of American History
identifier: label: ID Number
content: 1999.0339.01
label: catalog number
content: 1999.0339.01
label: accession number
content: 1999.0339
objectType: label: Object Name
content: Documentation
physicalDescription: label: Physical Description
content: plastic (overall material)
label: Physical Description
content: paper (overall material)
label: Physical Description
content: metal (overall material)
label: Measurements
content: overall: 13 cm x 40 cm x 23.7 cm; 5 1/8 in x 15 3/4 in x 9 5/16 in