3 ms·

I'd love some background on the problem - I'm a big fan of well-explained proofs like this, but I'm not a mathematician by trade and I like hearing a little bit

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