Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
Three houses each need a path to each of three wells, nine paths in all, drawn on flat ground. The paths may bend but may not cross. This is the graph .
Prove that the nine paths cannot all be drawn. Explain why every face of a planar drawing of would need at least edges. Use Euler's formula to find the largest number of edges a planar graph on vertices with no triangle can have. Then do the same for , with .
For a connected planar drawing . A simple planar graph with has , and when it has no triangle. Every red and blue colouring of has a one-colour triangle.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. No triangle. is bipartite, so every cycle has even length. A face is bounded by a cycle, so it has at least edges.
Step 2. Count. , so . Euler's formula gives , so for .
Step 3. Contradiction. has edges, more than . So no planar drawing exists.
Step 4. . Here faces have at least edges, so . But has edges, so it is not planar either.
Answer: the bounds are and , and and exceed them. Proof complete.
Log in to join the discussion.
Loading…