Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
The edges of are coloured red or blue. We know there is always one one-colour triangle. In fact there are always at least two.
Prove this. Call a pair of edges at a vertex mixed when they have different colours. Count mixed pairs at each vertex: a vertex with red and blue edges has mixed pairs, at most . A triangle that is not one colour has exactly two corners with a mixed pair. Find the most triangles that are not one colour, and so the fewest one-colour triangles.
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. Mixed pairs. At a vertex with red edges there are mixed pairs. Over vertices there are at most .
Step 2. Triangles that are not one colour. Such a triangle has two edges of one colour and one of the other. Exactly two of its corners see a mixed pair. Each mixed pair at a vertex lies in exactly one triangle.
Step 3. Count. So the number of triangles that are not one colour is (mixed pairs) .
Step 4. One-colour triangles. At least .
Check. Two disjoint red triangles with all other edges blue have exactly one-colour triangles. The program below tries all colourings and confirms the minimum.
Answer: at most mixed pairs, so at least one-colour triangles. Proof complete.
Log in to join the discussion.
Loading…