4 ms·
> I read "those" as "those subgraphs" rather than "those graphs". That is the correct reading; your mistake must be elsewhere? >> [the proof] proceeds by show
by 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.