# Difficulty in understand the proof of the lemma : “Matroids exhibit the optimal-substructure property” I was going through the text "Introduction to Algorithms" by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma I give a brief description of the possible prerequisites for the lemma.

Let $$M=(S,\ell)$$ be a matroid where $$S$$ is the ground set and $$\ell$$ is the family of subsets of $$S$$ called the independent subsets of $$S$$.

Let us have an algorithm which finds an optimal subset of $$M$$ using greedy method as:

$$GREEDY(M,W):$$

$$1\quad A\leftarrow\phi$$

$$2\quad \text{sort S[M] into monotonically decreasing order by weight w }$$

$$3\quad \text{for each x\in S[M] , taken in monotonically decreasing order by weight w(x) }$$

$$4\quad\quad \text{do if A\cup\{x\} \in \ell[M] }$$

$$5\quad\quad\quad\text{then A\leftarrow A\cup \{x\} }$$

$$6\quad \text{return A }$$

I was having a problem in understanding a step in the proof of the lemma below.

Lemma: (Matroids exhibit the optimal-substructure property)

Let $$x$$ be the first element of $$S$$ chosen by $$GREEDY$$ for the weighted matroid $$M = (S, \ell)$$. The remaining problem of finding a maximum-weight independent subset containing $$x$$ reduces to finding a maximum-weight independent subset of the weighted matroid $$M’ = (S’, \ell’)$$, where

$$S’ = \{y\in S:\{x,y\}\in \ell\}$$ ,

$$\ell’ = \{В \subseteq S – \{x\} : В \cup \{x\} \in \ell\}$$ ,

and the weight function for $$M’$$ is the weight function for $$M$$, restricted to $$S’$$. (We call $$M’$$ the contraction of $$M$$ by the element $$x$$.)

Proof:

1. If $$A$$ is any maximum-weight independent subset of $$M$$ containing $$x$$, then $$A’ = A — \{x\}$$ is an independent subset of $$M’$$.

2. Conversely, any independent subsubset $$A’$$ of $$M’$$ yields an independent subset $$A = A’\cup\{x\}$$ of $$M$$.

3. We have in both cases $$w(A) = w(A’) + w(x)$$.

4. Since we have in both cases that $$w(A) = w(A’) + w(x)$$, a maximum-weight solution in $$M$$ containing $$x$$ yields a maximum-weight solution in $$M’$$, and vice versa.

I could understand $$(1),(2),(3)$$. But I could not get how the line $$(4)$$ was arrived in the proof from $$(1),(2),(3)$$. especially the part in bold-italics. Could anyone please make it clear to me. Posted on Categories proxies