Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2023/combinatorial-optimisation/2/c/viii/solution

Write . Since , the one-element increment bound gives . Since ,
But gives the reverse lower bound . Hence , which is precisely . This is the matroid closure exchange property; it follows from one-element rank of a matroid increments and does not require exchanging an entire matroid basis.

New to topics? Read the docs here!