Let $k\in\mathbb{N}$ and $G$ be a graph. Define $$\mathcal{F}_{G}:=\{F\subset E(G): \Delta((V(G),F))\leq k\}$$
I want to show, that $(E(G),\mathcal{F}_{G})$ is always an Independence System but in general $(E(G),\mathcal{F}_{G})$ is no Matroid.
My approach:
- The empty set is always in $\mathcal{F}_{G}$ for every $k$ since the maximum degree $\Delta((V(G),\emptyset))$ is always zero and there for smaller then any valid $k$.
- Let $B\in\mathcal{F}_{G}$ and $A\subset B$. Since $B\in\mathcal{F}_{G}$ it is true that the maximum degree $\Delta((V(G),B))\leq k$. And because $A$ is a subset of edges of $B$ it is true, that for every node $v\in A$: $\delta(v)_A\leq\delta(v)_B$, meaning $\Delta((V(G),A))\leq\Delta((V(G),B))\leq k$.
To show, that this construction does not hold in general for Matroids, I tried to build an example, that breaks the exchange property (M3) of Matroids. So have to find a set $A$ and a set $B$ such that $|A|>|B|$ and there is no edge e in $A$, that I can add to $B$ such that $\Delta((V(G),B\cup\{e\}))\leq k$ is true. Right?
I considered loops and double edges in my counter examples, but I couldn't find one that actually breaks the property. Any suggestions?
Hint: $k=1$ suffices. Be creative.