The Toft Problem:
Let G be a (k+1)-colorable graph with out K_(k+1).
Does it follow that there are two vertices X and Y
and two k-colorable subgraphs G1 and G2
each containing X and Y such that
(1) in any k-coloring of G1, X and Y receive different colors, and
(2) in any k-coloring of G2, X and Y receive the same colors.
The minimum counter example to the 4CT qualifies as graph G. Figure 1
is an always present induced subgraph of G.
Figure 1 R G R
1----2----3
|\ | /|
| \ | / |
| \ | / |
| O O |
| / \ |
| / \ |
| / \ |
|/ \|
B 5---------4 Y
For convenience, the vertices of Figure 1 have been assigned colors.
By definition, P (the pentagon formed by vertices 1 thru 5) may not be
3-colored.
Toft Problem Analysis of Figure 1.
Let v_0 be X ; v_2 = Y. Then G1 is shown in Figure 2
Figure 2 R G R
1----Y----3
|\ | /|
| \ | / |
| \ | / |
| X B |
| \ |
| \ |
| \ |
| \|
B 5---------4 Y
G2 is shown in Figure 3
Figure 3 R G R
1----Y----3
|\ /|
| \ / |
| \ / |
| X G |
| / \ |
| / \ |
| / \ |
|/ \|
B 5---------4 Y
By definition P must be 4-colored. Therefore, v_X must be adjacent to at
least 3 different colors. but v_X cannot be adjacent to 4 different colors.
Then G2 would not be 4-colorable! The only way that G2 can be 4-colored
is when v_X is adjacent to only 3 different colors and
v_X and v_Y receive the same colors!