Re: Four Color Theorem


a.khanm@xxxxxxxxx wrote:
bill wrote:
Hypothesis: A simple loopless maximal planar graph with a 5-degree
vertex cannot be a
minimal counter example to the four color theorem!.

It follows from the four colour theorem. However, proving it directly
is another matter. A possible way is induction on the minimum vertex
degree of a maximal planar graph.

Any triangulation with minimum degree 1,2,3 or 4 is cannot be a minimal
counter example by induction on the number of vertices. Assume that
none of the triangulations with minimum vertex degree n-1 is a minimal
counter example and prove the result for n.

This would prove the general version of your statement and the four
colour theorem. But this will take some doing as inductive arguments to
prove four colour theorem and its reformulations have always failed.

My proof is based on the assumption that the following graph is not
4-chroma.
[The drawing below is correct in the "print" mode}

|..............| Internal chord
|--------------| External {B-C-B} Kempe chain
D <== A-----B-----C-----B------D ==> A
|--------------|--------------| External {A-C) & {C-D}
Kempe chains

The graph is planar. The {B-C-B} chain may cross the {A-C} & {C-D}
chains
at common 'C' vertices.

----Bill J

.

Relevant Pages

  • Re: Four Color Theorem
    ... My approach is to expand the yellow regions so that they have a common ... It follows from the four colour theorem. ... A possible way is induction on the minimum vertex ... counter example by induction on the number of vertices. ...
    (sci.math)
  • Re: Four Color Theorem
    ... It follows from the four colour theorem. ... A possible way is induction on the minimum vertex ... Any triangulation with minimum degree 1,2,3 or 4 is cannot be a minimal ... counter example by induction on the number of vertices. ...
    (sci.math)
  • Re: Four Color Theorem
    ... coloring algorithm in more detail, that is three-coloring of the spiral ... It follows from the four colour theorem. ... A possible way is induction on the minimum vertex ... counter example by induction on the number of vertices. ...
    (sci.math)
  • Re: Four Color Theorem
    ... coloring algorithm in more detail, that is three-coloring of the spiral ... It follows from the four colour theorem. ... A possible way is induction on the minimum vertex ... counter example by induction on the number of vertices. ...
    (sci.math)
  • Re: Four Color Theorem
    ... coloring algorithm in more detail, that is three-coloring of the spiral ... It follows from the four colour theorem. ... A possible way is induction on the minimum vertex ... counter example by induction on the number of vertices. ...
    (sci.math)