Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.