Past exam of the computer science course of the University of Oxford / 2023 / Combinatorial optimisation / 2 / c / viii / Solution

Write $r(Y)=r$. Since $y\notin \sigma (Y)$, the one-element increment bound gives $r(Y+y)=r+1$. Since $y\in \sigma (Y+x)$,But $Y+y\subseteq Y+x+y$ gives the reverse lower bound $r(Y+x+y)\ge r(Y+y)=r+1$. Hence $r(Y+x+y)=r(Y+y)$, which is precisely $x\in \sigma (Y+y)$. 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.