2 ms·

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 sub

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.

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.