Editing Four color theorem (section)

==Three-coloring==
[[File:visual_proof_USA_states_map_needs_4_colors.svg|thumb|upright=1.2|[[Proof without words]] that a map of US states needs at least four colors.]]
While every planar map can be colored with four colors, it is [[NP-complete]] in [[computational complexity theory|complexity]] to decide whether an arbitrary planar map can be colored with just three colors.<ref>{{Citation
 | last1 = Dailey | first1 = D. P.
 | title = Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | volume = 30
 | pages = 289–293
 | year = 1980
 | doi = 10.1016/0012-365X(80)90236-8
 | issue = 3
| doi-access = free
 }}</ref>

A [[Cubic graph|cubic map]] can be colored with only three colors if and only if each interior region has an even number of neighboring regions.<ref>{{citation
 | last = Steinberg | first = Richard
 | editor1-last = Gimbel | editor1-first = John
 | editor2-last = Kennedy | editor2-first = John W.
 | editor3-last = Quintas | editor3-first = Louis V.
 | contribution = The state of the three color problem
 | doi = 10.1016/S0167-5060(08)70391-1
 | mr = 1217995
 | pages = 211–248
 | publisher = North-Holland | location = Amsterdam
 | series = Annals of Discrete Mathematics
 | title = Quo Vadis, Graph Theory?
 | volume = 55
 | year = 1993| isbn = 978-0-444-89441-0
 }}</ref> In the US states map example, landlocked [[Missouri]] (MO) has eight neighbors (an even number): it must be differently colored from all of them, but the neighbors can alternate colors, thus this part of the map needs only three colors. However, landlocked [[Nevada]] (NV) has five neighbors (an odd number): these neighbors require three colors, and it must be differently colored from them, thus four colors are needed here.