In class we skipped a small part of the proof the following proposition.

Let C be a cycle and e be the most expensive element on the cycle. Assume all weights/costs are different. We claimed that this implies that the minimum cost basis does not include e.

The proof went by contradiction. Assume it does, and let B this basis. We showed that there is a cut D such that D and B intersect exactly in e only. Now both the cycle C and the cut D contain the element e. We used the property (proven previously) that the intersection of a cut and a cycle cannot be a single element. So there is a different element f also in both C and D. The claim whose proof we did not finish in class is that B-e+f is independent.

A number of you told me proofs, or sent me email with proofs. So far, here are two proofs that came out of this.

Proof 1. Suppose B-e+f  contains a cycle C'. We know that B-e is independent, so C' must contain f. Now we know that C' and D both contain f. But they cannot contain any other element as D and B intersect in e only. This is a contradiction as a cycle and a cut now intersect in exactly one element.

Proof 2. D is a cut, and by the minimality that must be a basis, B' that is disjoint from D-f. B' cannot avoid D, so B' and D intersect in exactly f. Now use property (ii) for B-e (which we know is independent), and B': there must be an element x in B' that can be added to B-e and make it a basis B-e+x. But the new basis cannot avoid D and B-e does, so the new element x must be from D. B' only has one element in D, namely f, so we must have added x=f.