Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A connected planar graph with vertices is drawn without crossings, and every face of the drawing, the outside face included, is bounded by exactly edges. Such a drawing is called a triangulation.
Find the number of edges and the number of faces. Use the fact that each edge borders exactly two faces, together with Euler's formula. Then explain why no simple planar graph on vertices can have more edges than this one.
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. Faces and edges. Each face has edges and each edge borders faces, so .
Step 2. Euler's formula. , so and .
Step 3. Faces. . Check: .
Step 4. The most edges. Any simple planar graph with has . A triangulation reaches the bound, so no planar graph on vertices has more edges.
Answer: edges and faces.
Log in to join the discussion.
Loading…