Re: Minimal Counter-example to the 4CT.


bill wrote:
Chip Eastham wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
Chip Eastham wrote:
[...]
I'm confused what you are asking. "Minimal counterexample"
has a pretty clearly defined in meaning with respect to 4CT,

Or in any other proof. A graph G is a minimal counterexample to a
proposition T if

(1) T is not true for G, and
(2) If H has fewer vertices than G, then T is true for H.

The idea is similar to that of "Infinite Descent".

Thr principle of "Infinite Descent" is a valid method of mathematical
proof. A summary is given in;.
http://mcraefamily.com/MathHelp/PythagInfiniteDescent.htm

Generally, ID says that you start with the assumption of minimality and
then find
something smaller.. But in the long run, it is not nrcessary to start
with an assumption of minimality.

It seems to me that ID is a viable way of proving that an "mce to the
4CT" does not exist. Could I be wrong?

Yes.

---

But am I wrong?

Let's review. You wrote:

: Thr principle of "Infinite Descent" is a valid method of mathematical
: proof. A summary is given in;.
: http://mcraefamily.com/MathHelp/PythagInfiniteDescent.htm

Okay so far.

: Generally, ID says that you start with the assumption of minimality and
: then find something smaller.. But in the long run, it is not nrcessary to
: start with an assumption of minimality.


A precise notion of minimality is necessary to use "infinite descent"
as "a valid method of mathematical proof". It may be a matter of
presentation in the proof when this notion gets introduced/defined,
but since it is a bridge that has to be crossed, saying that it is "not
necessary to start with an assumption of minimality" is irrelevant
at best to an overview of your approach. After all, we presume the
"m" in "mce" stands for "minimal".

If we are required to start with the presumption of minimality, then a
graph with vertices of degree <=4 must be assumed to be minimal!

But you're not looking at a minimal planar graph; you're looking for a
minimal planar graph _that requires 5 colors_.

If I wish to avoid the issue of pre-assumed minimality, I merely add a vertex to my
graph. This does not effect the colorability of the graph [or] the validity of my
analysis. Then at the end, I remove the vertex. But as long as that
vertex is present, the question of minimality is moot?

But if you have a mce to the 4CT and add a vertex v to get G, you can't
say anything about how many colors the graph G-u needs, unless u is the
vertex v.

: It seems to me that ID is a viable way of proving that an "mce to the
: 4CT" does not exist. Could I be wrong?

Since "infinite descent" already entrains the notion of "no minimal
(counter)example exists", I would suggest re-phrasing this to avoid
redundancy as "ID is a viable way of proving the 4CT".

I don't understand? How can ID prove the 4CT without proving that an
"mce to the 4CT does not exist"?

ID would say that for every counterexample G(0), there is a
counterexample G(1) with fewer vertices; and then this analysis can be
applied to G(1) to get a counterexample G(2) with fewer vertices than
G(1), etc. But G(0) has a finite number of vertices (let's say n) to
start with, so G(n) can't have any vertices at all. (G(i) has at most
n-i vertices, for all i.) Since a graph with <= 4 vertices can be
4-colored, this contradicts the fact that G(n) is a counterexample,
which propogates up the chain to G(0).

If that is the
meaning, I will have to admit you are right.

The existing proofs of
the four- and five-color theorems clearly have an ingredient of this.

For example the first proof of 4CT by Appel and Haken introduces
the notions of "unavoidable set" and "reducible configurations". In
particular a reducible configuration is defined in a manner implying
minimal counterexamples cannot contain a reducible configuration.

See here for discussion of how many reducible configurations are
needed to form an unavoidable set:

I maintain that there is an unavoidable set with only one configuration; ie,
a vertex with degree = 5! This is the basis for my "phantom" proof of the 4CT
using the principles of 'Infinite [Descent]".

But the problem is that a vertex of degree 5 isn't a reducible
configuration, so the proof doesn't go completely through, and another
unavoidable set is needed.

Probably the second-smallest unavoidable set for a planar graph (with
minimum degree >= 5) is {C(1), C(2)} where C(1) consists of two
vertices of degree 5 adjacent to each other, and C(2) is a vertex of
degree 5 adjacent to a vertex of degree 6. This is proved using a
technique called "discharging".

--- Christopher Heckman

.

Relevant Pages

  • Re: Minimal Counter-example to the 4CT.
    ... "Minimal counterexample" ... with an assumption of minimality. ... graph with vertices of degree <=4 must be assumed to be minimal! ... minimal counterexamples cannot contain a reducible configuration. ...
    (sci.math)
  • Re: Minimal Counter-example to the 4CT.
    ... "Minimal counterexample" ... with an assumption of minimality. ... graph with vertices of degree <=4 must be assumed to be minimal! ... minimal counterexamples cannot contain a reducible configuration. ...
    (sci.math)
  • Re: Four Color Theorem
    ... It follows from the four colour theorem. ... My proof is based on the assumption that the following graph is not 4-chroma. ... All you have done is made one coloring fail to work; ... You get a coloring C from the minimality of G, and show that there is a ...
    (sci.math)
  • Re: Four Color Theorem
    ... It follows from the four colour theorem. ... My proof is based on the assumption that the following graph is not 4-chroma. ... All you have done is made one coloring fail to work; ... You get a coloring C from the minimality of G, and show that there is a ...
    (sci.math)
  • Re: Minimal Counter-example to the 4CT.
    ... "Minimal counterexample" ... with an assumption of minimality. ... Since "infinite descent" already entrains the notion of "no minimal ... minimal counterexamples cannot contain a reducible configuration. ...
    (sci.math)