Every proof technique used in the collapsed proofs of these notes (116 notes with proofs), with the notes that apply it; generated by scanning the [!proof] callouts. How to find a proof: Proof Techniques.
Induction
Observation Toolkit · Greedy Constructions · Heaps · Range Order Statistics and Wavelets · DP Foundations · LIS, LCS and Edit Distance · Interval DP · Tree DP and Rerooting · DAG and Expected-Value DP · Counting DP Techniques · Matrix Exponentiation DP · Knuth-Yao Optimization · Graph Basics and Modeling · BFS, DFS and Grids · Shortest Paths · Shortest Path Techniques · Matrix-Tree Theorem · Hamiltonian Paths and TSP · Special Graph Classes · Global Minimum Cut · Min-Cost Flow · Matroid Intersection · Stable Matching · Tree Isomorphism and Prüfer Codes · Lowest Common Ancestor · Small to Large (DSU on Tree) · Kruskal Reconstruction Tree · Modular Arithmetic · Probability and Expectation · GCD and Extended Euclid · Linear Congruences and CRT · Continued Fractions and Pell Equations · Prisoners and Hats
Exchange argument
Operations and Reachable States · Shortest Path Techniques · Dynamic Connectivity · Minimum Spanning Trees · Special Graph Classes · Matroid Intersection · Stable Matching · Probability and Expectation · Backtracking and Pruning
Contradiction / minimal counterexample
Knapsack and Subset Sum · Divide and Conquer Optimization · BFS, DFS and Grids · Shortest Paths · SCC and 2-SAT · Minimum Spanning Trees · General Matching · Matroid Intersection · Stable Matching · Lowest Common Ancestor · Heavy-Light and Long-Path Decomposition · Continued Fractions and Pell Equations
Invariant
Parity, Coloring and Mod Observations · Operations and Reachable States · Invariant-Based Constructions · Range Order Statistics and Wavelets · Mo’s Algorithm · Offline and 2D Range Queries · Permutation Tree · LIS, LCS and Edit Distance · Broken Profile DP · Monotone Queue, 1D1D and SMAWK · BFS, DFS and Grids · Shortest Paths · SCC and 2-SAT · Bridges and Biconnectivity · Dynamic Connectivity · Push-Relabel · Min-Cost Flow · Weighted General Matching · Matroid Intersection · Lowest Common Ancestor · Small to Large (DSU on Tree) · Link-Cut Tree · Quadratic Residues and Modular Roots
Monovariant / potential function
Push-Relabel · Min-Cost Flow · Matroid Intersection · Stable Matching · Link-Cut Tree · Top Trees · Modular Arithmetic · Probability and Expectation
Double counting
Bitset and Word-Level Parallelism · Sqrt Decomposition · Special Graph Classes · Euler Tour, Subtree and Path Queries
Bijection
Grid and Matrix Constructions · Classic DP Problems · Minimum Spanning Trees · Euler Tours · Tree Isomorphism and Prüfer Codes · Probability and Expectation
Linearity of expectation
Amortized analysis
Heaps · Link-Cut Tree · Top Trees · Modular Arithmetic
Optimal substructure
Adversary / information bound
Broken Profile DP · Primality Testing and Factorization · Prisoners and Hats
Colouring argument
Parity, Coloring and Mod Observations · Interval DP · Bipartite Graphs · Special Graph Classes · Graph Coloring · Small to Large (DSU on Tree) · Prisoners and Hats
Parity argument
Parity, Coloring and Mod Observations · Interval DP · Counting DP Techniques · BFS, DFS and Grids · Bipartite Graphs
Telescoping
Knuth-Yao Optimization · Shortest Paths · K Shortest and Disjoint Paths · Link-Cut Tree · Top Trees · Modular Arithmetic
Linear algebra (rank, determinant)
Grid and Matrix Constructions · Range Order Statistics and Wavelets · Counting DP Techniques · Matrix-Tree Theorem · Special Graph Classes · General Matching · Matroid Intersection · Stable Matching · Probability and Expectation · Continued Fractions and Pell Equations · Inclusion-Exclusion and Derangements
Matroids
Minimum Spanning Trees · Matroid Intersection
Convexity
Aliens Trick · Slope Trick · Min-Cost Flow · Assignment Problem · Tree Basics, Diameter and Center · Complexity, Constraints and Amortized Analysis
Flow duality (max-flow min-cut)
Maximum Flow · Flow Modeling · Minimum Cut · Weighted General Matching
Probabilistic method / Schwartz–Zippel
General Matching · Tree Isomorphism and Prüfer Codes
Exhaustive or brute-force verification
Observation Toolkit · When the Answer Is Small · Sorting and Ordering Observations · Parity, Coloring and Mod Observations · Operations and Reachable States · Ad Hoc on Arrays and Strings · Permutation Constructions · Graph Constructions · Greedy Constructions · Bitset and Word-Level Parallelism · Broken Profile DP · Primality Testing and Factorization · Backtracking and Pruning · Josephus Problem · Egg Dropping · Lights Out · Knight’s Tour and N Queens · Fast I/O and Constant Factor