Module 2: Combinatorics & Graph Theory

Primary texts: Mathematics for Computer Science and Discrete Mathematics and Its Applications
Selective support: local chunked sections from the same semester book library, used only where they sharpen a concept or add exercise volume

This guide is the primary teacher. You are not supposed to read both books front-to-back. You are supposed to become operationally strong at counting arguments, recurrence modeling, and graph structure, because later probability, algorithms, and systems work will reuse these ideas constantly.

---

Scope of This Module

This is not a vocabulary tour through "basic combinatorics" and "basic graph theory." The point is to learn how to build and justify finite models.

What it covers in depth:

• counting by decomposition, product rules, division rules, and bijections
• permutations, combinations, multinomial coefficients, and binomial identities
• inclusion-exclusion, pigeonhole arguments, and constrained distribution problems
• recurrence modeling and ordinary generating functions as counting tools
• graph modeling, degree arguments, connectivity, and matrix viewpoints
• trees, spanning trees, rooted structure, and traversal reasoning
• Euler tours, Hamilton paths, graph coloring, matching structure, and planarity

What it deliberately does not try to finish here:

• full asymptotic combinatorics
• advanced graph algorithms as an algorithms course substitute
• spectral graph theory
• probabilistic combinatorics or random graph theory
• exhaustive recurrence solving beyond the linear and generating-function toolkit needed here

The standard is proof-backed fluency. If you can compute but cannot justify why the setup is correct, you are not done.

---

Before You Start

Use the Module 1 prerequisite diagnostic, which checks proof, set, function and tracing skills. Counting formulas and tree theorems are taught here, not required on entry. Keep Counting and Graph Model Contracts beside your notebook while working through the six clusters.

What This Module Is For

Computer science repeatedly asks the same family of questions in different clothes:

• how many legal states are there?
• how many bad states must exist?
• how can a recursive process be counted or bounded?
• when does a network have enough structure to connect, route, color, or schedule?
• what graph invariant forces a conclusion?

Combinatorics gives you tools for finite counting and existence arguments. Graph theory gives you a language for dependency, connectivity, conflict, and structure. Together they form a major part of the mathematical substrate for:

• probability calculations in Module 3
• recurrence and complexity reasoning in algorithms
• data-structure invariants
• scheduling and dependency modeling
• routing, matching, and optimization intuition

You are learning to see the structure before you touch the formula.

---

Concept Map

---

How To Use This Module

Work in order. The graph cluster depends on the proof habits from Module 1 and the counting discipline from the first half of this module.

Cluster 1: Counting Models

Order	Concept	Type	Focus
1	Counting by Structure, Not by Guessing	PRIMARY	Product, sum, division, and bijection as modeling moves
2	Permutations, Combinations, and Multinomial Thinking	SUPPORTING	Ordered vs unordered choice, repetition, and block constraints
3	Binomial Coefficients, Identities, and Combinatorial Proofs	SUPPORTING	Why identities are counts of the same set in two ways

Cluster mastery check: Can you explain why the counting model is correct before doing the algebra?

Cluster 2: Constrained Counting

Order	Concept	Type	Focus
4	Inclusion-Exclusion as Overlap Accounting	PRIMARY	Counting unions without double-counting
5	Pigeonhole Principle, Collisions, and Extremal Guarantees	SUPPORTING	Existence proofs and lower-bound arguments
6	Stars and Bars, Distributions, and Integer Solutions	PRIMARY	Translating distributions into countable encodings

Cluster mastery check: Can you tell whether the problem is about overlap, forced collision, or distribution under constraints?

Cluster 3: Recurrences and Generating Functions

Order	Concept	Type	Focus
7	Recurrences Arise from Structural Decomposition	PRIMARY	Turning recursive construction into equations
8	Ordinary Generating Functions as Encoded Counting	SUPPORTING	Encoding choices in coefficients
9	Solving Linear Recurrences and Extracting Coefficients	SUPPORTING	Closed forms, coefficient extraction, and model verification

Cluster mastery check: Can you derive the recurrence or generating function from the object definition instead of memorizing a template?

Cluster 4: Graph Language and Structure

Order	Concept	Type	Focus
10	Graphs as Models of Constraint and Interaction	PRIMARY	Translating finite systems into vertices and edges
11	Degrees, Walks, Paths, Cycles, and Connectivity	SUPPORTING	Local and global graph structure
12	Graph Representations, Isomorphism, and Matrix Viewpoints	SUPPORTING	Multiple representations of the same combinatorial object

