Hacker News Reader

Comment by Bootvis | Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com