|
|
| Author |
Message |
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
 Posted: Tue Jun 20, 2006 6:55 pm Post subject:
Four Color Theorem
|
|
|
Hypothesis: A simple loopless maximal planar graph with a 5-degree
vertex cannot be a
minimal counter example to the four color theorem!. |
|
| Back to top |
|
 |
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Tue Jun 20, 2006 11:21 pm Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | Hypothesis: A simple loopless maximal planar graph with a 5-degree
vertex cannot be a
minimal counter example to the four color theorem!.
|
Actually, that should be a lemma, not a hypothesis.
--- Christopher Heckman |
|
| Back to top |
|
|
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Wed Jun 21, 2006 5:55 pm Post subject:
Re: Four Color Theorem
|
|
|
Proginoskes wrote:
| Quote: | 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!.
Actually, that should be a lemma, not a hypothesis.
--- Christopher Heckman
|
In Message-ID: <1141801956.464981.70430@j33g2000cwa.googlegroups.com>
Date: 7 Mar 2006 23:12:36 -0800. you stat;
"The problem is that a vertex of degree 5 isn't a reducible
configuration.
Technically, no one has been able to figure out how to make it one."
Are you now stating that a vertex of degree 5 is a reducible
configuration? |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Thu Jun 22, 2006 6:36 am Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | Proginoskes 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!.
Actually, that should be a lemma, not a hypothesis.
In Message-ID: <1141801956.464981.70430@j33g2000cwa.googlegroups.com
Date: 7 Mar 2006 23:12:36 -0800. you stat;
"The problem is that a vertex of degree 5 isn't a reducible
configuration.
Technically, no one has been able to figure out how to make it one."
Are you now stating that a vertex of degree 5 is a reducible
configuration?
|
Sheesh. For crying out loud, either continue this privately OR in the
Usenet group, but not both.
Here's the reply I sent him:
No. What I meant was that you need to _prove_ your hypothesis. You
can't assume it (which is what "hypothesis" usually means: something
you assume is true, and work from there).
--- Christopher Heckman |
|
| Back to top |
|
|
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Sat Jun 24, 2006 9:10 pm Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | Hypothesis: A simple loopless maximal planar graph with a 5-degree
vertex cannot be a minimal counter example to the four color theorem!.
|
If this is true, then the four color theorem is true! |
|
| Back to top |
|
|
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Thu Jun 29, 2006 9:44 pm Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | Proginoskes 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!.
Actually, that should be a lemma, not a hypothesis.
--- Christopher Heckman
In Message-ID: <1141801956.464981.70430@j33g2000cwa.googlegroups.com
Date: 7 Mar 2006 23:12:36 -0800. you stat;
"The problem is that a vertex of degree 5 isn't a reducible
configuration.
Technically, no one has been able to figure out how to make it one."
|
One way to make a 5-degree vertex into a reducible configuration is to
prove that
you cannot force a 4-coloring on 5-cycle graph. Has this been tried?
If so,
why did the proof fail?
---Bill
| Quote: |
Are you now stating that a vertex of degree 5 is a reducible
configuration? |
|
|
| Back to top |
|
|
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Thu Jun 29, 2006 9:46 pm Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | Proginoskes 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!.
Actually, that should be a lemma, not a hypothesis.
--- Christopher Heckman
In Message-ID: <1141801956.464981.70430@j33g2000cwa.googlegroups.com
Date: 7 Mar 2006 23:12:36 -0800. you stat;
"The problem is that a vertex of degree 5 isn't a reducible
configuration.
Technically, no one has been able to figure out how to make it one."
|
One way to make a 5-degree vertex into a reducible configuration is to
prove that
you cannot force a 4-coloring on a 5-cycle graph. Has this been tried?
If so,
why did the proof fail?
---Bill
| Quote: |
Are you now stating that a vertex of degree 5 is a reducible
configuration? |
|
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Fri Jun 30, 2006 4:50 am Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | bill wrote:
Proginoskes 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!.
Actually, that should be a lemma, not a hypothesis.
In Message-ID: <1141801956.464981.70430@j33g2000cwa.googlegroups.com
Date: 7 Mar 2006 23:12:36 -0800. you stat;
"The problem is that a vertex of degree 5 isn't a reducible
configuration.
Technically, no one has been able to figure out how to make it one."
One way to make a 5-degree vertex into a reducible configuration is to prove that
you cannot force a 4-coloring on a 5-cycle graph. Has this been tried? If so,
why did the proof fail?
|
A few people have tried to say that since a 5-cycle can be colored with
3 colors, that leaves you with one color for the center vertex v.
(Someone posted a paper at LANL within the past couple of years with
this idea.) However, you may need more colors than needed, because the
3-coloring of the 5-cycle might not be compatible with any of the other
colorings of G-v.
Think of it this way: If you take a pentagon and remove one vertex u,
then the neighbors of u can be colored the same. (There is no edge
between them.) But there is no way to 2-color the entire pentagon.
--- Christopher Heckman |
|
| Back to top |
|
|
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Sat Jul 01, 2006 5:29 am Post subject:
Re: Four Color Theorem
|
|
|
Proginoskes wrote:
| Quote: | bill wrote:
bill wrote:
Proginoskes 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!.
Actually, that should be a lemma, not a hypothesis.
In Message-ID: <1141801956.464981.70430@j33g2000cwa.googlegroups.com
Date: 7 Mar 2006 23:12:36 -0800. you stat;
"The problem is that a vertex of degree 5 isn't a reducible
configuration.
Technically, no one has been able to figure out how to make it one."
One way to make a 5-degree vertex into a reducible configuration is to prove that
you cannot force a 4-coloring on a 5-cycle graph. Has this been tried? If so,
why did the proof fail?
A few people have tried to say that since a 5-cycle can be colored with
3 colors, that leaves you with one color for the center vertex v.
(Someone posted a paper at LANL within the past couple of years with
this idea.) However, you may need more colors than needed, because the
3-coloring of the 5-cycle might not be compatible with any of the other
colorings of G-v.
|
If it not, then the 4CT is false. But has anybody tried to prove that
you can't
force a 4-coloring on a 5-cycle graph?
| Quote: | Think of it this way: If you take a pentagon and remove one vertex u,
then the neighbors of u can be colored the same. (There is no edge
between them.) But there is no way to 2-color the entire pentagon.
I am satisfied if the pentagon can always be properly 3-colored! |
---Bill J
> --- Christopher Heckman |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Sat Jul 01, 2006 6:12 am Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | Proginoskes wrote:
bill wrote:
bill wrote:
Proginoskes 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!.
Actually, that should be a lemma, not a hypothesis.
In Message-ID: <1141801956.464981.70430@j33g2000cwa.googlegroups.com
Date: 7 Mar 2006 23:12:36 -0800. you stat;
"The problem is that a vertex of degree 5 isn't a reducible
configuration.
Technically, no one has been able to figure out how to make it one."
One way to make a 5-degree vertex into a reducible configuration is to prove that
you cannot force a 4-coloring on a 5-cycle graph. Has this been tried? If so,
why did the proof fail?
A few people have tried to say that since a 5-cycle can be colored with
3 colors, that leaves you with one color for the center vertex v.
(Someone posted a paper at LANL within the past couple of years with
this idea.) However, you may need more colors than needed, because the
3-coloring of the 5-cycle might not be compatible with any of the other
colorings of G-v.
If it not, then the 4CT is false. But has anybody tried to prove that you can't
force a 4-coloring on a 5-cycle graph?
|
Probably.
| Quote: | Think of it this way: If you take a pentagon and remove one vertex u,
then the neighbors of u can be colored the same. (There is no edge
between them.) But there is no way to 2-color the entire pentagon.
I am satisfied if the pentagon can always be properly 3-colored!
|
True, but the point of the example is: You can't just concentrate on
the neighborhood of a certain vertex; a coloring is a global object.
The same argument applies if "pentagon" is replaced by "a cycle of
length (2 * google plex + 3)". If you pick a single vertex v and look
at all the vertices within a distance of a google plex of v, you will
have a 2-colorable graph, yet the entire graph is not 2-colorable.
--- Christopher Heckman |
|
| Back to top |
|
|
bill
science forum Guru
Joined: 07 Sep 2005
Posts: 311
|
| Posted: Sat Jul 01, 2006 7:57 pm Post subject:
Re: Four Color Theorem
|
|
|
Proginoskes wrote:
| Quote: | bill wrote:
Proginoskes wrote:
bill wrote:
bill wrote:
Proginoskes 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!.
Actually, that should be a lemma, not a hypothesis.
In Message-ID: <1141801956.464981.70430@j33g2000cwa.googlegroups.com
Date: 7 Mar 2006 23:12:36 -0800. you stat;
"The problem is that a vertex of degree 5 isn't a reducible
configuration.
Technically, no one has been able to figure out how to make it one."
|
But has anyone proved that a 5-degree vertex is NOT a reducible
configuration?
| Quote: |
One way to make a 5-degree vertex into a reducible configuration is to prove that
you cannot force a 4-coloring on a 5-cycle graph. Has this been tried? If so,
why did the proof fail?
A few people have tried to say that since a 5-cycle can be colored with
3 colors, that leaves you with one color for the center vertex v.
(Someone posted a paper at LANL within the past couple of years with
this idea.) However, you may need more colors than needed, because the
3-coloring of the 5-cycle might not be compatible with any of the other
colorings of G-v.
If it not, then the 4CT is false. But has anybody tried to prove that you can't
force a 4-coloring on a 5-cycle graph?
Probably.
What were the probable results? |
| Quote: | Think of it this way: If you take a pentagon and remove one vertex u,
then the neighbors of u can be colored the same. (There is no edge
between them.) But there is no way to 2-color the entire pentagon.
I am satisfied if the pentagon can always be properly 3-colored!
True, but the point of the example is: You can't just concentrate on
the neighborhood of a certain vertex; a coloring is a global object.
The same argument applies if "pentagon" is replaced by "a cycle of
length (2 * google plex + 3)". If you pick a single vertex v and look
at all the vertices within a distance of a google plex of v, you will
have a 2-colorable graph, yet the entire graph is not 2-colorable.
|
> --- Christopher Heckman |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Sun Jul 02, 2006 4:36 am Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
bill wrote:
Proginoskes 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!.
Actually, that should be a lemma, not a hypothesis.
In Message-ID: <1141801956.464981.70430@j33g2000cwa.googlegroups.com
Date: 7 Mar 2006 23:12:36 -0800. you stat;
"The problem is that a vertex of degree 5 isn't a reducible
configuration.
Technically, no one has been able to figure out how to make it one."
But has anyone proved that a 5-degree vertex is NOT a reducible
configuration?
|
I don't think so.
Remember proving something is not possible is different from not
proving that it is possible.
| Quote: |
One way to make a 5-degree vertex into a reducible configuration is to prove that
you cannot force a 4-coloring on a 5-cycle graph. Has this been tried? If so,
why did the proof fail?
A few people have tried to say that since a 5-cycle can be colored with
3 colors, that leaves you with one color for the center vertex v.
(Someone posted a paper at LANL within the past couple of years with
this idea.) However, you may need more colors than needed, because the
3-coloring of the 5-cycle might not be compatible with any of the other
colorings of G-v.
If it not, then the 4CT is false. But has anybody tried to prove that you can't
force a 4-coloring on a 5-cycle graph?
Probably.
What were the probable results?
|
Failure.
| Quote: | Think of it this way: If you take a pentagon and remove one vertex u,
then the neighbors of u can be colored the same. (There is no edge
between them.) But there is no way to 2-color the entire pentagon.
I am satisfied if the pentagon can always be properly 3-colored!
True, but the point of the example is: You can't just concentrate on
the neighborhood of a certain vertex; a coloring is a global object.
The same argument applies if "pentagon" is replaced by "a cycle of
length (2 * google plex + 3)". If you pick a single vertex v and look
at all the vertices within a distance of a google plex of v, you will
have a 2-colorable graph, yet the entire graph is not 2-colorable.
|
--- Christopher Heckman |
|
| Back to top |
|
|
a.khanm@gmail.com
science forum beginner
Joined: 02 Jul 2006
Posts: 14
|
| Posted: Sun Jul 02, 2006 11:25 am Post subject:
Re: Four Color Theorem
|
|
|
bill wrote:
| Quote: | 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. |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Sun Jul 02, 2006 4:54 pm Post subject:
Re: Four Color Theorem
|
|
|
a.khanm@gmail.com wrote:
| Quote: | 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.
|
But a variation of induction is the backbone to reduction, a technique
that both Appel and Haken, and Robertson Sanders Seymour Thomas used to
find a proof.
--- Christopher Heckman |
|
| Back to top |
|
|
icahit@gmail.com
science forum beginner
Joined: 30 Sep 2005
Posts: 24
|
| Posted: Sun Jul 02, 2006 9:34 pm Post subject:
Re: Four Color Theorem
|
|
|
May be the answer to Bill's question is in my response in another group
at
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1150590683
Cahit
Proginoskes wrote:
| Quote: | a.khanm@gmail.com 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.
But a variation of induction is the backbone to reduction, a technique
that both Appel and Haken, and Robertson Sanders Seymour Thomas used to
find a proof.
--- Christopher Heckman |
|
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Jan 10, 2009 2:07 am | All times are GMT
|
|
Credit Cards | Sexy School Girl Costume | Nora Roberts | Mortgages | Adverse Credit Remortgage
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
