2
$\begingroup$

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?

1 Answers 1

2

Hint: $k=1$ suffices. Be creative.

  • 0
    @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!2011-07-06