3 ms·
> while a circle with an even number of nodes needs only two, even though both models seem similarly complex. This is touched on in the article. The triangle i
by squeaky-clean 9y ago
> while a circle with an even number of nodes needs only two, even though both models seem similarly complex.
This is touched on in the article. The triangle is a complete graph, each vertice is connected to each other. A 2 colored circular graph would not be a complete graph. It would have a ring or fan-out shape.
You could have graph with 3 vertices that is 2 colored, you just can't have each vertice be connected to each other one.
I don't have great intuition for graphs but I'm pretty sure something like a square or larger cannot be both complete and planar.
Or to bring it back to software, I think it's true that a small system where each piece can directly talk to each other piece is more complex than a large system where pieces only communicate with their neighbors.
- akud 9y ago> I don't have great intuition for graphs but I'm pretty sure something like a square or larger cannot be both complete and planar. A square can, (you put one node in the middle), but 5 and up can't be both complete and planar.
- squeaky-clean 9y ago> A square can, (you put one node in the middle) Clever!
- tomsmeding 9y agoI was talking about a circle in which only neighbouring nodes are connected: +---+ / \ + + \ / +---+ For 6, for example. This thing is two-colourable, while one with 5 nodes is only three-colourable. That's the instability I was referring to.