Cluster mastery check: Can you choose a graph representation that exposes the property you need to prove?

Cluster 5: Trees and Network Structure

Order	Concept	Type	Focus
13	Trees Are Minimally Connected and Maximally Acyclic	PRIMARY	Equivalent characterizations of trees
14	Rooted Trees, Traversals, and Structural Recursion	SUPPORTING	Hierarchy, recursion, and traversal order
15	Spanning Trees and Network Skeletons	SUPPORTING	Extracting minimal connectivity from larger graphs

Cluster mastery check: Can you move between tree definitions, inductive reasoning, and spanning structure without treating them as separate topics?

Cluster 6: Advanced Graph Structure

Order	Concept	Type	Focus
16	Euler Tours, Hamilton Paths, and Edge vs Vertex Constraints	PRIMARY	Why Euler questions and Hamilton questions behave differently
17	Coloring, Bipartite Graphs, and Matching Structure	PRIMARY	Conflict graphs, two-colorability, and assignment structure
18	Planarity, Euler's Formula, and Forbidden Structure	PRIMARY	Using topological bounds to rule graphs in or out

Cluster mastery check: Can you identify which invariant actually controls the problem: degree parity, path coverage, coloring conflict, matching capacity, or planar edge bounds?

Then work these practice pages:

Order	Practice path	Focus
1	Counting and Combinatorial Proof Lab	Setup selection, bijections, and identity proofs
2	Constrained Counting and Recurrence Workshop	Inclusion-exclusion, distributions, recurrences, and generating functions
3	Graph Structure and Proof Clinic	Degree arguments, trees, Euler/Hamilton, coloring, and planarity
4	Code Katas	Small implementations that reinforce counting and graph structure

Use Module Quiz after finishing the concept and practice path. Use Reference and Selective Reading and Learning Resources as targeted reinforcement, not as your default path.

---

Learning Objectives

By the end of this module you should be able to:

1. Build correct counting models using product, sum, division, bijection, and case decomposition.
2. Distinguish clearly between ordered and unordered choice, with and without repetition.
3. Use binomial and multinomial coefficients with full justification instead of pattern matching.
4. Prove counting identities combinatorially by counting the same set in two different ways.
5. Apply inclusion-exclusion, pigeonhole reasoning, and stars-and-bars to constrained finite problems.
6. Derive recurrences from recursive structure and use generating functions for selected counting problems.
7. Translate real systems into graphs with appropriate notions of adjacency, direction, capacity, or conflict.
8. Use degree arguments, path language, and connectivity to prove structural graph properties.
9. Recognize and prove equivalent tree characterizations and reason about spanning trees.
10. Separate Euler, Hamilton, coloring, matching, and planarity questions by the invariants they actually depend on.

---

Outputs and Completion

Submit P1–P20 with reasoning, four runnable labs, an independent ten-part checkpoint and the workshop planning project. Preserve first attempts, help, corrections and changed-assumption evidence. Use the assessment rubric: all ten competencies require level 2 independently; an average or completed reading quota cannot compensate for a missing skill.

Open the separate practice/assessment keys only after saving attempts. Recheck selected competencies after 7–14 days. Record external-review status honestly.

Reading Policy

• Concept pages are the main path.
• Local book chunks are selective reinforcement, not a parallel syllabus.
• Read only if stuck means try the concept page and drill first.
• Optional deep dive means useful extension, not required progression.
• Because this is an in-depth module, proof-backed written work is required even for computational questions.

---

Workload and Progression

Activity	Estimated hours
Diagnostic, lessons and bounded reading	30–42
Four guided implementation/proof labs	16–24
Independent practice and revision	24–34
Assessment, feedback and remediation	10–16
Workshop project	10–14
Total	90–130

These are planning estimates pending learner pilots. At ten hours/week, allow roughly 9–13 weeks. Prerequisite repair and optional full-book depth add time. Work cluster by cluster; count the code-kata work within labs, not twice.

Practice, Evidence and Feedback

Diagnostic · Model contracts · Runnable labs · Practice feedback · Independent checkpoint · Assessment rubric · Assessment key · Workshop project · Instructor review record

Authored candidate: independent mathematical/code review and learner pilots remain pending. This is rigorous practice material, not evidence of an elite percentile outcome.

Reference

If you need exact links into the local chunked books, use Reference and Selective Reading.

---

Rich Learning Pages

Worked Examples | Guided Labs | Case Studies | Mistake Clinic | Reading Guide | Capstone Thread