> 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.