1
$\begingroup$

I'm given an assignment to prove that a cycle basis has the properties of a matroid. But I'm having problems trying to understand the paragraph below excerpted from here

Let a matroid be a set of elements M, and a family of nonempty subsets C1, C2, etc, which we will call cycles. No cycle is a proper subset of another cycle, and the union of two different cycles, minus their intersection, is or contains another cycle.

To show equivalence, begin with a matroid defined in terms of cycles, and let independent sets be subsets of M that contain no cycles[1]. Clearly the subset of an independent set contains no cycles, hence it is another independent set. Let V be the largest independent set[2]. Adding any element x to V will produce at least one cycle. However, adding x cannot produce more than one cycle, since the set C1+C2, with x crossed out, would be a subset of V, and V would contain a cycle. Therefore adding x and deleting one of the other elements in the resulting cycle produces a new maximal independent set. Thus V can be gradually transformed into any other independent set U, by taking any element x in U-V, adding it to V, and deleting an element from V-U. Once all elements are transferred, the new independent set contains U, and is as large as V.

I drew a graph with 4 vertices ABCD that looked like a square.
AB
CD
Let's say C1 = {AB, BC, CA} and C2 = {BC, CD, DB}
An example of [1] could be any combination of {AB, BC, CD}, right?
An example of V would be {AB, BC, CD}, correct?
Now I suppose x = AC, adding x to V would indeed create at least one cycle, great!
But I'm lost here. C1+C2 with x crossed out would give me {AB, BC, CD, DB}.
How is this a subset of V?

1 Answers 1

1

The assumption in the text is that $V \cup \{ x \}$ contains two cycles $C_1$ and $C_2$; then $(C_1 \cup C_2) \setminus \{ x \}$ would be a subset of $V$ (and this would lead to a contradiction, so the situation can never happen). In your example, $C_2$ is not a cycle in $V \cup \{ x \} = \{AB,BC,CD,AC\}$, since $C_2$ contains the edge $DB$ which is not in $V \cup \{ x \}$.

  • 0
    "Adding any element x to V will produce at least one cycle"; a cycle in $V \cup \{ x\}$, that is. And then they want to show that there can't be *two* cycles in $V \cup \{ x\}$. So assume that there are two cycles $C_1$ and $C_2$ (in $V \cup \{ x\}$; this is understood but not stated explicitly), and derive a contradiction.2011-04-06