A B A B C.
Figure 1; 1-----2-----3-----4-----5
We wish to force a 4-coloring as shown in Figure 2,
A B D B C.
Figure 2; 1-----2-----3-----4-----5
Caveat: No edge or vertex may be added inside the cycle.
In reality, this is an impossible task, as everyone knows! But the fiction
that it can be solved must be maintained. Otherwise, the 4CT would be
true by default.
Since we have to pretend that its solvable, let's go ahead and pretend that
we have a solution!
For simplicity, let's stipulate that the entire graph X is a simple loopless
planar graph. Chi(X) = 4.
Graph X is planar but not maximal. It is possible to add two interior
chord to the subgraph C. One of them can be added between v_2 & v_4 as
shown in Figure 3
A B D B C.
Figure 3; 1-----2-----3-----4-----5
|-----------|
Now X is not properly 4-colored. Since failure to do so will prove the 4CT;
it is essential that we can properly 4-color Figure 3. Note that;
1. Figure 3 is 4-colored if v_2 is colored C vice B
2. Figure 3 is 4-colored if v_4 is colored A vice B.
This gives us a problem that we should not arbitrarily dismiss!
If either v_2 or v_4 can be conveniently recolored individually; why cannot
they be recolored simultaneously?
Let's limit our options by adding a second interior chord as in Figure 4.
A B D B C.
Figure 4; 1-----2-----3-----4-----5
| |-----------|
|-----------------|
Now Figure 4 can be made 4-C only by recoloring v_2 from B to C.
A C D B C.
Figure 5; 1-----2-----3-----4-----5
| |-----------|
|-----------------|
Then we move chord {14} to {25}
A C D B C.
Figure 6; 1-----2-----3-----4-----5
|-----------| |
|-----------------|
Recoloring v_5 = D vice C
A C D B D.
Figure 7; 1-----2-----3-----4-----5
|-----------| |
|-----------------|
Now we have another situation which merits consideration:
Vertex v_2 can be either B or C; vertex v_5 can either be C or D. If
v_2 could be B and v_5 could be D at the same time; then C would be
3-colored!
Initial Conditions
I
|---------------|
|----------| | Internal Chords
A----B1----C----B2----D
|~~~~~~~~~~|~~~~~~~~~| External Chains
Graph P before recoloring.
One way to 4-color Graph P is to recolor vertex B2 = A.
|---------------|
|----------| | Internal Chords
A1---B1----C----A2---D
|~~~~~~~~~~|~~~~~~~~~| External Chains
This can be countered by moving a chord to A1/A2
|---------------|
| |----------| Internal Chords
A1---B1----C----A2----D
|~~~~~~~~~~|~~~~~~~~~~| External Chains
If we respect the integrity of the chains, how can we 4-color this graph?
Perhaps, if we change B1 to D and then recolor A2 = B?
Waaaaa ... it a minute! If we change B1 to D, do not we have a 3-coloring of
Graph P?
II
Let's start over with a different set of chains
|---------------|
|----------| | Internal Chords
A----B1----C----B2---D
|~~~~~~~~~~| | External Chains
|~~~~~~~~~~~~~~~|
Graph P before recoloring.
This configuration cannot be 4-colored without disturbing one or
both of the chains! Let's try again.
III
|---------------|
|----------| | Internal Chords
A----B1----C----B2---D
| |~~~~~~~~~| External Chains
|~~~~~~~~~~~~~~~|
Graph P before recoloring.
A good start is B2 = A2
|---------------|
|----------| | Internal Chords
A----B1----C----A2---D
| |~~~~~~~~~| External Chains
|~~~~~~~~~~~~~~~|
Counter with
|---------------|
| |----------| Internal Chords
A----B1----C----A2---D
| |~~~~~~~~~| External Chains
|~~~~~~~~~~~~~~~|
Recolor A = C1
|---------------|
| |----------| Internal Chords
C1---B1----C2---A2---D
| |~~~~~~~~~| External Chains
|~~~~~~~~~~~~~~~|
Chord counter move
|---------------|
|----------| | Internal Chords
C1---B1----C2---A2---D
| |~~~~~~~~~| External Chains
|~~~~~~~~~~~~~~~|
It seems to me that the only way to 4-color this configuration is
to make C2 = D2 But I don't know how this will effect the C2/D chain?