An Unusual Proof of the Doodle Theorem | Hacker News Reader

An Unusual Proof of the Doodle Theorem

solipsys.co.uk

17 pointsColinWright7 comments

You provide a bit of context but if you could explain even more terms it would be great for someone like me that is only vaguely familiar with graph theory. I can follow the general argument and some extra pointers would be greatly appreciated.

Can you be a little more specific about what you need more details on? I'd be happy to write a little more, put some extra links or text boxes to clarify, but I'm not sure what people need explaining.

Does this help?

http://www.solipsys.co.uk/new/GraphThreeColouring.html?HN2

Feel free to email if you'd prefer, I'll go and start reviewing it.

Thanks!

Edit: I've now added a side-box with that link.

Not the original poster, but one thing that confused me was that I can clearly draw a graph that cannot be two coloured with a single pen stroke if I am allowed to reverse direction and keep drawing back over the same line again (indeed it is of course possible to draw any connected graph this way). I wasn't sure which part of the conditions forbid this.

Perhaps it is no longer a graph if I have a bidirectional edge? Or perhaps it is not considered planar if two edges coincide?

Ah, it's not allowed to go back exactly over the same line, so you can't reverse direction. You can go back and revisit the same node, but it will require a separate edge, and the two parts of the stroke will then encompass another area.

I'll add that - thanks!

Edit: now added - it will go live when the page updates.

I'd really appreciate comments on this - anything you feel like saying about it.

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 about why anyone is thinking about this stuff in the first place.

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

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.

Reply on news.ycombinator.com