Re: Some Thoughts on the Four Color Theorem

On Jul 4, 4:12 pm, Proginoskes <CCHeck...@xxxxxxxxx> wrote:
On Jul 4, 2:16 pm, bill <b92...@xxxxxxxxx> wrote:

1. The minimal counter example (MCE) to the 4CT

The vertex-coloring version of the 4CT.

is a simple
loopless triangulation such that every vertex has degree
equal 5 or greater.

2. The dual of the MCE is a triangle-free cubic planar graph.

There are no triangular _faces_ in a triangulation with minimum degree>= 5, but there might be triangles in a planar graph which are not

planar. However, this is not true for a MCE. (It takes a little bit of
work, though, which I'll let bill do.)

3 The MCE must be the dual of a triangle-free cubic planar graph!

This is the same thing you said in (2.)

Compare the two statements:
"2. The dual of the MCE is a triangle-free cubic planar graph."
"3 The MCE must be the dual of a triangle-free cubic planar graph!"

4 Every triangle-less cubic planar graph is 3 edge colorable.

You can eliminate "triangle-less" here, but you need to put in "bridge-
free" (or 2-connected) here. If every triangle-free 2-connected cubic
planar graph is 3-edge colorable, then every 2-connected cubic planar
graph is 3-edge colorable. Again, I'll leave this as an exercise for
bill, hinting to do it by induction on the number of triangles in the
graph.

A isolated triangle can be removed by replacing the 3 vertices
of the triangle with a single vertex. A twin-triangle; ie, two
triangles with a common edge, may be replaced with an
single edge! Then any 3 coloring of the triangle-free graph
can be extended to a 3 coloring of the original.

Note: Any CPG's pertinent to the 4CT cannot have "twin-
triangles"! The dual of a CPG with T-T's invariably has a loop and
parallel edges. This is also true for the dual of a CPG
with a bridge!

Bill J

5 The 4CT is true if statement 4 above is true!

This is a statement of the form (False => something), so is vacuuously
true. After adding the 2-connected condition, it becomes equivalent.

--- Christopher Heckman


.

Relevant Pages