Re: Minimum Counter-Example to the Four Color Theorem


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.

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.

--- Christopher Heckman

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

bill j

.

Relevant Pages

  • Re: 4CT
    ... Removing that vertex always results in a 4-colorable graph. ... You're talking about an arbitrary coloring (which has at least N/5 ... It would be closer to N/4 green vertices, but the number of green, blue, yellow and ... a mce MUST have a 5-coloring of this sort! ...
    (sci.math)
  • Re: Minimum Counter-Example to the Four Color Theorem
    ... The MCE/4CT is a simple loopless maximal planar graph. ... If the MCE starts out less than ... Note that when you're talking about "a coloring", ...
    (sci.math)
  • Re: Minimum Counter-Example to the Four Color Theorem
    ... The MCE/4CT is a simple loopless maximal planar graph. ... If the MCE starts out less than ... Note that when you're talking about "a coloring", ...
    (sci.math)
  • Re: Minimum Counter-Example to the Four Color Theorem
    ... The MCE/4CT is a simple loopless maximal planar graph. ... If the MCE starts out less than ... Note that when you're talking about "a coloring", ...
    (sci.math)
  • Re: Minimum Counter-Example to the Four Color Theorem
    ... The MCE/4CT is a simple loopless maximal planar graph. ... If the MCE starts out less than ... Note that when you're talking about "a coloring", ...
    (sci.math)
Quantcast