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

Answer these closed-book before starting the main path:

1. Why is n! not the answer to every arrangement problem?
2. What is the difference between choosing k objects and ordering k objects?
3. If two counting methods give the same total, what kind of proof opportunity does that create?
4. What does the degree of a vertex measure?
5. Why does a tree with n vertices have exactly n - 1 edges?

Diagnostic Interpretation

4-5 solid answers

• You are ready for the full path.

2-3 solid answers

• Continue, but expect extra time on the first three counting concepts and the tree cluster.

0-1 solid answers

• Review Module 1 proof habits first. This module assumes you can already write definitions, follow hypotheses, and justify claims line by line.

---

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

• a counting notebook with at least 20 fully worked problems and written setup justification
• a combinatorial proof sheet containing at least 5 double-counting or identity proofs
• one recurrence notebook with at least 6 derived recurrences and their interpretations
• one generating-function sheet translating problem statements into series and extracting coefficients
• one graph notebook with your own examples and non-examples for connectivity, trees, bipartite graphs, and planar graphs
• at least 8 short graph proofs using degree sums, contradiction, induction, or invariant arguments
• one implementation mini-project using combinations, recurrence DP, or graph analysis
• one memo explaining how Module 2 tools feed directly into probability and algorithm analysis

---

Completion Standard

You have completed Module 2 when all of these are true:

• you can explain the setup of a counting problem before computing it
• you can justify inclusion-exclusion and pigeonhole arguments in sentence form
• you can derive, not just solve, a recurrence from a combinatorial process
• you can model a real problem as a graph and state what graph property answers the question
• you can prove at least one nontrivial tree theorem and one nontrivial planar or coloring claim
• you can tell when a graph question is local-degree based, path based, parity based, or embedding based

If you can do exercises only when they look identical to textbook examples, the module is not complete.

---

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.

---

Suggested Weekly Flow

Day	Work
1	Concepts 1-3 and two combinatorial proof attempts
2	Concepts 4-6 and one distribution or inclusion-exclusion sheet
3	Concepts 7-9 and one recurrence plus one generating-function drill
4	Concepts 10-12 and one graph-model translation exercise
5	Concepts 13-15 and one tree proof plus one spanning-tree analysis
6	Concepts 16-18 and one coloring or planarity argument
7	Practice pages, quiz, and notebook cleanup

---

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