Hi I'm studying for a Combinatorial Optimization final and I've come across a question I can't solve and also can't seem to find any justification for online. As a preamble, are there any general techniques to proving something is a Matroid or is it usually just trying the arguments until you see a trick?
"Let $G$ be a digraph, $E=V(G)$ and fix $s \in V(G)$. Let $F$ be the set of all vertex sets $I \subseteq E$ such that there are edge-disjoint paths $(P_i)_{i \in I}$ where each $P_i$ is an $s-i$ path."
The properties for it to be an independence system seemed clear to me, but I can't make that step for it to be a matroid. I've tried considering Menger's theorem but it seems like there must be a counterexample in my head (which I know there isn't.) Can anyone give me a hand or a hint of where to go?
Cheers
Suppose that $A$ and $B$ are independent sets such that $|A|\leq |B|$.
then there is an independent subset $C$ of $B\cup A$ that contains $A$ and has cardinality $|B|$.
Let $B=\{b_1,b_2,\dots,b_m\}$. Start with $C_0=(b_0,b_1,\dots,b_m)$, we do the following step until $A\subseteq C_n$:
Pick an element $a\in A\setminus C_n$ and find a suitable $b\in C_n$ such that $C_{n+1}=C_n\setminus\{b\}\cup \{a\}$ is independent.
In order for our strategy to work we need to use specific paths however.
Here is how it works:
Start with fixed families of paths $P_a$ and $Q_b$ for $A$ and $B$
In each step we select $a$ arbitrarily and we consider the path $P_a$ . Next, consider the last edge $e$ of $P_a$ that is also inside one of the paths in $C_n$, let $c_{n,i}$ be the vertex corresponding to that path. We remove $x$ from $C_n$ and in turn we add $a$ along with the path for $a$ that starts the same way as the old path, except that after edge $e$ it follows the edges of $P_a$. Clearly these paths do not share edges. Now, suppose that $x$ was already in $A$, then notice that the "value" of $C_{n+1}$ decreases (because the edges of $P_a$ are disjoint). We define the "value" of $C_n$ as : $\sum\limits_{i=1}^m \text{(# of edges at the start of the $s-c_{n,i}$ path in $C_n$ that coincide with $Q_{b_i}$)}$. It follows that $x$ cannot always be inside $A$, so after a finite number of steps $A\subseteq C_n$.