Find the certificate. Write the proof.

Graphs and Their Models — Vertices, edges, and the first families: paths, cycles, complete and bipartite graphs

Walks, Degrees, and Isomorphism — Representations of a graph, invariants, the Petersen graph and the n-cube

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, symmetric differences, and Berge's theorem

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 — Odd components, perfect matchings in general graphs, and 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 — Minimum cuts equal maximum disjoint paths — vertex, edge, and global versions

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