Courses / Mathematics / Combinatorics and graph theory: enumeration, structure and certificates Mathematics · unit version 1 Combinatorics and graph theory: enumeration, structure and certificates A proof-based undergraduate sequence extending discrete foundations through enumerative methods, structural graph theory, algorithms and probabilistic existence. Public practice and reviewed assessment remain distinct evidence.
Open any lesson. Completion records participation; automatic practice checks and human judgment of written arguments are separate. This unit retains its own versioned requirements.
Readiness and preparation Check your starting point Try these short questions on paper, then compare your reasoning. They are optional self-checks, not a placement score or a navigation requirement. Use a targeted review when useful and return with your browser’s Back control.
What must a counting bijection prove beyond giving a formula? Enumeration often transfers a difficult counting problem to a simpler family.
Compare reasoning and find a refresher Define a map on every object, show it lands in the target family, and construct its inverse or prove injectivity and surjectivity. A few matching examples do not establish equality of the two finite counts.
Review bijections and cardinality
Why does every finite undirected graph have an even sum of degrees? Graph identities frequently count incidences in two orders.
Compare reasoning and find a refresher Each edge has two endpoint incidences, so the sum of vertex degrees equals twice the number of edges. If loops are allowed, each loop contributes two; declare the graph convention before using the identity.
Review degrees and double counting
How does a recurrence become an equation for a generating function? Later counting methods build on coefficient shifts and initial conditions.
Compare reasoning and find a refresher Multiply the recurrence by the appropriate power of the formal variable and sum over its valid indices. Shift indices carefully and retain omitted initial terms. Formal coefficient identities do not require analytic convergence, which is a separate question.
Review generating-function shifts
Loading saved mathematics work…
Combinatorics: constructions, bounds and certificates
The mixed assessment has separate response history and review criteria; it does not change lesson participation records.
Lesson sequence Each linked lesson opens on its own page. Expand its details here when you want to check the objectives before choosing.
Lesson details and objectives Construct reversible counting correspondences.
Construct reversible counting correspondences. Count incidence pairs in two orders. Diagnose overcounting by explicit fibers. 8 practice tasks.
Lesson details and objectives Translate allocation restrictions into shifted variables.
Translate allocation restrictions into shifted variables. Derive upper-bound inclusion–exclusion. Check zero and infeasible cases. 8 practice tasks.
Lesson details and objectives Derive the inversion insertion recurrence.
Derive the inversion insertion recurrence. Interpret q-factorial coefficients. Prove symmetry by permutation reversal. 6 practice tasks.
Lesson details and objectives Derive the second-kind Stirling recurrence.
Derive the second-kind Stirling recurrence. Relate partitions to surjections. Distinguish labeled boxes from unlabeled blocks. 6 practice tasks.
Lesson details and objectives Use conjugation to exchange partition restrictions.
Use conjugation to exchange partition restrictions. Prove the distinct-parts odd-parts identity. Extract coefficients from finite products. 6 practice tasks.
Lesson details and objectives Count permutations with a specified cycle type.
Count permutations with a specified cycle type. Derive the first-kind Stirling recurrence. Connect insertion to a rising-factorial polynomial. 6 practice tasks.
Lesson details and objectives Derive derangement counts by forbidden fixed points.
Derive derangement counts by forbidden fixed points. Use rook numbers for position restrictions. Explain why incompatible forbidden placements contribute zero. 6 practice tasks.
Lesson details and objectives Translate initial conditions into a rational generating function.
Translate initial conditions into a rational generating function. Extract coefficients using factorization. Separate formal identities from analytic convergence. 6 practice tasks.
Lesson details and objectives Derive the binomial convolution product rule.
Derive the binomial convolution product rule. Solve a labeled recurrence with an EGF. Explain factorial normalization. 6 practice tasks.
Lesson details and objectives Derive the set-of-components exponential formula.
Derive the set-of-components exponential formula. Count set partitions and restricted permutation cycles. Track component multiplicities without ordering them. 6 practice tasks.
Lesson details and objectives Prove a reflection bijection for bad paths.
Prove a reflection bijection for bad paths. Derive the Catalan recurrence. Connect balanced paths and rooted binary shapes. 6 practice tasks.
Lesson details and objectives Construct the incidence Möbius function recursively.
Construct the incidence Möbius function recursively. Prove finite-poset inversion. Recover subset inclusion–exclusion as a special case. 6 practice tasks.
Lesson details and objectives Prove the LYM inequality by chain counting.
Prove the LYM inequality by chain counting. Deduce Sperner’s bound. Derive Dilworth’s theorem through bipartite matching. 6 practice tasks.
Lesson details and objectives Prove Burnside’s lemma by double counting.
Prove Burnside’s lemma by double counting. Compute fixed colorings from permutation cycles. Distinguish rotations from reflections. 6 practice tasks.
Lesson details and objectives Prove the Havel–Hakimi reduction by switches.
Prove the Havel–Hakimi reduction by switches. Construct a graph from a valid sequence. Use degree constraints as impossibility certificates. 6 practice tasks.
Lesson details and objectives Construct and decode Prüfer sequences.
Construct and decode Prüfer sequences. Prove Cayley’s formula. Count trees with prescribed degrees. 6 practice tasks.
Lesson details and objectives Relate oriented incidence matrices to Laplacians.
Relate oriented incidence matrices to Laplacians. Prove the cofactor formula using Cauchy–Binet. Evaluate a small spanning-tree count. 6 practice tasks.
Lesson details and objectives Prove the safe-edge exchange argument.
Prove the safe-edge exchange argument. Verify the graphic matroid exchange axiom. Explain why greedy optimization needs an exchange structure. 6 practice tasks.
Lesson details and objectives Derive basis size and the extension lemma from finite independence axioms.
Distinguish maximal, maximum-cardinality and maximum-weight choices. Prove common basis size and correctly quantified exchange. Extend an independent prefix without deleting its elements. 6 practice tasks.
Lesson details and objectives Prove optimality with a preserved-prefix invariant and audit signed objectives.
Prove the optimal-basis extension invariant, including rejection persistence. Separate the basis objective from arbitrary-size weight optimization. Use non-graphic examples and structural witnesses to diagnose greedy failure. 6 practice tasks.
Lesson details and objectives Prove the Euler tour construction.
Prove the Euler tour construction. Derive Dirac’s sufficient condition. Use obstructions without treating sufficient conditions as necessary. 6 practice tasks.
Lesson details and objectives Prove flow value is bounded by every cut.
Prove flow value is bounded by every cut. Derive residual augmentation and max-flow/min-cut. State integral-capacity termination and complexity limits. 6 practice tasks.
Lesson details and objectives Reduce vertex-disjoint paths to split-vertex flow.
Reduce vertex-disjoint paths to split-vertex flow. Prove the nonadjacent vertex version of Menger. Distinguish vertex and edge connectivity. 6 practice tasks.
Lesson details and objectives Prove Hall’s theorem with alternating reachability.
Prove Hall’s theorem with alternating reachability. Construct a deficient neighbor-set certificate. Apply matching to representatives and assignments. 6 practice tasks.
Lesson details and objectives Prove Kőnig’s equality using alternating paths.
Prove Kőnig’s equality using alternating paths. Extract a minimum cover from a maximum matching. Bound augmenting-path algorithm work. 6 practice tasks.
Lesson details and objectives Prove the odd-component necessity in Tutte’s criterion.
Prove the odd-component necessity in Tutte’s criterion. Analyze an odd blossom and an augmenting path. Distinguish a theorem dependency from a checked certificate. 8 practice tasks.
Lesson details and objectives Prove greedy and degeneracy coloring bounds.
Prove greedy and degeneracy coloring bounds. Use critical subgraph degree constraints. State the exceptions and proof boundary of Brooks’ theorem. 6 practice tasks.
Lesson details and objectives Prove deletion–contraction.
Prove deletion–contraction. Compute chromatic polynomials of small graphs. Read degree and edge count from coefficients. 6 practice tasks.
Lesson details and objectives Prove Euler’s formula by deleting cycle edges.
Prove Euler’s formula by deleting cycle edges. Derive simple and bipartite planar edge bounds. Distinguish necessary bounds from complete planarity criteria. 6 practice tasks.
Lesson details and objectives Prove the five-color theorem with Kempe chains.
Prove the five-color theorem with Kempe chains. Relate bridges and cycles to dual edges. State the dependence on a fixed plane embedding. 6 practice tasks.
Lesson details and objectives Prove Mantel’s bound.
Prove Mantel’s bound. Derive Turán’s structure by symmetrization. Construct balanced multipartite extremizers. 6 practice tasks.
Lesson details and objectives Prove a finite Ramsey recurrence.
Prove a finite Ramsey recurrence. Establish the six-vertex triangle theorem. Separate upper bounds from exact Ramsey values. 6 practice tasks.
Lesson details and objectives Use indicator expectations without independence.
Use indicator expectations without independence. Derive a random-cut guarantee. Apply deletion to turn an expected count into an existence bound. 8 practice tasks.
Lesson details and objectives Compute subgraph expectations with explicit dependence.
Compute subgraph expectations with explicit dependence. Use variance and the second-moment method. Compare threshold-scale evidence with proved probability bounds. 6 practice tasks.
Learn