TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 18
Zur Navigation springen
Zur Suche springen
18) Let M=(E, S) be a matroid and A⊆E. The rank r(A) of A is defined as the cardinality of a maximal independent subset of A. Prove that for all A, B ⊆ E we have
- (a) r(A) ≤ |A|,
- (b) A⊆B implies r(A) ≤ r(B),
- (c) r(A∩B) + r(A∪B) ≤ r(A) + r(B).