On Tuesday, June 18, 2013 3:14:41 PM UTC-7, bill wrote: > Conjecture: A graph is four-colorable, if it does not contain a complete K5 sub graph.
Sorry, post not entirely true. We have
A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graph on five vertices) or K3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph). A subdivision of a graph results from inserting vertices into edges (for example, changing an edge ???? to ?????) zero or more times.
So replace "K3,3 sub-graph" with "sub-graph that is a K3,3 subdivision".
Also, we need the graph to free of sub-graphs that are K5 subdivisions.