4 ms·
It required a notoriously hard-to-simplify proof, which required computer assisted brute force analysis. But an intuition is that a complete graph with four nod
by hawkice 7y ago
It required a notoriously hard-to-simplify proof, which required computer assisted brute force analysis. But an intuition is that a complete graph with four nodes is planar, and five is not. A (3,3) bipartite graph is also the smallest non-planar bipartite graph. That's probably good for answering "why would you suspect 4".
- jessriedel 7y agoTo save laymen a google: A complete graph is one where all the nodes are connected. A planar graph is one that can be draw in the plane without two lines intersecting.
- rocqua 7y agoNotably one you can draw on either a flat piece of paper or a sphere. On a torus, you need up to 7 colors.
- FreeFull 7y agoYeah, any graph of a sphere can be easily deformed to fit on a plane, with something like stereographic projection
- pmiller2 7y agoYep, and the proof that any graph that can be drawn without crossings on the torus can be properly colored with no more than 7 colors is vastly easier than the case for graphs drawn on the sphere/plane.