Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/iii/paper-204/3/e/solution

Take and let with
Then , , and . Part d gives .
On a four-cycle, occurs exactly when all four edges are open, because the two length-two paths from to are the only disjoint witnesses. Hence
Choosing sufficiently small gives the two numerical inequalities in the question.

New to topics? Read the docs here!