Problem-solving recipes

A step-by-step procedure for every problem type this course teaches — what to do first, what to do next, and how to tell which case you're in.

What are you being asked to do?

Start with what you're actually being asked to produce.

Readiness review — check a degree list, or test bipartiteness by two-coloring, before either gets reused formally later in the course.

A basic structural fact about a graph — a degree sequence, whether one graph is a subgraph of another, whether two graphs are isomorphic, or whether a closed sequence of vertices is a walk, circuit, or cycle — the matching foundations recipe.

A distance fact — the distance between two vertices, a vertex's eccentricity, the graph's diameter and radius, or its center — in that dependency order, each building on the one before it.

A rooted tree — find a node's height.

A Hamiltonian path or cycle — search for one directly.

Whether a graph is bipartite, as a formal course topic (not readiness review) — the 2-colorability recipe.

A weighted graph — compute a specific path's total weight, or audit a Dijkstra run when negative weights are suspected of corrupting it.

A planar graph — solve Euler's formula for a missing vertex, edge, or face count.

A digraph, need its strongly connected components — the SCC recipe.

A flow network — build the residual graph and find an augmenting path, then compute a cut's capacity to prove a flow is already maximum (the second recipe extends the first).

A matching — prove one is maximum with a vertex cover, check Hall's condition and find the deficiency, or model a transportation problem as a flow network — three different questions about matchings, each with its own recipe.

A k-regular graph — test whether one can even exist before trying to build it.

Readiness

Check a degree list and find the edge count

Use when: you're given a list of vertex degrees, with no picture of the graph, and asked whether it's valid, how many edges it has, or both

Goal: either a confirmed impossible list, or a valid one paired with its exact edge count

Review: graphs, degree, and the handshaking theorem

Test whether a graph is bipartite

Use when: you're given a graph, drawn or listed by edges, and asked whether it splits into two sides with every edge crossing between them

Goal: a definite classification, backed by either a working two-coloring or the odd cycle that blocks one

Review: bipartite graphs and matchings

Foundations of graphs

Compute a degree sequence from an edge list

Use when: you're given a graph's edge list, possibly with a self-loop, and asked for the degree of some or all of its vertices

Goal: the degree of every vertex asked about, plus which of them are isolated or pendant

Degree, isolated, and pendant vertices, revisited

Classify a candidate H against G

Use when: you're given a graph G and a candidate H, or just a vertex subset, and asked whether H is a subgraph, an induced subgraph, a spanning subgraph, or none of these

Goal: a definite classification of H against G, backed by the exact vertex and edge check that produced it

Subgraphs, induced subgraphs, and spanning subgraphs

Determine whether two graphs are isomorphic

Use when: you're given two graphs G and H, possibly with entirely different vertex labels, and asked whether they're isomorphic

Goal: either a working bijection proving G is isomorphic to H, or one disagreeing invariant proving they aren't

Graph isomorphism, revisited

Classify a closed sequence of vertices

Use when: you're given a specific closed sequence of vertices in a graph and asked whether it's a closed walk, a circuit, or a cycle

Goal: the tightest classification the sequence actually earns, plus the check that proves it

Closed walks, circuits, and cycles, revisited

Walks, distance, and connectivity

Find the distance between two vertices

Use when: you're given a graph and two vertices u, v, and asked for d(u,v) without a search widget to slide through walk lengths for you

Goal: the exact shortest-path length between u and v, or confirmation that no path exists at all

Distance in a graph

Compute a vertex's eccentricity

Use when: you're given a connected graph and one specific vertex v, and asked for ecc(v)

Goal: the single largest distance from v to any other vertex in the graph

Eccentricity

Needs a vertex's distances to every other vertex, from the recipe above.

Find a graph's diameter and radius

Use when: you're given a connected graph (or one component of a disconnected graph) and asked for its single worst-case and best-case distances

Goal: two numbers, diam(G) and rad(G), read off the full list of every vertex's eccentricity

Diameter and radius

Needs every vertex's eccentricity, from the recipe above.

Find the center of a graph

