4 ms·

Thanks for the insightful comment. >The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds by showing that there is

• ColinWright 4y ago
  My comment was: > The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example. You said: > Isn't this missing a crucial point? You seem to be saying: > 1. There is some (small) set S of graphs, all of which are 5-colorable This is not what it's saying. It's saying that these graphs cannot be in a minimal counter-example. That's different from simply saying that they are 5-colourable. > 2. Every planar graph has at least 1 sub-graph in S > 3. Therefore, all planar graphs are 5-colorable No, you've missed a bit of my comment. I said: > showing for each of those that it cannot be in a minimal counter example. So we have an unavoidable set U. So for every graph G there is an element S of U that is a sub-graph of G. But we have also shown for every element S of G that any graph containing S cannot be a minimal counter-example. We're not showing that these elements S of U are themselves 5-colourable, we are showing that any G containing S is not a counter-example to the theorem. So now suppose the theorem is false. That means there is a graph that requires 6 colours. From among those choose a minimal one, so M is a minimal counter-example. But the set U is unavoidable, so there is a S in U that is a subgraph of M. But any graph containing S cannot be a minimal counter-example, and we have our contradiction. Hence there are no counter-examples, and the theorem is true. For the Five Colour Theorem the unavoidable set U has only four graphs, so it's easy to check by hand. For the Four Colour Theorem in the original proof there were around 2000 elements of U, so it was infeasible to check by hand. That has been reduced to 633 graphs in U, but it's still tough to check by hand. The paper in the original submission here takes a different approach.
  • siftrics 4y ago
    Ah, thank you. The key to my misreading was this part: > showing for each of those that it cannot be in a minimal counter example I read "those" as "those subgraphs" rather than "those graphs". Thanks.
    • thaumasiotes 4y ago
      > I read "those" as "those subgraphs" rather than "those graphs". That is the correct reading; your mistake must be elsewhere? >> [the proof] proceeds by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example. No minimal counterexample to the claim [that a planar graph is 5-colorable] can contain any of these subgraphs. All planar graphs contain at least one of these subgraphs. Therefore, all planar graphs fail to satisfy the predicate "this graph is a minimal counterexample to the claim that all planar graphs are 5-colorable". The elaboration is very explicit that the theorem is "for every subgraph S in the unavoidable set U, that subgraph (S) cannot be contained in any minimal counterexample": >> we have also shown for every element S of G that any graph containing S cannot be a minimal counter-example.
    • ColinWright 4y ago
      As the sibling comment to this says, you must still be confused about something here. Let me expand. The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds as follows. Cleverly produce a set U of small graphs S that have the following properties: 1: For every graph G, there is an S in U such that S is a sub-graph of G; 2: If G is a counter-example to the theorem, and S from U is a sub-graph of G, then there is a smaller graph H that is also a counter-example. This is enough, because now let M be a minimal counter-example. By (1) there is an S from U that is a sub-graph of M. But by (2) there is then a smaller counter-example, contradicting the minimality of M. So there can be no counter examples. With that now in mind, here is the original statement: We proceed by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example. This is easily done by hand. I hope that helps.
• lmm 4y ago
  You don't just show that the graphs in S are 5-colourable. You show that they couldn't possibly be part of a minimal non-colourable graph (e.g. if a graph containing this subgraph is not 5-colourable, you can replace this subgraph with this simpler subgraph, and the larger graph will still be non-5-colourable).