[proofplan] We first prove the universal upper bound by splitting a common independent set across an arbitrary subset of the ground set. For the reverse inequality, choose a maximum common independent set and build its standard exchange digraph. Since the common independent set is maximum, there is no augmenting path; the vertices reachable from the elements addable in the first matroid determine a complementary cut. The absence of crossing exchange arcs forces the cut side to be spanned in the first matroid by the selected elements it contains, and forces the reachable side to be spanned in the second matroid by the selected elements it contains, giving equality for this particular cut. [/proofplan] [step:Bound every common independent set by every rank cut] Let $J\subset E$ be a set such that $J\in\mathcal I_1\cap\mathcal I_2$, and let $A\subset E$. Since $J\cap A\subset A$ and $J\cap A\in\mathcal I_1$, the definition of $r_1(A)$ gives \begin{align*} |J\cap A|\le r_1(A). \end{align*} Similarly, since $J\cap(E\setminus A)\subset E\setminus A$ and $J\cap(E\setminus A)\in\mathcal I_2$, the definition of $r_2(E\setminus A)$ gives \begin{align*} |J\cap(E\setminus A)|\le r_2(E\setminus A). \end{align*} The two sets $J\cap A$ and $J\cap(E\setminus A)$ are disjoint and their union is $J$, so \begin{align*} |J| = |J\cap A|+|J\cap(E\setminus A)| \le r_1(A)+r_2(E\setminus A). \end{align*} Taking the maximum over all common independent sets $J$ and then the minimum over all subsets $A\subset E$ yields \begin{align*} \max\{ |J| : J\in\mathcal I_1\cap\mathcal I_2\} \le \min_{A\subset E}\bigl(r_1(A)+r_2(E\setminus A)\bigr). \end{align*} [/step] [step:Construct the exchange digraph of a maximum common independent set] Let $I\subset E$ be a common independent set of maximum cardinality, so $I\in\mathcal I_1\cap\mathcal I_2$ and \begin{align*} |I|=\max\{ |J| : J\in\mathcal I_1\cap\mathcal I_2\}. \end{align*} For $k\in\{1,2\}$ and $B\subset E$, define the closure of $B$ in $M_k$ by \begin{align*} \operatorname{cl}_{M_k}(B) := \{e\in E : r_k(B\cup\{e\})=r_k(B)\}. \end{align*} We will use the following elementary consequences of the matroid circuit axioms. If $B\in\mathcal I_k$ and $e\in E\setminus B$ with $B\cup\{e\}\notin\mathcal I_k$, then $B\cup\{e\}$ contains a unique circuit, denoted $C_k(e,B)$, and $e\in C_k(e,B)$. Moreover, for $b\in B$, the set $(B\setminus\{b\})\cup\{e\}$ is independent in $M_k$ exactly when $b\in C_k(e,B)$. We will also use the circuit elimination axiom in the following form: if $C$ and $C'$ are distinct circuits, $a\in C\cap C'$, and $b\in C\setminus C'$, then there is a circuit contained in $(C\cup C')\setminus\{a\}$ that contains $b$. Define the $M_1$-source set $S_I\subset E\setminus I$ by \begin{align*} S_I:=\{e\in E\setminus I : I\cup\{e\}\in\mathcal I_1\}. \end{align*} Define the $M_2$-target set $T_I\subset E\setminus I$ by \begin{align*} T_I:=\{e\in E\setminus I : I\cup\{e\}\in\mathcal I_2\}. \end{align*} Define a directed graph $D(I)$ with vertex set $E$ as follows. For $y\in I$ and $x\in E\setminus I$, put an $M_1$-exchange arc \begin{align*} y\longrightarrow x \end{align*} whenever $(I\setminus\{y\})\cup\{x\}\in\mathcal I_1$. Put an $M_2$-exchange arc \begin{align*} x\longrightarrow y \end{align*} whenever $(I\setminus\{y\})\cup\{x\}\in\mathcal I_2$. [claim:There is no augmenting path from $S_I$ to $T_I$] There is no directed path in $D(I)$ from $S_I$ to $T_I$. [/claim] [proof] Suppose that there were a directed path \begin{align*} P=(p_0,p_1,\dots,p_m) \end{align*} in $D(I)$ with $p_0\in S_I$ and $p_m\in T_I$. Choose such a path with minimal length. Since all arcs of $D(I)$ go between $I$ and $E\setminus I$, and since $p_0\in E\setminus I$, the vertices alternate: \begin{align*} p_{2j}\in E\setminus I,\qquad p_{2j+1}\in I \end{align*} whenever the displayed vertices occur. Since $p_m\in T_I\subset E\setminus I$, the integer $m$ is even. No internal even vertex $p_{2j}$ with $1\le j\le m/2-1$ belongs to $S_I\cup T_I$: if $p_{2j}\in T_I$, the initial segment from $p_0$ to $p_{2j}$ is a shorter path from $S_I$ to $T_I$, while if $p_{2j}\in S_I$, the terminal segment from $p_{2j}$ to $p_m$ is a shorter path from $S_I$ to $T_I$. Thus every internal even vertex is dependent over $I$ in both matroids in the relevant places where a fundamental circuit is used. Define \begin{align*} I' := I\triangle \{p_0,p_1,\dots,p_m\} = \bigl(I\setminus\{p_1,p_3,\dots,p_{m-1}\}\bigr) \cup \{p_0,p_2,\dots,p_m\}. \end{align*} Put $\ell:=m/2$, and for $0\le j\le \ell$ define $x_j:=p_{2j}\in E\setminus I$, while for $1\le j\le \ell$ define $y_j:=p_{2j-1}\in I$. Thus the path has the form \begin{align*} x_0,y_1,x_1,\dots,y_\ell,x_\ell. \end{align*} The arcs of $P$ imply \begin{align*} (I\setminus\{y_j\})\cup\{x_j\}\in\mathcal I_1 \end{align*} for $1\le j\le \ell$, and \begin{align*} (I\setminus\{y_j\})\cup\{x_{j-1}\}\in\mathcal I_2 \end{align*} for $1\le j\le \ell$. Also $x_0\in S_I$ gives $I\cup\{x_0\}\in\mathcal I_1$, and $x_\ell\in T_I$ gives $I\cup\{x_\ell\}\in\mathcal I_2$. We first prove $I'\in\mathcal I_1$. For $1\le j\le \ell$, the element $x_j$ is not in $S_I$: this follows from the preceding paragraph when $j<\ell$, and follows from $x_\ell\in T_I$ together with the absence of a shorter path of length zero when $\ell=0$. Hence $I\cup\{x_j\}\notin\mathcal I_1$ whenever the fundamental circuit below is needed. Let \begin{align*} C_{1,j}:=C_1(x_j,I)\subset I\cup\{x_j\} \end{align*} denote the fundamental circuit of $x_j$ over $I$ in $M_1$. The $M_1$-exchange arc $y_j\to x_j$ and the single-element exchange criterion give $y_j\in C_{1,j}$. If $i<j$ and $y_i\in C_{1,j}$, then the same criterion gives an $M_1$-arc $y_i\to x_j$. Since $y_i$ occurs before $x_j$ on $P$, replacing the subpath from $y_i$ to $x_j$ by this single arc and then following the remaining part of $P$ would give a shorter directed path from $S_I$ to $T_I$, contradicting the minimality of $P$. Hence \begin{align*} C_{1,j}\cap\{y_1,\dots,y_{j-1}\}=\varnothing. \end{align*} Define $I_{1,0}:=I\cup\{x_0\}$ and, for $1\le j\le \ell$, \begin{align*} I_{1,j}:=(I\setminus\{y_1,\dots,y_j\})\cup\{x_0,x_1,\dots,x_j\}. \end{align*} The set $I_{1,0}$ is independent in $M_1$ by $x_0\in S_I$. Suppose $I_{1,j-1}\in\mathcal I_1$. We prove that $I_{1,j}\in\mathcal I_1$. If $I_{1,j-1}\cup\{x_j\}$ is independent, then its subset $I_{1,j}$ is independent. Otherwise let $C$ be a circuit contained in $I_{1,j-1}\cup\{x_j\}$. Since $I_{1,j-1}$ is independent, $x_j\in C$. If $C$ avoids $y_j$, then $C$ is not contained in $I\cup\{x_j\}$ because the only circuit in $I\cup\{x_j\}$ is $C_{1,j}$ and $y_j\in C_{1,j}$. Thus $C$ contains some previously inserted element $x_i$ with $0\le i<j$. Choose the least index $i$ such that $x_i\in C$. We now remove the remaining inserted elements from $C$ one at a time, but only when they actually occur in the current circuit. More precisely, suppose the current circuit $C^*$ contains $x_i$, avoids $y_1,\dots,y_i$, and is contained in \begin{align*} I\cup\{x_i,x_{i+1},\dots,x_j\}. \end{align*} If $C^*\subset I\cup\{x_i\}$, stop. Otherwise let $h>i$ be the largest index with $x_h\in C^*$. The circuit $C_{1,h}$ also contains $x_h$, and the preceding shortest-path argument gives \begin{align*} C_{1,h}\cap\{y_1,\dots,y_{h-1}\}=\varnothing. \end{align*} Since $i<h$, this implies $C_{1,h}$ avoids $y_1,\dots,y_i$. Also $x_i\notin C_{1,h}$, because $C_{1,h}\subset I\cup\{x_h\}$ and $x_i\notin I\cup\{x_h\}$. Applying circuit elimination to the distinct circuits $C^*$ and $C_{1,h}$ with common element $x_h$ and retained element $x_i$ produces a circuit contained in $(C^*\cup C_{1,h})\setminus\{x_h\}$ that still contains $x_i$ and still avoids $y_1,\dots,y_i$. By the maximal choice of $h$, the new circuit is contained in \begin{align*} I\cup\{x_i,x_{i+1},\dots,x_{h-1}\}. \end{align*} Repeating this finite procedure eliminates all inserted elements except $x_i$, giving a circuit contained in $I\cup\{x_i\}$ that contains $x_i$ and avoids $y_1,\dots,y_i$. If $i=0$, this contradicts $I\cup\{x_0\}\in\mathcal I_1$. If $i\ge1$, the uniqueness of the fundamental circuit in $I\cup\{x_i\}$ forces the resulting circuit to be $C_{1,i}$, but $C_{1,i}$ contains $y_i$, again a contradiction. Therefore every circuit in $I_{1,j-1}\cup\{x_j\}$ contains $y_j$, and removing $y_j$ leaves the independent set $I_{1,j}\in\mathcal I_1$. Induction gives $I_{1,\ell}=I'\in\mathcal I_1$. We next prove $I'\in\mathcal I_2$ by the reverse argument. For $0\le j\le \ell-1$, the element $x_j$ is not in $T_I$: this follows from the preceding paragraph when $j>0$, and if $j=0$ then $x_0\in T_I$ would give a path of length zero from $S_I$ to $T_I$. Hence $I\cup\{x_j\}\notin\mathcal I_2$ whenever the fundamental circuit below is needed. Let \begin{align*} C_{2,j}:=C_2(x_j,I)\subset I\cup\{x_j\} \end{align*} denote the fundamental circuit of $x_j$ over $I$ in $M_2$. The $M_2$-exchange arc $x_j\to y_{j+1}$ and the single-element exchange criterion give $y_{j+1}\in C_{2,j}$. If $i>j+1$ and $y_i\in C_{2,j}$, then the same criterion gives an $M_2$-arc $x_j\to y_i$. Replacing the subpath from $x_j$ to $y_i$ by this single arc and then following the remaining part of $P$ would again produce a shorter directed path from $S_I$ to $T_I$, contradicting minimality. Hence \begin{align*} C_{2,j}\cap\{y_{j+2},\dots,y_\ell\}=\varnothing. \end{align*} Define $I_{2,\ell}:=I\cup\{x_\ell\}$ and, for $0\le j\le \ell-1$, \begin{align*} I_{2,j}:=(I\setminus\{y_{j+1},\dots,y_\ell\})\cup\{x_j,x_{j+1},\dots,x_\ell\}. \end{align*} The set $I_{2,\ell}$ is independent in $M_2$ by $x_\ell\in T_I$. Descending induction on $j$ shows that $I_{2,j}\in\mathcal I_2$. Indeed, assume $I_{2,j+1}\in\mathcal I_2$. If $I_{2,j+1}\cup\{x_j\}$ is independent, then its subset $I_{2,j}$ is independent. Otherwise let $C$ be a circuit contained in $I_{2,j+1}\cup\{x_j\}$. Since $I_{2,j+1}$ is independent, $x_j\in C$. If $C$ avoids $y_{j+1}$, then $C$ must contain some inserted element $x_i$ with $j<i\le \ell$. Choose the greatest index $i$ such that $x_i\in C$. We remove the remaining inserted elements from $C$ one at a time, but only when they actually occur in the current circuit. More precisely, suppose the current circuit $C^*$ contains $x_i$, avoids $y_{i+1},\dots,y_\ell$, and is contained in \begin{align*} I\cup\{x_j,x_{j+1},\dots,x_i\}. \end{align*} If $C^*\subset I\cup\{x_i\}$, stop. Otherwise let $h<i$ be the smallest index with $x_h\in C^*$. The circuit $C_{2,h}$ also contains $x_h$, and the preceding shortest-path argument gives \begin{align*} C_{2,h}\cap\{y_{h+2},\dots,y_\ell\}=\varnothing. \end{align*} Since $h<i$, this implies $C_{2,h}$ avoids $y_{i+1},\dots,y_\ell$. Also $x_i\notin C_{2,h}$, because $C_{2,h}\subset I\cup\{x_h\}$ and $x_i\notin I\cup\{x_h\}$. Applying circuit elimination to the distinct circuits $C^*$ and $C_{2,h}$ with common element $x_h$ and retained element $x_i$ produces a circuit contained in $(C^*\cup C_{2,h})\setminus\{x_h\}$ that still contains $x_i$ and still avoids $y_{i+1},\dots,y_\ell$. By the minimal choice of $h$, the new circuit is contained in \begin{align*} I\cup\{x_{h+1},x_{h+2},\dots,x_i\}. \end{align*} Repeating this finite procedure eliminates all inserted elements except $x_i$, giving a circuit contained in $I\cup\{x_i\}$ that contains $x_i$ and avoids $y_{i+1},\dots,y_\ell$. If $i=\ell$, this contradicts $I\cup\{x_\ell\}\in\mathcal I_2$. If $i<\ell$, uniqueness of the fundamental circuit in $I\cup\{x_i\}$ forces the resulting circuit to be $C_{2,i}$, but $C_{2,i}$ contains $y_{i+1}$, a contradiction. Therefore every circuit in $I_{2,j+1}\cup\{x_j\}$ contains $y_{j+1}$, and removing $y_{j+1}$ leaves the independent set $I_{2,j}\in\mathcal I_2$. Therefore $I_{2,0}=I'\in\mathcal I_2$. Combining the two conclusions gives \begin{align*} I'\in\mathcal I_1\cap\mathcal I_2. \end{align*} Moreover $I'$ removes $m/2$ elements of $I$ and adds $m/2+1$ elements of $E\setminus I$, so \begin{align*} |I'|=|I|+1. \end{align*} This contradicts the maximality of $I$. Therefore no directed path in $D(I)$ begins in $S_I$ and ends in $T_I$. [/proof] [/step] [step:Use reachability to define the minimizing cut] Let $R\subset E$ be the set of vertices reachable in $D(I)$ from some vertex of $S_I$, where vertices of $S_I$ are counted as reachable by paths of length zero. Define \begin{align*} A:=E\setminus R. \end{align*} By the preceding claim, no vertex of $T_I$ is reachable, so \begin{align*} R\cap T_I=\varnothing. \end{align*} We will prove \begin{align*} r_1(A)=|I\cap A| \qquad\text{and}\qquad r_2(R)=|I\cap R|. \end{align*} Since $E\setminus A=R$, these identities will give \begin{align*} r_1(A)+r_2(E\setminus A) = |I\cap A|+|I\cap R| = |I|. \end{align*} [/step] [step:Show that $A$ is spanned by $I\cap A$ in $M_1$] Since $I\cap A\subset A$ and $I\cap A\in\mathcal I_1$, we have \begin{align*} r_1(A)\ge |I\cap A|. \end{align*} It remains to prove the opposite inequality. Let $x\in A\setminus I$. Since $x\notin R$, in particular $x\notin S_I$. Hence \begin{align*} I\cup\{x\}\notin\mathcal I_1. \end{align*} Because $I\in\mathcal I_1$, there is a unique fundamental circuit $C_1(x)\subset I\cup\{x\}$ of $x$ over $I$ in $M_1$. For each $y\in C_1(x)\setminus\{x\}$, the fundamental circuit exchange property gives \begin{align*} (I\setminus\{y\})\cup\{x\}\in\mathcal I_1. \end{align*} Thus $D(I)$ has an $M_1$-exchange arc $y\to x$ for every $y\in C_1(x)\setminus\{x\}$. If some $y\in C_1(x)\setminus\{x\}$ belonged to $R$, then the reachability of $y$ and the arc $y\to x$ would imply $x\in R$, contradicting $x\in A=E\setminus R$. Therefore \begin{align*} C_1(x)\setminus\{x\}\subset I\cap A. \end{align*} Since $C_1(x)\subset (I\cap A)\cup\{x\}$ is a circuit containing $x$, the element $x$ lies in $\operatorname{cl}_{M_1}(I\cap A)$. [guided] The goal is to prove that the elements of $A$ do not add any new $M_1$-rank beyond the elements of $I$ already lying in $A$. We already know that $I\cap A$ is independent in $M_1$, so \begin{align*} r_1(A)\ge |I\cap A|. \end{align*} To prove equality, it is enough to show that every element of $A\setminus I$ is spanned by $I\cap A$ in $M_1$. Fix $x\in A\setminus I$. Since $A=E\setminus R$, the element $x$ is not reachable from $S_I$. In particular $x\notin S_I$, because every element of $S_I$ is reachable by the length-zero path from itself. By the definition of $S_I$ this means \begin{align*} I\cup\{x\}\notin\mathcal I_1. \end{align*} The set $I$ is independent in $M_1$, so adding $x$ creates exactly one fundamental circuit in $M_1$; denote it by \begin{align*} C_1(x)\subset I\cup\{x\}. \end{align*} This circuit contains $x$. The single-element exchange criterion for the fundamental circuit applies because $I\in\mathcal I_1$ and $I\cup\{x\}\notin\mathcal I_1$: for an element $y\in I$, the set $(I\setminus\{y\})\cup\{x\}$ is independent in $M_1$ exactly when $y$ lies in $C_1(x)\setminus\{x\}$. Hence for every $y\in C_1(x)\setminus\{x\}$ the exchange digraph has the directed arc \begin{align*} y\longrightarrow x. \end{align*} Now suppose that some $y\in C_1(x)\setminus\{x\}$ belonged to $R$. Since $R$ is the set of vertices reachable from $S_I$, there is a directed path from $S_I$ to $y$. Appending the arc $y\to x$ would produce a directed path from $S_I$ to $x$, so $x$ would belong to $R$. This contradicts $x\in A=E\setminus R$. Therefore every element of $C_1(x)\setminus\{x\}$ lies outside $R$, and also lies in $I$ because $C_1(x)\subset I\cup\{x\}$. Thus \begin{align*} C_1(x)\setminus\{x\}\subset I\cap A. \end{align*} The circuit $C_1(x)$ is contained in $(I\cap A)\cup\{x\}$ and contains $x$, which is precisely the matroidal certificate that $x\in\operatorname{cl}_{M_1}(I\cap A)$. We have proved this for every $x\in A\setminus I$. Every element of $I\cap A$ belongs to $\operatorname{cl}_{M_1}(I\cap A)$ by containment, so \begin{align*} A\subset \operatorname{cl}_{M_1}(I\cap A). \end{align*} Taking ranks in $M_1$ gives \begin{align*} r_1(A)\le r_1(I\cap A). \end{align*} Since $I\cap A$ is independent in $M_1$, its rank is its cardinality: \begin{align*} r_1(I\cap A)=|I\cap A|. \end{align*} Together with the earlier inequality $r_1(A)\ge |I\cap A|$, this yields \begin{align*} r_1(A)=|I\cap A|. \end{align*} [/guided] We have shown that every element of $A\setminus I$ belongs to $\operatorname{cl}_{M_1}(I\cap A)$, while every element of $I\cap A$ belongs to $\operatorname{cl}_{M_1}(I\cap A)$ by containment. Hence \begin{align*} A\subset \operatorname{cl}_{M_1}(I\cap A). \end{align*} Therefore \begin{align*} r_1(A)\le r_1(I\cap A)=|I\cap A|. \end{align*} Combining this with the opposite inequality gives \begin{align*} r_1(A)=|I\cap A|. \end{align*} [/step] [step:Show that $R$ is spanned by $I\cap R$ in $M_2$] Since $I\cap R\subset R$ and $I\cap R\in\mathcal I_2$, we have \begin{align*} r_2(R)\ge |I\cap R|. \end{align*} Let $x\in R\setminus I$. Since $R\cap T_I=\varnothing$, we have $x\notin T_I$. Hence \begin{align*} I\cup\{x\}\notin\mathcal I_2. \end{align*} Because $I\in\mathcal I_2$, there is a unique fundamental circuit $C_2(x)\subset I\cup\{x\}$ of $x$ over $I$ in $M_2$. For every $y\in C_2(x)\setminus\{x\}$, the fundamental circuit exchange property gives \begin{align*} (I\setminus\{y\})\cup\{x\}\in\mathcal I_2. \end{align*} Thus $D(I)$ has an $M_2$-exchange arc $x\to y$ for every $y\in C_2(x)\setminus\{x\}$. If some $y\in C_2(x)\setminus\{x\}$ belonged to $A$, then the reachability of $x\in R$ and the arc $x\to y$ would imply $y\in R$, contradicting $y\in A=E\setminus R$. Therefore \begin{align*} C_2(x)\setminus\{x\}\subset I\cap R. \end{align*} Thus $x\in\operatorname{cl}_{M_2}(I\cap R)$. It follows that every element of $R$ lies in $\operatorname{cl}_{M_2}(I\cap R)$, so \begin{align*} r_2(R)\le r_2(I\cap R)=|I\cap R|. \end{align*} Combining both inequalities gives \begin{align*} r_2(R)=|I\cap R|. \end{align*} [/step] [step:Evaluate the cut and conclude equality] Since $A=E\setminus R$, the identities proved above give \begin{align*} r_1(A)+r_2(E\setminus A)=r_1(A)+r_2(R). \end{align*} Using $r_1(A)=|I\cap A|$ and $r_2(R)=|I\cap R|$, this becomes \begin{align*} r_1(A)+r_2(E\setminus A)=|I\cap A|+|I\cap R|. \end{align*} The sets $A$ and $R$ partition $E$, so $I\cap A$ and $I\cap R$ partition $I$. Therefore \begin{align*} r_1(A)+r_2(E\setminus A)=|I|. \end{align*} Since $I$ is a maximum common independent set, \begin{align*} |I|=\max\{ |J| : J\in\mathcal I_1\cap\mathcal I_2\}. \end{align*} The cut $A$ therefore satisfies \begin{align*} \min_{B\subset E}\bigl(r_1(B)+r_2(E\setminus B)\bigr) \le r_1(A)+r_2(E\setminus A) = \max\{ |J| : J\in\mathcal I_1\cap\mathcal I_2\}. \end{align*} Together with the upper bound from the first step, this proves \begin{align*} \max\{ |J| : J\in\mathcal I_1\cap\mathcal I_2\} = \min_{B\subset E}\bigl(r_1(B)+r_2(E\setminus B)\bigr). \end{align*} [/step]