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

The rank of a matroid on a subset $A\subseteq X$ isThe matroid independence axioms imply that every maximal matroid independent set in $A$ has this cardinality. We write $A+x=A\cup \{x\}$, as in the source. Directly from the definition,For the last upper bound, deleting $x$ from any matroid independent set in $A+x$ leaves an independent subset of $A$.