# Discrete structures: count only assignments that can coexist — Study worksheet

[Study guides](https://unireadinglist.com/guides/discrete-structures/)

[Course topic: Discrete Mathematics](https://unireadinglist.com/subjects/mathematics/#course-discrete-mathematics)

Sources checked: 2026-11-04

Study route and exercise: University Reading List editorial project.

An introductory discrete-mathematics route through sets, logic, counting and bipartite matching. Levin means fourth edition; Epp fifth edition; Lovász–Pelikán–Vesztergombi the 2003 first edition. The invented allocation cases have distinct tasks and slots, unit capacity and explicit allowed pairs. They are not scheduling guarantees for a real organization.

## Choose your starting point

- [ ] I want a free inquiry route
  Choose Levin for investigations, examples and selected feedback, beginning with the fourth edition’s logic and proofs.

- [ ] I need explicit proof-writing instruction
  Choose Epp when quantified statements, relations and argument structure need careful practice.

- [ ] I want deeper problem-led reasoning
  Choose Lovász and colleagues for counting and graph puzzles after you can follow short proofs.

## Compare the three books

### Discrete Mathematics: An Open Introduction

Oscar Levin · 4 · 2025
Free logic-to-graphs introduction

Choose it when: You want to investigate a small case before formalizing it.
Use another route when: You require complete solutions to every exercise or assume older editions use the same order.
Selected reading: Fourth edition: logic and proofs, graph theory, counting, then sequences; use the matching material for the case.
Limits and trade-offs: Hints and interactive feedback support inquiry; writing a proof remains your responsibility.

#### Try before choosing

List the assignments for A,B:\{1,2\}, C:\{2,3\}, checking that slots are not reused.
Check your work: Exactly two survive. Explain why eight products of local choices are not eight legal assignments.

Your notes:

________________________________

ISBN: 9781032966168

[Official free reading](https://discrete.openmathbooks.org/dmoi4.html)

[Book record and access options](https://unireadinglist.com/subjects/mathematics/discrete-mathematics-an-open-introduction/)

### Discrete Mathematics with Applications

Susanna S. Epp · 5 · 2020
Systematic logic and relations spine

Choose it when: You need to express eligibility and distinctness before counting.
Use another route when: You want only graph puzzles without a sustained logic/proof component.
Selected reading: Chapters 1–5 for language and proof, 8 for relations, 9 for counting, 10 for graphs and trees.
Limits and trade-offs: Broader formal coverage takes time before graph applications; WebAssign is a separate product.

#### Try before choosing

Write the assignment as an injective function f from tasks to slots with (t,f(t)) allowed.
Check your work: State both eligibility and injectivity. A function alone permits two tasks to share a slot.

Your notes:

________________________________

ISBN: 9781337694193

[Book record and access options](https://unireadinglist.com/subjects/mathematics/discrete-mathematics-with-applications-epp/)

### Discrete Mathematics: Elementary and Beyond

László Lovász; József Pelikán; Katalin Vesztergombi · 2003
Problem-led counting and matchings

Choose it when: You can turn examples into short arguments and want a structural explanation.
Use another route when: You need a complete syllabus in formal logic, relations and algorithm notation.
Selected reading: Counting, graph/tree and matching topics; locate them by title in the selected first edition.
Limits and trade-offs: Compact questions reward persistence and may need a systematic companion for omitted syllabus topics.

#### Try before choosing

Find a subset of tasks with too few eligible slots in the follow-up.
Check your work: The witness \{A,B,D\} has three tasks but only two neighbors; total slot count cannot fix it.

Your notes:

________________________________

ISBN: 9780387955858

[Book record and access options](https://unireadinglist.com/subjects/mathematics/discrete-mathematics-elementary-and-beyond/)

## Check your preparation

### Can I distinguish a function from an injection?

Your notes:

________________________________

### Can I count without double counting?

Your notes:

________________________________

### What does Hall’s condition say?

Your notes:

________________________________

## A six-step study plan

- [ ] Draw the relation

Selected reading: Levin graph material; Epp relations.

What to do: Make the bipartite graph and an allowed-pair table for the three-task case.

Check your work: There are no task-to-task edges or hidden slot capacity.

Your notes:

________________________________

- [ ] Formalize validity

Selected reading: Epp mathematical language and functions.

What to do: Write a quantified condition for a valid full assignment.

Check your work: Each task is assigned, every pair is allowed, and distinct tasks use distinct slots.

Your notes:

________________________________

- [ ] Count constructively

Selected reading: Levin counting; Lovász counting.

What to do: List every legal assignment and explain the forced choice for C.

Check your work: C must use 3; A and B then exchange 1 and 2.

Your notes:

________________________________

- [ ] Check a structural criterion

Selected reading: Matching topics.

What to do: Tabulate neighbor-set sizes for all seven nonempty subsets of \{A,B,C\}.

Check your work: No subset has fewer neighbors than tasks; counting is consistent with existence.

Your notes:

________________________________

- [ ] Break and repair the model

Selected reading: Matching topics and the follow-up.

What to do: Add D and slot 4, identify an obstruction, then add the stipulated edge D→4 and recount.

Check your work: A single edge restores feasibility; adding a slot without access did not.

Your notes:

________________________________

- [ ] Separate algorithm from certificate

Selected reading: Your two solved models.

What to do: Write an existence certificate, an impossibility certificate and a counting argument.

Check your work: A found matching proves existence; a Hall witness proves impossibility; neither alone proves a claimed count.

Your notes:

________________________________

## Worked exercise: Three tasks, eight local choices, two legal assignments

Distinct tasks A,B,C must occupy distinct slots 1,2,3. Allowed slots are A:\{1,2\}, B:\{1,2\}, C:\{2,3\}. Determine all full assignments and verify feasibility using Hall’s condition.

Assumptions: Each task uses exactly one slot; each slot has capacity one. Only the listed pairs are allowed. All tasks and slots are labeled; no probability model is assumed.

Your notes:

________________________________

## Change an assumption: Extra capacity without access does not restore feasibility

Keep the original allowed pairs, add task D with allowed slots \{1,2\}, and add slot 4. Determine feasibility. Then change the eligibility relation by adding the single edge D→4; count the repaired full assignments and explain why one added edge is a minimal repair.

Your notes:

________________________________

## Before moving on

- Represent an allocation as an injective allowed-pair function.
- Give a small Hall witness and explain why total capacity misses it.
- Prove both a matching count and the minimal size of a repair.

## Answer and interpretation

### Can I distinguish a function from an injection?

A function assigns each task one slot. Injectivity additionally forbids two distinct tasks receiving the same slot.

### Can I count without double counting?

For three tasks, enumerate the six slot permutations and test eligibility, rather than multiplying independent choices.

### What does Hall’s condition say?

Every subset S of tasks must have at least |S| eligible neighboring slots. It is a condition on all subsets, not just individual tasks.

### Three tasks, eight local choices, two legal assignments

1. A and B must occupy 1 and 2 in some order. Since slots cannot be reused, C must occupy 3. The two assignments are (A,B,C)=(1,2,3) and (2,1,3).
2. For singleton task sets the neighbor counts are 2. For \{A,B\} it is 2; for \{A,C\} and \{B,C\} it is 3; for all three tasks it is 3. Thus every subset meets Hall’s condition.
3. The product 2·2·2=8 counts choices with collisions. It is not a count of injections; checking the six slot permutations gives the same two legal assignments.

Exactly two full assignments exist: (1,2,3) and (2,1,3) in task order A,B,C.

Test the result: Verify all listed pairs and distinct slots for each assignment. Exhaustion follows because A and B force C to 3, leaving exactly two permutations of 1 and 2.

### Change an assumption: Extra capacity without access does not restore feasibility

1. Before repair, S=\{A,B,D\} has neighbor set \{1,2\}. Three tasks cannot inject into two slots, so no full assignment exists even though there are four slots in total.
2. After adding D→4, A and B still occupy 1 and 2. D must therefore use 4, and C uses 3. A and B can exchange their slots.
3. The repaired assignments in order A,B,C,D are (1,2,3,4) and (2,1,3,4). Zero added edges cannot work by the obstruction; this one edge works, so one is the minimum number, though the repair need not be unique.

Before the added eligibility edge: zero full assignments. With D→4: exactly two. The minimum repair size is one edge.

Test the result: The capacity of slot 4 matters only once a task can reach it. Do not conclude that D→4 is the only possible one-edge repair; the problem asks for the stipulated repair, not uniqueness.

## Common mistakes

### Treating choices as independent

The multiplication rule needs a valid sequential count; capacities couple the choices.

### Checking only totals

Enough slots overall does not exclude a bottleneck for a subset of tasks.

### Confusing existence and counting

One matching or Hall’s theorem answers feasibility; a separate exhaustive argument establishes the number.

## Sources and edition checks

- [Author: fourth edition and reorganization](https://discrete.openmathbooks.org/dmoi4.html)
  The author confirms the fourth edition’s revised order, full free reading and CC BY-NC-SA 4.0 scope.

- [Cengage: exact fifth edition and contents](https://www.cengage.com/c/discrete-mathematics-with-applications-5e-epp/9781337694193/)
  Cengage verifies the fifth-edition logic, relations, counting and graph units, with platform products separate.

- [Springer: selected first-edition softcover](https://link.springer.com/book/10.1007/b97469)
  Springer identifies the exact 2003 softcover and the problem-led counting/graph/matching scope.

These are proposed study activities, not official course assignments or a claim that every book has been read cover to cover.

[How we curate](https://unireadinglist.com/editorial/)