Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 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 \}$.

share|improve this answer
    
I'm still confused. Exactly where was this assumption assumed? –  Some Noob Student Apr 6 '11 at 7:52
    
"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. –  Hans Lundmark Apr 6 '11 at 8:07

Your Answer

 
discard

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.