Given a connected graph $G=(V,E)$ let us define $M(G)=(E,I)$ where $I=\{E'\subseteq E | (V,E\backslash E') \text{ is connected}\}$.
When proving $M(G)$ is a Matroid we must show:
if $A,B\in I$ and $|B|<|A|$ then there is $x\in A\backslash B$ s.t. $B\cup \{x\}\in I$.
In other words, we have two sets of edges $A,B$ which can be removed from $E$ w/o making $G$ disconnected. We must show that if $|B|<|A|$, there's an edge $x$ in $A$ which isn't in $B$, that even after removing $B$'s edges can be removed while keeping G connected.
I'm having trouble proving this last statement. Should I be looking for a specific edge that could work, or formulate a general statement that will lead to its existence?
Many thanks.
For convenience, let $n = |V|$. Using $n-1$ edges to connect the $n$ nodes, you get a tree (connected + no circles).
Because $A \in I$, that means that $(V, E \text{ \ } A)$ is a connected graph. Therefore $|E \text{ \ } A| \ge n-1$ (otherwise the graph $(V, E \text{ \ } A)$ would not be connected).
$$|B| < |A| \Rightarrow |E \text { \ } B| > | E \text { \ } A |$$
Because of that, $|E \text{ \ } B| \ge n$, which means that there is at least one circle in the graph $(V, E \text{ \ } B)$. Since both $(V, E \text{ \ } A)$ and $(V, E \text{ \ } B)$ are connected graphs, there has to be one edge on a circle in $(V, E \text{ \ } B)$, which is not used in the graph $(G, E \text{ \ } A)$:
$$\exists e \in (E \text{ \ } B): e \notin (E \text{ \ } A) \\ \Leftrightarrow \exists e \in E: (e \notin B) \wedge (e \in A) \\ \Leftrightarrow \exists e \in (A \text{ \ } B) $$
By putting this edge $e$ into $B$, we remove an edge on a circle in $(V, E \text{ \ } B)$, without disconnecting the graph. Hence $(B \cup \left\lbrace e \right\rbrace) \in I$.
$\square$