Choose the right objective and certificate before treating an algorithm's answer as advice.
By the end: explain what a computed optimum establishes and what remains outside the graph.
Translate the claim into a question
A planner wants to connect four sites cheaply, deliver parcels quickly, and survive a cable outage. Those are distinct requirements. Minimum spanning tree optimizes total selected construction cost under a tree constraint. Shortest path minimizes one route cost. Maximum flow optimizes steady throughput under capacities. None silently includes the others.
Write the vertex and edge semantics, direction, units, objective, and hard constraints. Decide whether multiple uses share capacity, whether service changes over time, and which failures count. An exact solution to an underspecified or incorrect graph can be precisely wrong for the real decision.
Separate a proposed design from the journeys it permits
Suppose four depots A, B, C, and D need a new cable network. The available undirected links are AB costing 2, AC costing 3, BC costing 1, BD costing 4, and CD costing 2 construction units. There are no other links. A construction unit is an invented common budget unit, not a minute or a kilometer. Selecting AB, BC, and CD spends 5 and connects every depot. That calculation concerns which cables to build. A journey through the finished network is a different selection, made from cables that already exist.
This distinction changes what gets added. For construction, count each selected cable once, even if many journeys later use it. For a route from A to D in that selected tree, add the weights along AB, BC, and CD to obtain 5. A second route from A to C costs 3 under the same additive weights. Adding these two route costs would count AB and BC twice. That sum might describe repeated travel expenditure, but it is not the price of constructing the network. An audit must identify what one payment or one traversal means.
The same triangle has two different measurements
Edge or selection
Construction units
Travel minutes
AB
2
1
AC
2
1
BC
1
9
Tree AB + BC
3
A to C via B: 10
Tree AB + AC
4
A to C direct: 1
This separate example has exactly vertices A, B, C and undirected edges AB, AC, BC. Construction units count each built edge once. Travel minutes add only along the journey taken; they are independent input data.
Separate units can reverse a recommendation without changing any endpoints. Consider a paper example on vertices A, B, and C with exactly the undirected edges AB, AC, and BC. Their construction costs are 2, 2, and 1. Their travel times are instead 1, 1, and 9 minutes. The cheaper tree AB plus BC costs 3 to build, but its A-to-C journey takes 10 minutes. The tree AB plus AC costs 4 and gives that journey a one-minute direct link. Neither drawing position nor construction cost tells us those travel times. They are additional assumptions supplied for this comparison.
A hard constraint is a requirement that every acceptable answer must satisfy. An objective ranks the answers that satisfy those requirements. If every depot must remain connected after any one selected cable fails, the cost-5 tree is unacceptable before we compare its price with other designs. Removing BC leaves A and B separated from C and D. This is not a slightly worse objective value. It is a violation of the stated requirement. Treating resilience as a descriptive advantage rather than a constraint would allow a cheap but disallowed answer to win the comparison.
For the four-depot example, adding AC to the cost-5 tree makes a triangle around A, B, and C, but CD still provides D's only connection. Spending 3 more units therefore does not solve the all-cable failure requirement. Adding BD instead makes the cycle B-C-D-B, but AB still provides A's only connection. Both additions together give the full five-edge graph, which does survive any single edge loss because every edge has an alternative path between its endpoints. That establishes a structural property under the assumed failure event. It supplies no probability that cables will actually fail independently.
A failed tree edge separates two reachable groups
Only the selected tree AB, BC, CD is drawn. The dashed BC link is removed, leaving components {A, B} and {C, D}. Labels are construction costs, not geometric distances. The original available links AC and BD are not built in this design.
An audit can also find a cheaper resilient selection than all five links. AB, AC, BD, and CD form the cycle A-B-D-C-A and cost 11. Every depot remains reachable after any one of these four edges is removed. Any resilient connected simple graph on four vertices needs each degree to be at least two, so it needs at least four edges. Among the five possible four-edge subsets here, the other four leave a degree-one vertex. Thus this cycle is the cheapest resilient selection for these exact options, although it costs more than twice the minimum tree's 5.
Ask for a checkable certificate
A candidate route supplies evidence of reachability and an upper bound on minimum cost. Dijkstra's settling argument supplies optimality under its assumptions. A spanning tree must connect all vertices without cycles, and a minimum claim needs more than counting n minus one edges. A feasible flow plus an equal-capacity cut supplies a compact optimality certificate.
Look for counterexamples before trusting a broad claim. A single shorter route refutes a shortest-route assertion. A single failed edge that disconnects a selected tree refutes single-edge resilience. A worker subset with too few distinct jobs refutes a complete-assignment claim. Counterexamples attack the stated guarantee rather than an unrelated metric.
Verify the result without trusting the algorithm's name
A certificate is evidence that another person can check against the stated claim. Start with feasibility, which means obeying the constraints. For the proposed four-depot tree, verify that AB, BC, and CD are available original edges. Starting at A, they reach B, then C, then D. They contain no cycle and their weights total 5. These observations establish a spanning tree of cost 5. They do not yet establish minimum cost. An expensive tree could pass exactly the same connectivity and edge-count checks. Optimality needs a comparison with alternatives or a bound that rules those alternatives out.
Here a short lower-bound argument proves the minimum. Separate A from B, C, and D. Any connected selection must cross that separation, and the available choices AB and AC cost at least 2. Separately, connecting D requires BD or CD, costing at least 2. These are different edges because no AD edge exists. A four-vertex tree needs a third edge, and the cheapest edge anywhere is BC at 1. Consequently every spanning tree costs at least 5. The proposed tree attains that bound. This argument uses the actual edge list, not a claim that three cheap-looking lines must be optimal.
Each omitted edge can be checked against a tree path
Thick edges AB, BC, CD form the proposed cost-5 tree. Thin edges are available but omitted. AC costs 3 while the largest edge on A-B-C costs 2. BD costs 4 while the largest edge on B-C-D costs 2. Neither exchange reduces total construction cost. Positions are schematic.
Another check examines the edges left out of the proposed tree. Adding AC creates the cycle A-B-C-A. The existing tree path between A and C contains weights 2 and 1; replacing either with AC at 3 cannot reduce the total. Adding BD creates B-C-D-B, whose tree edges cost 1 and 2. BD at 4 cannot improve that tree either. More generally, a tree is minimum if every omitted edge costs at least the largest edge on its existing tree path. The exchange argument repeatedly removes such an edge when comparing against an alternative tree, without making that alternative more expensive.
Route optimality admits a different certificate. Label A, B, C, and D with proposed minimum costs 0, 2, 3, and 5 from A. For every undirected edge, check both directions. The label at the destination must be no greater than the starting label plus the edge weight. For AC, that reads 3 no greater than 0 plus 3 in one direction and 0 no greater than 3 plus 3 in the other. For BD, it reads 5 no greater than 2 plus 4 and 2 no greater than 5 plus 4. Check the remaining edges in the same way.
Why do these inequalities prove anything? Starting with A's label zero, apply the appropriate inequality at each successive edge of any route. The final label cannot exceed the sum of all traversed weights. Thus 5 is a lower bound on the cost of every A-to-D route. The tree route A-B-C-D actually costs 5, so it reaches that bound. Similarly, A-B costs 2 and A-B-C costs 3. The labels and the explicit routes together certify the optimum. Labels alone could underestimate every real route; routes alone could overlook a cheaper alternative. Both pieces are necessary for this check.
The proposed route labels satisfy every edge check
Edge and weight
Forward check
Reverse check
AB, 2
2 ≤ 0 + 2
0 ≤ 2 + 2
AC, 3
3 ≤ 0 + 3
0 ≤ 3 + 3
BC, 1
3 ≤ 2 + 1
2 ≤ 3 + 1
BD, 4
5 ≤ 2 + 4
2 ≤ 5 + 4
CD, 2
5 ≤ 3 + 2
3 ≤ 5 + 2
Proposed costs from A are A = 0, B = 2, C = 3, D = 5. Each row checks both allowed directions of an undirected edge. These inequalities give lower bounds on every route cost. The tree routes attain those bounds, completing the shortest-route certificate for these additive weights.
The tree certificate and the route certificate happen to succeed on the same selected edges here. That coincidence is informative because it prevents an overcorrection. Saying that an MST never preserves shortest routes would be as wrong as saying that it always does. The supported claim is narrower: this particular tree preserves costs 2, 3, and 5 from A when the construction weights are reused as additive route costs. It still fails the cable-outage constraint, and it has no certificate about minutes because the example never supplied travel times for these four depots. Each claim needs evidence with its own meaning.
Inspect the graph and its result
Compare construction and route objectives
Minimum spanning selection
Spanning tree. Total cost: 5.
Shortest-path selection from A
Route costs: 0, 2, 3, 5.
Selected edge total: 7. Unreachable vertices have no parent.
Edge by weight
Decision
B–C: 1
Join different components
A–B: 2
Join different components
C–D: 2
Join different components
A–C: 3
Reject cycle
B–D: 4
Reject cycle
A spanning forest includes every vertex but may have several components.
Presets replace the graph. Kruskal ties follow the displayed edge-record order. The selected forest minimizes total tree cost within each component. All original edges stay visible; thick blue edges are selected. Weights are cost units, not measured distances.
Planner request
Appropriate starting question
Cheapest tree connecting all sites
Minimum spanning tree
Least additive travel cost from A
Shortest paths
Largest steady throughput to D
Maximum flow
Survive any selected cable loss
Redundant connectivity, not a tree
Different objectives can favor different edges. Thick blue edges are the named selection; all original connections remain visible.
Use the existing presets to test the scope of a guarantee
In the comparison above, select Four-site network. The left panel selects AB, BC, CD and counts each construction edge once, giving total 5. The right selects AB, AC, CD with selected-edge total 7, while reporting route costs 0, 2, 3, and 5 from A. Both trees attain those route costs. When B offers another cost-3 route to C, strict relaxation keeps C's existing direct predecessor AC. Equal route costs therefore do not imply identical selected edges. Kruskal instead accepts BC first, then AB and CD, rejecting AC and BD because their endpoints are already connected.
Now select Route cost differs. This replaces the input with vertices A, B, C and undirected edges AB at 2, AC at 2, and BC at 1. Kruskal accepts BC and then AB, obtaining total 3. Its route from A to C costs 3 through B. The right panel instead retains the direct links AB and AC, obtaining route costs 0, 2, and 2 with selected-edge total 4. The direct AC route is a concrete counterexample to a universal shortest-route claim about the left panel. The extra construction unit on the right buys a different objective, not a correction to Kruskal.
A cheaper construction tree can lengthen a route
This is the actual Route cost differs preset: undirected AB = 2, AC = 2, BC = 1. Thick AB and BC minimize construction total at 3. The omitted direct AC edge supplies a cheaper A-to-C route than the selected tree does. Geometry is schematic; printed weights determine cost.
Equal-cost triangle removes another possible misunderstanding. Its only vertices are A, B, and C, and all three undirected edges AB, AC, BC have weight 1. Every two-edge selection is a minimum tree of total 2. The displayed choice AB and AC follows record order, not a theorem that those edges are uniquely best. An alternative selection AB and BC would have the same construction total but a longer A-to-C route under these weights. A deterministic display makes repeatable choices. It does not make the selected physical design uniquely justified when several optima satisfy the mathematical objective.
Disconnected pairs changes feasibility rather than merely changing the best price. The vertices remain A, B, C, D, but the only edges are AB at 2 and CD at 1. The left panel returns a forest costing 3 with two components. That total purchases both available links; it does not purchase a network connecting all four sites. The right panel reaches B from A at cost 2 and leaves C and D unreachable. Infinity records that absence of a route, not a very high estimated price. Any recommendation to connect the components requires a new available edge, which this preset does not provide.
For a separate paper sensitivity check, keep the three-vertex graph AB, AC, BC, fix AB at 2 and BC at 1, and let AC cost 1, 2, or 3. No control here edits individual weights. At AC cost 1, the cheapest tree is AC plus BC, totaling 2. At cost 2, both AC plus BC and AB plus BC total 3. At cost 3, AB plus BC wins at 3. The chosen edge set can change while the optimum value changes little or not at all. Report both quantities when explaining whether a recommendation is sensitive to uncertain input.
One price change alters which tree is cheapest
AC price
AB + BC total
AC + BC total
Minimum selection
1
3
2
AC + BC, total 2
2
3
3
Either, total 3
3
3
4
AB + BC, total 3
Paper scenarios only, not new controls. Vertices are A, B, C; the only undirected edges are AB at 2, BC at 1, and AC at the listed price. The third possible tree AB + AC costs 3, 4, or 5 respectively, so it does not beat the displayed winners.
Changing an edge's availability is different from changing its cost. In the same paper triangle, deleting AC leaves AB and BC as the only spanning tree regardless of how cheap AC used to be. Deleting BC instead forces AB and AC, at a total determined by their two costs. A price estimate cannot represent a prohibited link unless the model explicitly treats it as unavailable. This matters when a road closes or an eligibility condition fails. A selected edge disappearing can invalidate the old answer immediately. Recomputing on a changed graph answers a new conditional question; it does not repair the evidence for the old one.
Sensitivity is not a probability forecast
Compare altered edge sets and weights to see which assumptions change the decision. Removing a bridge or changing eligibility can change feasibility, not just the objective value. Equal optima may switch under a tiny cost change, so a different selected edge set does not necessarily signal a large change in total value.
Scenario comparisons show conditional consequences. They do not estimate failure probabilities, forecast demand, validate recorded travel times, or settle ethical priorities. Report both the graph result and the omitted evidence needed for action. A useful conclusion can be that the model must change before the requested recommendation is justified.
Distinguish a mathematical bound from an observed service rate
Consider a separate directed parcel network with vertices A, B, C, D, source A and sink D. Its complete capacity list is A-to-B at 3, A-to-C at 2, B-to-C at 1, B-to-D at 2, and C-to-D at 3 items per hour. An allocation of 3, 2, 1, 2, and 3 on those edges respects every capacity. B receives 3 and sends 1 plus 2. C receives 2 plus 1 and sends 3. The source sends 5 and the sink receives 5. This feasible allocation is a lower bound on maximum throughput because it demonstrates that 5 is possible within the model.
The cut separating A from B, C, and D gives an upper bound of 3 plus 2, or 5 items per hour. Every item reaching D must leave A across one of these two original directed edges. Since the feasible allocation attains the bound, the model optimum is exactly 5. If actual parcels arrive at only 3 per hour, a measurement of output at 3 does not refute that proof. Capacity is an upper limit, not a promise of sufficient demand. To investigate the discrepancy, compare observed arrivals and sustainable link rates with the assumptions used in the certificate.
An allocation attains the source cut's bound
Arrowheads show the only permitted directions. Every label is flow/capacity in items per hour. Original edges are A→B, A→C, B→C, B→D, C→D. The cut {A} | {B, C, D} has outgoing capacity 3 + 2 = 5, equal to this feasible flow. Positions are schematic. This is a steady allocation, not a timing simulation.
A missing shared resource can also explain the discrepancy. Suppose the two departures from A use one handling desk that can process only 3 items per hour in total. The original graph permits 3 on A-to-B and 2 on A-to-C simultaneously, but the desk does not. This is a shared constraint, not either edge's existing individual capacity. Encoding a shared handling stage with its own capacity would change the model and its bound. The old equal-cut certificate remains correct for the old graph while failing to answer the revised operational question. Mathematical validity and adequacy of the chosen representation are separate judgments.
Assignment recommendations have the same separation. Take workers A, B, C, jobs D, E, F, and exactly the eligibility edges AD, BD, CE, CF. At most one of A and B can receive their only eligible job D. C can receive E or F, so two assignments are attainable and three are impossible. The subset of workers A and B has only one distinct neighboring job, which certifies the shortage. One unused job does not contradict that certificate. Its identity matters: extra availability at E or F cannot help A or B unless their eligibility edges also change.
Suppose the recorded eligibility of B for D is uncertain because a required qualification has not been verified. A two-pair recommendation using BD depends on that uncertain fact. Another maximum selection AD plus CE would avoid it, yet the cardinality objective alone does not express a preference for verified records. Conversely, confirming a new edge BE would allow AD, BE, CF and cover all three workers. These are conditional consequences of precise edge changes. They are not estimates of qualification probability, fairness, or likely job performance. Evidence about the people must determine whether each proposed change belongs in the graph.
Two workers compete for one eligible job
Workers A, B, C and jobs D, E, F have exactly eligibility edges AD, BD, CE, CF. Thick AD and CE give a matching of size two. The outlined worker subset {A, B} has only neighbor D, so covering all three workers is impossible despite the unused job F. Edges are undirected eligibility relations, not preferences. Positions are schematic.
A defensible final recommendation therefore includes the computed result and the condition under which someone can act on it. For the parcel example, report a model maximum of 5 items per hour, its feasible allocation and equal cut, and the unresolved shared-desk constraint. For the worker example, report the shortage at D and request eligibility evidence relevant to A or B rather than more unrelated jobs. For the cable example, state whether the requirement is a cheapest tree or survival of a link outage. These conclusions identify which observations or requirements could change the decision without pretending that calculation supplies those missing facts.
Exercises
Reject a combined guarantee
A consultant returns the cost-5 tree A-B, B-C, C-D in the displayed construction graph and says it is also outage-safe and fastest from A. Which parts are established?
Hint
Check a tree edge failure and compare A-to-C routes.
Worked answer
Claim
Evidence
Minimum tree cost
Selected weights 2 + 1 + 2 = 5
Single-edge resilience
Refuted by removal of B-C
Fastest travel
Travel-time weights not supplied
Check units before comparing route metrics. Thick blue edges are the named selection; all original connections remain visible.
The tree is a minimum-cost spanning tree for the stated weights. It is not outage-safe: removing B-C disconnects it. Under the same additive construction weights, this particular tree also happens to preserve the minimum route costs from A: 2 to B, 3 to C, and 5 to D. That coincidence is not a general MST guarantee. It does not prove fastest travel, because construction weights are not travel times unless explicitly defined that way.
Request missing evidence
A maximum flow of 5 items/hour is proven for a parcel network. Actual delivery is 3 items/hour. Name model omissions that could explain the difference without disproving the theorem.
Hint
The theorem concerns capacities and conservation in the supplied graph.
Worked answer
Model premise
Evidence to request
Capacities
Observed sustainable rates and shared resources
One commodity and destination
Actual parcel routing requirements
Steady operation
Scheduling, storage, delays, and demand
A discrepancy can challenge the model rather than the mathematical result.
The assumed link capacities may be inaccurate or time-varying; parcels may need incompatible destinations; handling delays, storage limits, vehicle schedules, and demand shortages may matter. The feasible flow and cut certify 5 for the stated single-source/sink steady model. They do not prove a measured service can attain it.
Sources and further reading
Selected reference passages support the definitions and algorithms below. The networks, explanations, and implementations are original. Terminology and assumptions are stated within each lesson; source review is not an independent audit of this course. Optional links are not runtime dependencies.
Brief overview and links to implementations. This page is explicitly incomplete; substantive residual and certificate details were checked in the linked implementation.
Matching, maximum cardinality, perfect matching, alternating paths, and the flow reduction. Our small visualizer uses exhaustive subset search instead.