Re: Minimum Counter-Example to the Four Color Theorem


bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Proginoskes wrote:
bill wrote:
Assuming that everyone knows what the "Minimum Counter-Example to the
Four Color Theorem" is, I would like to document some of its
properties.

A. The MCE/4CT is a simple loopless maximal planar graph. If the MCE
starts out as a "pseudograph" {as defined in Mathworld}, all loops and
multiple edges may be removed
without losing 5-chromacity. If the MCE starts out less than
"maximal", it can be maximized without losing 5-chromacity.

B. Every vertex must have degree equal to or greater than five.

C. The MCE needs only one vertex with the "fifth" color, say "O".
Suppose that there are two or more "O" vertices. If any vertex "v"'
is removed, then the resulting graph can be
recolored to a proper 4-coloring;
ie, no 'O' vertices. But when "v" is restored, only one vertex will
be 'O'. So why not start out with only one 'O' vertex?

Also, it is connected (in fact, "internally 6-connected", proven back
in 1913), and you may as well assume every face is a triangle.

I understand "six-connected" , but what is meant by "internally"
six-connected?

"Internally 6-connected" here means the graph is 4-connected, and if
you delete 6 vertices from G to get H, then H is connected, or one of
the connected components of H is a single vertex.

If there are 5-degree vertices, it seems that only 5 vertices would need
to be deleted to disconnect G (H)?

Yes; that's why the terminology "5-connected" is not used. In an
_internally_ 5-connected graph, if you delete 5 vertices, at least one
of the components consists of one vertex. This is the case if you
delete the neighbors of a vertex of degree 5.

Basically, "internally 5 connected" means: The only way to find 5
vertices whose deletion disconnects the graph, is to choose the
neighbors of a vertex of degree 5.

Is there really any significant difference between "internally 6-connected', and
"every vertex has degree >= 5"?

Yes. If it's internally 6-connected, then every vertex has degree >= 5,
but if every vertex has degree >= 5, the graph does not even need to be
connected (let alone 4-connected).


For my immediate purposes, the "connectedness" of an MCE is immaterial, as long as
every vertex has degree >= 5.

and every face is a triangle.

If I am successful in proving that the MCE cannot have a
vertex with degree = 5, it will be comforting to know that every
maximal planar graph has at least one vertex of degree = 5.

A little review:

Let G be a loopless maximal planar graph order 'n' All of the overt requirements for
MCE status are in place; ie, Chi(G) = 5, no 4-degree vertices; only one "O" vertex, etc.

In order to talk about an "O" vertex, you need to have a coloring
already.

Remove a 5-degree vertex (v_0) to create graph (H). By definition, H is smaller than G
because it has fewer vertices. H is given a proper 4-coloring. Vertex v_0 is replaced.
Chi(G) = 5. So far G is an MCE.

and v_0 is an "O" vertex of the coloring [c].

Note that when you're talking about "a coloring", you need to specify
which one. This is because later on, you will want a coloring of a
different graph, or a coloring with properties that c may not have.

And c is not necessarily unique. (In fact, according to Lorenz Friess,
it isn't.) I'm saying the coloring is the same if you shuffle the
colors.

Figure 1 below shows the neighbors of v_0 [v_0 not shown]

B R G
1----------2----------3
| |
| |
5----------------------4
Y R
Figure 1

A 4-coloring is shown for Figure 1.

Hypothesis: A four coloring of Figure 1 is necessary if Chi(H) = 4 and Chi(G) = 5,

This isn't a hypothesis; it's a fact about the coloring c. If 1,2,3,4,
and 5 are all colored with one of 3 colors, then v_0 can be colored
with the fourth color, and so Chi(G) = 4.

Graph H is not maximal. AN EDGE CAN BE ADDED BEWEEN V_2 & V_4!

I'll call this new graph H+e.

Now Figure 1 is not properly colored.

By c.

This can be corrected in several ways.

1. Vertex v_2 or v_4 can be colored "O"
2 Vertex v_2 can be colored Y.
3. Vertex v_4 can be colored B.

If (1), we are finished. G cannot be an MCE since H, a smaller graph,
is also 5-chroma.

No; it only shows that H+e _can_ be colored with 5 colors; it doesn't
show that H+e _requires_ 5 colors.

If (2), we add a second edge between v_2 & v_5.

Doing this might not result in a valid 4-coloring of H+e. For instance,
some neighbor of v_2 might be colored Y.

Even so, there still can be another coloring of this new graph (H+e+f)
that requries 4 colors. The only thing you've shown is that c isn't it.


You infer and imply that P(A/B) may be less that 1.000 but you would still ask me
to prove it!

That's your burden, as someone who claims there is a proof.

If (3), we add the second edge between v_1 & v_4.

Same comment.

Theoretically, every edge placement can be countered by a recoloring of Figure 1.
Without question, every recoloring can be countered by a legitimate repositioning
of one of the edges.


For some reason, the last two paragraphs of my last message have been
deleted. WHY?

This is not a probabilistic result.

Is this just your opinion or is it commonly held decision that is documented
somewhere?

It is a consequence of the statement of the 4CT:

THEOREM. For every planar map, there is a way to color it with at most
4 colors.

Note that the 4CT is NOT stated as:

THEOREM'. For 90% of all planar maps, there is a way to color them with
at most 4 colors.

or

THEOREM''. For all planar maps, there is a 90% chance of it being able
to be colored with at most 4 colors.

WHAT I AM TRYING TO PROVE IS THAT NO GRAPH WITH A FIVE-DEGREE
VERTEX CAN BE AN MCE!

There's no need to shout.

Sorry! I don't have italics, bolding or underlining.! Capitals are the only way I can
emphasize something.

Usenet ettiquette says that you can put _underlines_ or *asterisks*
around things you want to emphasize.


Getting back to the deleted paragraphs might be easier. You wrote:

] Consider Figure 1 as having two states.
] State A: Figure 1 is properly 4-colored
] State B Figure 1 is not properly colored.
]
] P(B/A) = 1; P(A/B) = ? [P(X/Y) means the probability
] of switching from state Y to state X]. If P(A/B) < 1,
] then the system will eventually halt in State B.
]
] This is far as I have gone. At some time in the future,
] it may be necessary to actually prove that
] P(A/B) < 1. [Too bad that the critics of the proof are
] not required to prove that P(A/B) = 1.000 ...0]

Critics of the proof don't have to prove anything; they would just have
to point out errors.

Suppose that I state categorically that P(A/B) < 1. A critic says that
P(A/B) = 1. Why should the burden of proof be on me rather than the
critic?. I have made no errors.

Once again, by claiming to have a proof, you have the burden of proof.
If you state something, the critic has a right to require that you
prove it.

Whenever anyone claims that they've proved a
result, they have the burdon of proof. Sometimes a proof is provided by
the critics as a response, though.

Another thing it's not just Figure 1 that needs to be properly
4-colored; the whole graph must be.

and Figure 1 can never be 3-colorable!

Yes, it can. (For instance, if Figure 1 is all of G-v_0.) But that's
not relevant to the 4CT.

--- Christopher Heckman

.

Relevant Pages
Quantcast