Find the certificate. Write the proof.

Graphs and Their Models — From raw data to a graph, and the first counts proved by bijection

Six exams and four students' course lists become a conflict graph. Learn what a graph is, the families that recur (paths, cycles, complete and complete bipartite graphs), count their edges by bijections, prove the complement edge count, and tell subgraphs from induced subgraphs. Then build models in code, give evidence either way, and assemble, repair and write proofs yourself.

You build: A conflict graph built from course lists, a check that tells a subgraph from an induced one, and a tournament schedule with a proof

• graph models
• complete and bipartite graphs
• induced subgraphs
• proof writing

Degrees, Representations, and Isomorphism — When two drawings are the same graph, and short certificates either way

Two sketches of one network: are they the same graph? Store graphs as adjacency lists and matrices, define isomorphism with both directions, prove that degree sequences and cycle counts are invariants and that color refinement colors are too, and prove the basic facts about the n-cube and the Petersen graph. Then search for isomorphisms, certify differences, and assemble, repair and write proofs yourself.

You build: A search that finds a renaming or shows none exists, a certificate that tells two graphs apart, and a relabeling of the cube with a proof

• isomorphism
• invariants
• color refinement
• the n-cube and the Petersen graph

Connectivity and Bipartite Graphs — Two shifts or an odd cycle: one search finds whichever certificate exists

Five volunteers cannot be split into two shifts without a clash, and a triangle proves it. Turn walks into paths, use a longest path to force long cycles, prove that odd closed walks contain odd cycles, and prove König's theorem that a graph is bipartite exactly when it has no odd cycle, as a search that returns a two-coloring or an odd cycle. Then assemble, repair and write proofs yourself.

You build: A two-coloring search that returns an odd cycle when it must, a long-cycle finder, and a two-room split with a proof

• walks and paths
• bipartite graphs
• odd cycles
• proof writing

Eulerian Circuits — Euler's theorem, Hierholzer's algorithm, Königsberg resolved, and Mantel's bound

Degree Sequences and Havel–Hakimi — Which sequences are graphic, and how to build the graph

Digraphs, Tournaments, and de Bruijn Sequences — Directed walks, strong connectivity, Eulerian digraphs, kings

Trees and Their Characterizations — Leaves, the four equivalent definitions, distance, and Jordan's center theorem

Counting Trees: Prüfer Codes and Cayley's Formula — A bijection that counts n^(n−2) labeled trees, and Kirchhoff's determinant

Minimum Spanning Trees — Kruskal, Prim, and the cut property that proves them both

Matchings and Augmenting Paths — Maximal versus maximum, path repairs, and a full proof of Berge's theorem

A pairing can be stuck, with no edge left to add, and still not be the largest. Repair it along an alternating path, prove what the symmetric difference of two matchings looks like, prove Berge's theorem including its endpoint argument, and justify a complete alternating search in bipartite graphs. Then assemble, repair and write proofs yourself.

You build: An alternating search that repairs a stuck pairing, a symmetric-difference certificate, and an instrument repair with a proof

• matchings
• augmenting paths
• Berge's theorem
• proof writing

Hall's Theorem and König–Egerváry — When every applicant can be placed, and the short evidence that proves it either way

Five applicants cannot all be placed, and a short certificate proves it: a set of applicants who between them qualify for too few jobs. Prove Hall's theorem by turning a stuck search into that certificate, prove König–Egerváry by reading a minimum cover off the same search, then assemble, repair and write proofs yourself.

You build: An alternating search, a König cover, and a proof that no roster is forced

• Hall's theorem
• vertex covers
• certificates
• proof writing

Stable Matchings and Gale–Shapley — Preferences, blocking pairs, and the proposal algorithm

Tutte's Theorem and Factors — Why some graphs cannot be perfectly matched, the short evidence that proves it, and how to build a 2-factor

Twenty-two devices, each compatible with exactly three others, cannot all be paired off, and one deleted vertex proves it: three odd pieces are left, and one vertex cannot rescue all three. You will prove that such evidence always rules out a perfect matching, follow a marked sketch of why its absence guarantees one (Tutte's theorem), and use the Berge–Tutte formula to say exactly how far from perfect a graph is. Then you will prove that every 2k-regular graph has a 2-factor and build one in code from closed trails. In the lab you search for the evidence, assemble a proof from its steps, find the false step in another, and write one for a problem that does not say what it is.

You build: A 2-factor built from closed trails, a search for the set whose removal rules out a perfect matching, and an audit with a proof

• Tutte's theorem
• odd components
• Berge–Tutte formula
• 2-factors

Connectivity and Edge-Connectivity — How many routers or cables must fail, and why κ ≤ κ′ ≤ δ

Every router has three cables, yet one router or two cables split the network. Define connectivity and edge-connectivity with their conventions, prove that every disconnecting set contains an edge cut, prove Whitney's inequality by charging a vertex cut to an edge cut, and see each inequality fail to be tight. Then assemble, repair and write proofs yourself.

You build: Whitney's construction in code, a weakest-link search, and a proof that a growing network cannot be cut cheaply

• connectivity
• edge cuts
• Whitney's inequality
• proof writing

2-Connected Graphs and Ear Decompositions — Two routes between any two routers, and a recipe that builds every robust network

No single router failure splits the prism, but why? Prove Whitney's theorem that a graph is 2-connected exactly when every two vertices have two routes sharing no stop, prove the expansion lemma, and prove that 2-connected graphs are exactly the graphs built from a cycle by adding open ears. Then grow ear decompositions in code, find routes where the obvious first choice fails, and assemble, repair and write proofs.

You build: An ear decomposition in code, two disjoint routes past a trap, and a proof that an inspector's loop always exists

• 2-connected graphs
• Whitney's theorem
• ear decompositions
• proof writing

Menger's Theorem — The fewest vertices that separate two vertices equals the most paths that avoid each other

How many routes between two routers share no router in between? A cut of the same size proves no more exist. Prove Menger's theorem by induction, with König–Egerváry as the base case, prove that k-connected means k disjoint paths between every pair, then grow disjoint routes by rerouting and read off the matching cut. Then assemble, repair and write proofs yourself.

You build: A rerouting search that returns the most disjoint routes and a cut of the same size, and a capacity version with a proof

• Menger's theorem
• disjoint paths
• cuts
• proof writing

Network Flows and Max-Flow Min-Cut — Feasible flows, residual networks, Ford–Fulkerson, and the theorem that pays for everything

Planar Graphs and Euler's Formula — Embeddings, faces, duals, and the edge bound that rules out K5 and K3,3

Kuratowski, Wagner, and Outerplanar Graphs — Subdivisions, minors, and the two obstructions that characterize planarity

Vertex Coloring and Greedy Bounds — Chromatic number, greedy coloring, degeneracy, and six colors for every map

Critical Graphs, Mycielski, and Brooks' Theorem — What forces colors: minimal k-chromatic graphs, triangle-free graphs of any chromatic number, and χ ≤ Δ

Edge Coloring — Line graphs, König, Shannon, Vizing, and the Four Color Theorem as an edge-coloring statement

Hamiltonian Cycles — Hamilton's puzzle, a necessary condition, and Dirac's theorem

Turán's Theorem and the Ten Theorems — Extremal graphs, the Ershov–Kozhukhin bound, and the course in ten results