Use when: you have a connected graph and need every vertex whose eccentricity is the smallest possible, not just the radius number itself

Goal: the exact set center(G): one vertex, several tied together, or the entire graph

The center of a graph

Needs every vertex's eccentricity too, compared against the radius.

Trees

Find the height of a rooted tree

Use when: you have a rooted tree and need its height, the length of the longest root-to-leaf path

Goal: the height as one number, plus which leaf or leaves actually achieve it

Rooted trees and rooted-tree terminology

Eulerian and Hamiltonian graphs

Search for a Hamiltonian path or cycle

Use when: you're given a small graph and asked to find a Hamiltonian path or Hamiltonian cycle, or to show none exists

Goal: either a full vertex order proving one exists, or confirmation that every branch of the search dead-ends

Hamiltonian paths and cycles

Graph coloring

Test a graph for bipartiteness

Use when: you're given a graph and asked whether it can be properly colored with only two colors

Goal: a genuine two-coloring if one exists, or a specific odd cycle proving that none can

Bipartite graphs and 2-colorability, revisited

The same technique as the readiness recipe above, taught formally as a course topic with the König's-theorem tie-in.

Planar graphs

Solve Euler's formula for an unknown count

Use when: you know any two of a connected plane graph's vertex count, edge count, and face count, and need the third

Goal: the missing count, plus confirmation the graph's connectedness hypothesis actually holds

Euler's formula for planar graphs

Shortest paths

Compute a path's weight

Use when: you're given a specific path through a weighted graph and need its total cost, or you're comparing two candidate paths to see which is actually shorter

Goal: the path's total weight, and confirmation that fewer edges doesn't automatically mean less weight

Weighted graphs, revisited

Audit a Dijkstra run for negative-edge corruption

Use when: a graph has at least one negative edge weight and you need to know whether Dijkstra's reported distances can actually be trusted

Goal: either a corrected distance where Dijkstra was wrong, or confirmation that every negative edge in the graph was harmless

Why Dijkstra's algorithm fails on negative weights

Directed graphs

Find all SCCs of a small digraph by hand

Use when: you can see every arc in a small digraph directly and need to group vertices by mutual reachability, without running Tarjan's or Kosaraju's algorithm

Goal: the complete partition of the digraph's vertices into maximal mutually reachable groups

Strongly connected components

Network flow and matching

Build the residual graph and find an augmenting path

Use when: you have a flow network with a partial or zero flow already in place and need to know whether more flow can still reach $t$

Goal: an augmenting path with its bottleneck, ready to push through, or confirmation that none remains

Residual graphs and augmenting paths · extended later in this course

Compute an s-t cut's capacity

Use when: you're given a partition of the vertices into S and T (with s in S and t in T) and need its capacity, or need to check whether a flow is already maximum

Goal: the cut's exact capacity, plus enough evidence to say whether a given flow is provably maximum

The max-flow min-cut theorem

Extends the recipe above with the cut-capacity argument that proves a flow is maximum once no augmenting path remains.

Prove a matching is maximum with a vertex cover

Use when: you already have a specific matching and need to show no larger one exists, without an exhaustive search

Goal: a matching-size vertex cover that certifies the matching is maximum, or the recognition that this test alone cannot decide the question

Matching, revisited

Check Hall's condition and find the deficiency

Use when: you have a bipartite graph and need to know whether every vertex in one side can be matched, or exactly how many cannot

Goal: either a confirmation that a matching saturating L exists, or the exact deficiency and the resulting maximum matching size when it doesn't

Hall's theorem, revisited

Model and solve a transportation or matching problem

Use when: you see two groups connected by capacity-limited connections, whether it's an exact one-to-one pairing or supplies and demands larger than one unit

Goal: a maximum flow value and a routing that shows exactly how many units move along every connection

Matching and flow in practice

Special graphs and graph counting

Test whether a k-regular graph can exist

Use when: you're given a vertex count $n$ and a target degree $k$ and asked whether a $k$ -regular graph on $n$ vertices exists

Goal: a feasibility verdict (yes or no), the edge count when it exists, and an explicit graph achieving it

Regular graphs, revisited