2 ms·
This isn't a big theorem - to some extent it's just a trivial observation. But it is a gateway into talking about graph theory. Why should it be that a doodle
by ColinWright 11y ago
This isn't a big theorem - to some extent it's just a trivial observation. But it is a gateway into talking about graph theory.
Why should it be that a doodle is always two-colorable? It's a question a child could ask, but it leads to the whole area of graph theory. Personally, I find it a much better introduction to Graph Theory than the usual question about the Bridges of Königsberg:
https://en.wikipedia.org/wiki/Seven_Bridges_of_Königsberg https://en.wikipedia.org/wiki/Seven_Bridges_of_Königsberg
But there is a progression.
* A doodle is two-colorable
* A doodle is a planar, connected, Eulerian graph
* The dual of a planar, connected, Eulerian graph is bi-partite
* Bi-partite graphs are trivial to identify, and trivial to colour.
* What about tri-partite graphs?
* Identifying whether a given graph is tri-partite is NP-Complete.