An unused station does not always mean a project can take it

Make the rules visible

NIST’s historical account of graph theory describes a matching as a set of connections in which no two meet at the same node. The following original classroom puzzle applies that idea to two paper lists.

Its projects, stations and permissions are fictional, not records of students or available facilities.

Place four project cards labeled A, B, C and D on the left, and four station cards numbered 1 through 4 on the right. Each project may take at most one station, and each station may serve at most one project in this single round.

An allowed connection is simply a rule printed on our worksheet. We supply no equipment, ages, skills, supervision requirements or schedules.

The puzzle asks only how many nonconflicting pairs these exact paper rules permit, not how to allocate an actual classroom.

Write every allowed connection

Give A the options 1 or 2. Give B only option 1.

Give C the options 2 or 3, and D the options 3 or 4. There are seven allowed connections altogether: two for A, one for B, two for C and two for D.

Four projects and four stations do not mean sixteen permissions. Crossing every card with every station would add nine connections that our model never authorized.

Keep the seven-connection list beside any drawing so the drawing can be checked.

Try a first-available pass in project order. A takes 1.

B cannot take its only option, because 1 is occupied, so leave B unpaired. C takes 2, and D takes 3.

The result has three pairs: A–1, C–2 and D–3. Station 4 is unused.

B cannot simply take it, because B–4 is not on the allowed list. Calling that empty card spare capacity does not create a permission.

Nor does the failed first pass establish that four pairs are impossible.

Revisit a chain of earlier choices

Start with the unpaired B and follow its only option to station 1. That station belongs to A, but A has another option at 2.

Station 2 belongs to C, which has another option at 3. Station 3 belongs to D, which can instead use empty station 4.

We have found a chain ending in a free place. It names specific allowed alternatives; it does not require pretending that any project can use any station.

Rearrange from the free end: move D from 3 to 4, move C from 2 to 3, then move A from 1 to 2. Finally assign B to 1.

The four pairs are A–2, B–1, C–3 and D–4. Every pair appears in the original seven-connection list, every project appears once and every station appears once.

Nothing was purchased or added. The improvement came from revising earlier choices.

Four is the largest possible total in this model because there are only four projects and each may appear in at most one pair.

Check the result without trusting the drawing

An independent paper check starts with B. Its only option forces B–1 if all four projects are to be paired.

Then A cannot use 1, so A must take 2. C cannot use 2, so C must take 3.

Finally D must take 4. That sequence proves our four-pair arrangement is the only arrangement covering every project under these rules.

It does not say that every partial arrangement is wrong; the initial three pairs were permitted, just not the largest achievable result.

A tiny exhaustive checker can test the same claim by considering each project’s allowed stations plus an unpaired option. It rejects a candidate whenever two projects reuse a station, then counts the remaining pairs.

For this four-card example that is a manageable verification method, not a performance claim about large scheduling systems. Keep its allowed-list input and its output together.

A program that quietly adds B–4 would solve a different problem even if it displayed four pairs with a confident check mark.

Change one permission and find the bottleneck

Make a second version of the puzzle by removing A–2. A and B now both have only station 1, while C still has 2 or 3 and D still has 3 or 4.

All four station cards remain present, and each project still has at least one option. Nevertheless, A and B together can contribute at most one pair because they share the same sole station.

C and D can contribute at most two more. The total therefore cannot exceed three.

Three is attainable: pair A with 1, C with 2 and D with 3, leaving B unpaired. Another valid three-pair choice uses B instead of A at 1.

The arithmetic does not prefer one project’s interests; it only identifies the shared restriction. Adding an unconnected fifth station would not remove that restriction.

Its card has no allowed connection to A or B. To restore four pairs, a rule would have to change, not merely the count of empty station cards.

Keep feasibility separate from preference

For a third version, retain A’s single option 1 but add B–2. Now A–1, B–2, C–3 and D–4 is permitted, and four projects fit again.

Record which permission changed so the successful result is not attributed to the previous version. This is a fictional rule change for checking the model.

It is not advice to relax a real safety condition, access requirement or student accommodation merely to make a chart look complete.

The worksheet’s goal was the number of valid pairs. It assigned no preference scores, waiting priorities, costs or measures of fairness, so it cannot select a fairest real outcome.

Preserve the allowed connections, one-pair limits and version beside the answer. When a first pass leaves someone out, ask whether a specific permitted rearrangement helps; when a bottleneck remains, identify it rather than blaming the unmatched card.

The useful lesson is a reproducible explanation of the constraint, not an invented promise that every allocation problem has a full solution.