# Show that $\mathcal{F}_{G}$ is an Independence System, but in general is no Matroid

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.
First: Thanks for the hint. If the maximum degree of $A$ is one (meaning $A$ contains only one edge) the maximum degree of $B$ must be chosen as zero. That means $B$ has no edges at all. Then we have $|A|<|B|$. To break the exchange property of matroids I have only the one edge $e$ in $A$ which is not in $B$. If I add $e$ to $B$ the maximum degree of $B$ would still not be greater then $1=k$ and $B$ is still in $\mathcal{F}_{G}$. Perhaps I am blind, but I can't see how to produce a contradiction for $k=1$. :-) – Aufwind Jul 6 '11 at 17:57
@Aufwind: You need to be a little more creative: $A$ can have maximum degree $1$ and more than one edge. A graph with $3$ edges suffices. – Brian M. Scott Jul 6 '11 at 18:30
@Brian M. Scott: After reading your comment I realized, that I misunderstood the meaning of the exchange property M3 in the case of $\mathcal{F}_{G}$. Then this solution came to me: $A:=\{\{a,b\},\{c,d\}\}$ and $B:=\{a,c\}$. Each edge $e$ from $A$ will make $B$ a dependent set after being added to $B$. Thanks a lot! – Aufwind Jul 6 '11 at 18:42