Edge-cover vertices
Choose as few vertices as possible while covering every listed edge.
Adult planning suggestion: about 9–12 · Logic & rule checking
- Players
- 3 per group
- Time
- 20–30 minutes
- Materials
- Printed record sheet, pencil and paper markers
Prepare
Use vertices A,B,C,D,E and edges AB,BC,CD,DA,AE,CE. Draw edges as listed even if the sketch looks different; crossing lines do not create extra vertices. Each trio receives five paper vertex markers.
Follow the rule
Select a subset of vertices. An edge is covered when at least one of its endpoints is selected; both endpoints may be selected. Mark each edge as covered or uncovered on the independent edge ledger.
Check each step
Try a two-vertex solution before a larger set. One pupil proposes, a second audits all six edges and a third seeks a lower bound. Having every vertex next to something selected is a different task and does not certify this one.
Worked example
A,C covers all six edges. A single vertex cannot cover both AB and CD because those edges have no common endpoint. Therefore at least two are needed, and the found two-set is minimum for this graph.
Finish and adapt
Finish with the subset, the six-edge audit and the lower-bound explanation. The small graph proves only this instance, not a fast method for every graph. Adults may pre-draw edges or read labels; do not substitute a matching for the selected vertices.
Purpose, observation and provenance
Within this activity: Choose as few vertices as possible while covering every listed edge.
Observe whether every edge is audited and a minimum claim includes a valid lower bound.
Our rules, examples and printable diagrams are separately prepared. The earliest inventor of the broader mechanism is not established here.
Cornell: vertex-cover definition — Technical background, not an evaluated primary-school lesson. This paper exercise and examples are our adaptation; age and support are adult planning suggestions.
Secondary practice: Cooperation and explaining a check.
For a class of 30, use ten groups of three. Prepare one player-material set per group and keep the host key with the adult. Rotate operator, recorder and checker after each worked example; a reader or scribe may help without choosing answers. Avoid public ranking or diagnostic labels.
Age bands are planning suggestions. Background references may address older learners and do not validate suitability for this age band. Goals describe observable actions, not measured long-term gains or institutional endorsement.
Free alternative: Copy the supplied grids, labels and cards onto reused paper. No specialist product is needed. Adults may prepare pieces or act as a scribe.
Printable materials
Preview at 100% scale, with browser headers and footers off. Cut with suitable help. Keep host keys separate. This is a manual tabletop kit, not an online opponent, automatic judge or solver.
Edge-cover vertices · Player sheet
Before you begin
- Use vertices A,B,C,D,E and edges AB,BC,CD,DA,AE,CE. Draw edges as listed even if the sketch looks different; crossing lines do not create extra vertices. Each trio receives five paper vertex markers.
- Select a subset of vertices. An edge is covered when at least one of its endpoints is selected; both endpoints may be selected. Mark each edge as covered or uncovered on the independent edge ledger.
- Try a two-vertex solution before a larger set. One pupil proposes, a second audits all six edges and a third seeks a lower bound. Having every vertex next to something selected is a different task and does not certify this one.
| Edge | Selected endpoint(s) |
|---|---|
| AB | |
| BC | |
| CD | |
| DA | |
| AE | |
| CE |
| Selected set | Lower bound reason |
|---|---|
| ________ | ________ |
| ________ | ________ |
Edge-cover vertices · Host key — keep separate
Minimum 2, attained by{A,C}; disjoint edges AB and CD certify a lower bound 2.
What to observe
Observe whether every edge is audited and a minimum claim includes a valid lower bound.
Use the three-person roles described in the rules; offer reading or writing support without selecting answers.
Read the rules as well as this example. Other valid solutions may exist for the puzzle boards. This key is not a claim of uniqueness or measured learning gains.
| Constraint / action | Evidence / correction |
|---|---|
| ________ | ________ |
| ________ | ________ |
| ________ | ________ |
| ________ | ________ |