Choose from a,b,c,d with at most two elements allowed. Their weights are 9, −1, −2, −5. A maximum-weight basis must fill a maximal independent choice: here, a pair. A maximum-weight independent set can have any allowed size, including zero. Predict the best set for each objective before using the checker. Weight means the sum of chosen element weights; cardinality means how many elements are chosen.
Predict
A decreasing-weight scan accepts a first. Should it accept b next? For a basis, yes: stopping at a leaves a nonmaximal set. The best basis is a,b, worth 8. For unrestricted weight, no: a alone is worth 9. A negative weight is not an error in the data; it exposes why the objective must be stated before applying an algorithm.
Experiment
Which choices does an exchange preserve?
Predict the next decision before stepping. This finite CPU checker uses predefined families and integer weights. Settings and traces are temporary; record a prediction, witness and explanation in your written practice. Replaying a case supplies no new independent evidence or automatic mastery.
Any subset of size at most two is independent. Ties use the displayed label order. A basis scan includes negative weights; the unrestricted scan omits negative candidates.
Axiom check: All finite independence axioms pass for this listed family. Checking this finite instance does not prove the general theorem.
Decision 1 of 4. Earlier decisions are retained only for these settings.
Retained prefix A
{}
Candidate
a: weight 9
Result
{a}
Independent extension accepted; total 9.
The candidate is already in B. No exchange is needed if the greedy scan accepts it.
This selected B need not be optimal. For the theorem’s invariant, also establish that B is optimal and contains the prior greedy prefix. The exchange lemma alone proves feasibility.
Reveal full trace and exhaustive comparison
Complete deterministic scan
Candidate
Prior set
Decision
Result
Weight
a
{}
Independent extension accepted
{a}
9
b
{a}
Independent extension accepted
{a, b}
8
c
{a, b}
Dependent extension rejected
{a, b}
8
d
{a, b}
Dependent extension rejected
{a, b}
8
Greedy: {a, b}, weight 8. Exhaustive optimum for the selected objective: 8; 1 tied optimum set(s): {a, b}.
The scan agrees with the exhaustive optimum for this instance. Agreement on one weight vector cannot establish augmentation. For a nonmatroid, maximal independent sets called “bases” here may have different sizes.
Enumerated 16 subsets; 16 one-element deletions and 52 candidate extensions checked for the axioms. Caps: 64 subsets, 384 deletion checks, 24,576 extension checks. These are operation counts, excluding sorting, optimum enumeration and rendering; no timing or complexity claim follows.
Keep the default uniform case and compare the two objectives. Then select the partition case. Before revealing the full trace, predict which elements of the second group must be accepted to make a basis. Choose a comparison basis containing the retained prefix, and identify an exchanged-out element that preserves that prefix. Finally try the failed family: a numerical agreement after changing weights cannot repair its augmentation witness.
Understand
Let E and I be a finite matroid, as defined in the basis-extension lesson. Give every element e a real weight w(e). The basis algorithm scans all elements in nonincreasing weight order, with a declared label order for ties. Start with the empty set A; accept an element exactly when adding it preserves independence. Scan negative weights too. We will prove that the resulting basis has maximum total weight.
A rejected element cannot become feasible later
Suppose p was rejected at prefix P, so P together with p was dependent. Every later prefix A contains P. If A with p were independent, heredity would make its subset P with p independent, a contradiction. Thus a rejection remains valid as the accepted set grows. At the end, no rejected element can extend the final set, so that set is maximal and hence a basis.
Keep an optimal basis compatible with every accepted choice
Our invariant is a statement maintained after each acceptance: some maximum-weight basis B contains the current prefix A. There is at least one basis, and finitely many of them, so a maximum exists. Initially any optimum contains the empty prefix.
Suppose the scan next accepts g. If g already belongs to B, the same optimal B contains the new prefix. Otherwise apply the preserved-prefix lemma to A, B and g. It gives a basis B′ obtained by adding g and removing some b from B outside A. Every prior accepted choice is retained.
Because A together with b is a subset of B, it is independent. Therefore b cannot have been rejected earlier: rejection persistence would contradict that independence. It has not been accepted either, since it is outside A. So b is still unprocessed when g is scanned. The decreasing order gives w(g) ≥ w(b), even with negative weights or ties.
The total weight of B′ is the weight of B plus w(g) minus w(b), at least the optimal value. Since B was already optimal, B′ is also optimal. It contains the new prefix, completing the induction. At the end, the greedy prefix is itself a basis and lies inside an optimal basis. Equal basis size forces equality, proving optimality.
This proof separates feasibility from value: the extension lemma preserves earlier choices, while processing order proves the weight inequality. The checker’s selected comparison basis need not be optimal, so an exchange displayed there illustrates the lemma, not automatically the entire optimality invariant.
The unrestricted objective and minimum costs
For maximum-weight independent sets of arbitrary size, remove all negative elements from consideration. Deleting a negative element from an independent set preserves feasibility and increases its weight, so an optimum uses none. Restriction to the remaining elements preserves heredity and augmentation. Extend an optimum in that restriction to a basis; all added weights are nonnegative, so the weight cannot decrease. The basis theorem then proves that greedy in the restriction attains the unrestricted optimum. Zero-weight additions are optional for this objective.
For minimum-cost bases, negate costs and apply the maximum theorem, equivalently scan increasing costs. A disconnected graphic matroid has a spanning-forest basis; calling it a spanning tree would be false. Rank-zero families have the empty basis, of weight zero. Deterministic tie breaking selects a witness, not a proof of uniqueness: U₂,₄ with four weights equal to one has six optimal bases, whereas weights 4,4,0,0 give a unique optimum despite ties.
A non-graphic example: why the broader proof was needed
U₂,₄ is not the forest family of any finite undirected graph. Every singleton and every pair is independent, which excludes loops and parallel edges. A graph representing it would therefore be simple and have rank two. Graph rank is the sum, over connected components, of the component’s vertex count minus one: a spanning tree in each component has that many edges.
Rank two permits one nontrivial three-vertex component, with at most three simple edges, or two two-vertex components, with at most two edges altogether. Isolated vertices add none. Neither arrangement can supply the four required edges. Thus this capacity example cannot be justified merely by repeating the graphical cut argument. The uniform-family axiom proof and general greedy theorem apply directly.
Structural failure is more informative than one bad score
Allow every subset of either a alone or the pair b,c. This family is hereditary, but A consisting of a and B consisting of b,c violate augmentation. With weights 3,2,2, the decreasing scan selects a of weight 3, while b,c gives 4. With weights 0,2,2, the same scan succeeds. The family still violates augmentation: changing weights has not changed its sets. A successful run does not establish the theorem’s hypotheses.
In a nonmatroid we may still use “basis” to mean inclusion-maximal independent set, but those sets need not have equal size. The checker enumerates that objective separately from arbitrary-size weight optimization. It does not substitute maximum cardinality for either objective.
Apply
In the partition case, capacities are one from a,b,c and two from d,e,f. Default weights are 8,7,6,5,−1,−2. Explain why the best basis is a,d,e with weight 12, while unrestricted weight is maximized by a,d with weight 13. With retained a and comparison basis a,e,f, insert d: which deletions preserve the prefix, and what are the two weight changes? Record the predicted and observed results separately.
For a changed case, attempt the mixed objective-and-exchange audit before opening its solution. Keep your initial argument, failed assumption checks and revision. The general proof is mathematical evidence; a saved written response still requires human review.
Continue
Return to basis extension if the exchange could delete a previous choice. Return to minimum spanning trees to connect minimum costs to graphic cut certificates. The broader combinatorics unit keeps its other proof and assessment obligations.
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
For arbitrary real weights on a finite matroid, prove that the decreasing-weight greedy scan returns a maximum-weight basis. Explain why an exchanged-out element cannot have been rejected earlier.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For U₂,₄ with weights a=9,b=−1,c=−2,d=−5, solve the maximum-weight basis and unrestricted independent-set problems. Prove how a nonnegative restriction solves the second objective. Translate the basis theorem to minimum costs.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
On U₂,₄ give all maximum-weight bases when every weight is one. What does label-order tie breaking prove? Compare weights (4,4,0,0).
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Show that U₂,₄ cannot be the independent-edge family of any finite undirected graph, including graphs initially allowed loops and parallel edges. Then explain why its signed-weight optimum follows from the matroid proof rather than a spanning-tree argument.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For the hereditary family of subsets of {a} or {b,c}, use weights (3,2,2) to exhibit greedy failure. Then choose new weights where greedy succeeds. Does that repair the failed axiom?
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Use the checker’s partition case with default weights (8,7,6,5,−1,−2). Predict both objectives before revealing the full trace. Record the independent optimum, a valid prefix exchange, the axiom-check bounds, and one limitation of enumeration.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
