Graph Algorithms

How to use this page

This page is for priming. The goal is to learn the shape of each topic before the lecture: the problem, the key idea, what the algorithm looks like while it runs, and the questions the proof has to answer. You don't need to master anything here. When the lecture fills in the details, you'll already have somewhere to put them.

1. Read the map first (2 min). There are six problems, three design techniques, and one proof pattern that keeps coming back.
2. Work up through the levels. Each algorithm has three: Simple (just the mechanism), Notes example (the one from the lecture), and Harder (a bigger graph to test yourself).
3. For each animation, guess before you click. Before pressing next, say which vertex or edge you expect to be picked. A wrong guess you then correct sticks far better than passively watching the answer.
4. Keep the "carry into the lecture" questions in mind. They are what the proofs in the notes are really answering.
5. Do the self-test the next day. Retrieval practice after a gap is what moves this into long-term memory.
6. If a symbol or a proof step feels shaky (∀, ⇒, set-builder, induction, big-O), use the Maths refresher tab.

0. Lecture 1: what was said

Summary of lecture 1 (28 Sep).

The module and how it runs

How you're expected to learn

The terminology she reviewed, and the points she stressed

It all maps onto section 2, and you can practise it in the notation worksheet. The points below are the ones she made a point of, so they're likely to matter in proofs and exams.

1. "Graph" means simple graph. E is a set of 2-element subsets of V. Why: for these problems, parallel edges or loops add nothing. For a shortest path you'd always use the cheaper of two parallel edges, so you can delete the other. A multigraph allows loops and multiple edges. A digraph's edges are ordered pairs.
2. Abuse of notation is allowed only once it's been established. Writing uv for {u,v} and G − v for G − {v} is fine because the notes set it up. In your own work you can't invent notation unless you define it first. Otherwise, stick to the conventions of the notes.
3. uv means different things in different contexts. In a graph uv = vu. In a digraph, uv is the arc from u to v, and vu is a different arc.
4. In a simple graph a walk can be written as just its vertices, since there's exactly one edge between adjacent vertices. So v₁, v₂, v₁ is a walk: each consecutive pair is adjacent, and that's the only condition.
5. Why is a cycle a "closed trail with distinct vertices except start = end", and not a "closed path"? Because a path can't repeat any vertex, including its first one at the end. So a "closed path" can't exist. The wording is chosen carefully.
6. A drawing of one example is not a proof. To prove "for every graph…", you can't check one particular graph. Her abstract drawings (a wiggly line for "some trail") stand for all possible cases. A picture of a specific graph is only an example.
7. Connected is a ∀∃ statement: for every pair of vertices there exists a path. There may be many paths; you only need one.
8. Component = inclusion-wise maximal connected induced subgraph. Her example: a connected piece that is missing an edge between two of its vertices isn't maximal, because you can add the edge. After adding it, nothing more can be added, so it's a component.
9. Leaf lemma, quoted carefully: every tree with at least 2 vertices has at least 2 leaves. A single vertex is a tree with no leaves. The lemma is the standard tool for induction on the number of vertices.
10. Forest: every connected component is a tree (equivalently, it has no cycle).
11. "Weighted graph" means edge-weighted throughout this part of the module. Vertex weights exist in other settings but aren't used here.

Second half (after the break)

1. The map

Throughout, n = |V| (vertices) and m = |E| (edges).

2. Vocabulary you're expected to be fluent in

Each term has three lines: formal (as in the notes), ELI5 (the plain idea), and analogy. One picture runs through all the analogies: a graph is a map of towns (vertices) joined by roads (edges).

Basics

graph G = (V, E)

formal V is a finite set of vertices. E is a set of 2-element subsets {u,v} of V, written uv.
ELI5 Some dots, and some lines that each join two dots. There's at most one line between any two dots, and no line from a dot back to itself.
analogy Towns, and the direct roads between them.

adjacent / neighbours, N(v); incident; endvertices

formal u,v are adjacent if uv ∈ E. N(v) = {u : uv ∈ E}. u is incident with e if u ∈ e.
ELI5 Two dots are neighbours if a line joins them. A line "touches" (is incident with) the two dots at its ends.
analogy N(v) is the list of towns you can reach from v in one drive. A road is incident with the two towns it connects.

walk → trail → path; closed walk; cycle

formal Walk: v₀,e₁,v₁,…,e_k,v_k, with each edge joining the vertices either side of it. Trail: no repeated edge. Path: no repeated vertex. Closed: v₀ = v_k. Cycle: a closed trail whose only repeat is the start/end.
ELI5 A walk is any route. A trail never uses the same line twice. A path never visits the same dot twice. A cycle is a loop back home with no other repeats.
analogy Walk: a wandering drive, going wherever you like, any number of times. Trail: a snowplough that never clears the same road twice. Path: a tourist who refuses to see the same town twice. Cycle: a bus route that starts and ends at the depot and visits each stop once.
note Every path is a trail, and every trail is a walk. The reverse is not true.

Subgraphs (being explained right now)

Same base graph G each time. Bold = kept, faint dashed = thrown away.

subgraph H ⊆ G (and supergraph)

formal V(H) ⊆ V(G) and E(H) ⊆ E(G), and H must itself be a graph. G is then a supergraph of H.
ELI5 Keep some dots and some lines, rubbing out the rest. One rule: you can't keep a line if you've rubbed out a dot at either end.
analogy A delivery driver's personal map, showing only the towns and roads they use. It can leave out roads even between towns that are on it. The full national map is the supergraph.

spanning subgraph

formal H ⊆ G and V(H) = V(G).
ELI5 Keep every dot. You may throw away lines.
analogy A snowstorm: some roads close, but every town is still on the map (possibly cut off).
why you care A spanning tree is a spanning subgraph that is a tree. It is the whole point of §2.

proper subgraph

formal H ⊆ G and H ≠ G.
ELI5 A subgraph that is missing at least one thing, either a dot or a line.
analogy Like "proper subset" (⊂ vs ⊆): a slice of the pizza, not the whole pizza. G counts as a subgraph of itself, but not as a proper one.

induced subgraph G[U]

formal Vertex set U, and edge set {xy ∈ E(G) : x,y ∈ U}. "The subgraph of G induced by U."
ELI5 You only choose the dots. Every line between chosen dots comes along automatically; you're not allowed to drop any of them.
analogy A party: you choose the guest list (U), and every friendship between guests comes too. You can't un-friend two guests at the door. Or: zoom a map in on a region, and you see all the roads inside it.

G − S (delete vertices)

formal Remove the vertices in S and every edge touching them. G − S = G[V(G) ∖ S]. For one vertex, write G − v.
ELI5 Rub out some dots, and any line that loses an end disappears with them.
analogy Towns flooded: the town goes, and so does every road into it.
note G − S is always an induced subgraph.

G − F (delete edges)

formal V(G − F) = V(G) and E(G − F) = E(G) ∖ F. For one edge, write G − e.
ELI5 Rub out some lines only. All the dots stay.
analogy Roadworks: some roads closed, no towns lost.
note G − F is always a spanning subgraph. G − e is how the notes define a cut-edge.

Connectivity and trees

connected she said: "this needs to be ingrained in your brain"

formal G is connected if for every pair of vertices u, v ∈ V(G) there is a (u,v)-path in G.
symbols ∀u, v ∈ V(G)  ∃ a (u,v)-path in G.   This is "doubly quantified": first ∀, then ∃.
ELI5 Pick any two dots. Can you always trace from one to the other along the lines? If yes for every choice, the graph is connected. It's all in one piece.
analogy A road network where you can drive from any town to any other town, maybe through other towns and not necessarily directly.

disconnected

formal Not connected: ∃u, v ∈ V(G) with no (u,v)-path.
ELI5 At least two pieces. Some pair of dots can't reach each other.
analogy An island with no bridge or ferry.

connected component

formal An inclusion-wise maximal connected induced subgraph of G.
ELI5 One whole piece: connected, and you can't add anything to it without breaking connectivity. "Induced" means it keeps all the edges between its vertices.
analogy A country of islands with no ferries: each island (with all its roads) is a component.
lecture example A connected piece that is missing one edge between two of its vertices is not maximal, because you can add that edge. Once nothing more can be added, it's a component.

forest (acyclic), tree, leaf

formal A forest has no cycle. A tree is a connected forest. A leaf is a vertex of degree 1.
ELI5 A tree is all in one piece, with no loops. A forest is several trees side by side. A leaf is a dot with only one line.
analogy A tree is like a family tree or the folders on your computer: exactly one route between any two things. A leaf is a dead-end town with only one road in.

cut-edge (bridge)

formal In connected G, e is a cut-edge if G − e is disconnected. Lemma 2.1: e is not a cut-edge ⇔ e lies on a cycle.
ELI5 A line that you can't remove without splitting the picture in two.
analogy The only bridge to an island. Lemma 2.1 in town terms: a road can close without cutting anyone off exactly when there's a detour, and a detour plus the road makes a cycle.

Theorem 2.3 (used constantly)

formal For n-vertex G, these are equivalent: (a) connected and acyclic, (b) connected with n−1 edges, (c) acyclic with n−1 edges, (d) exactly one path between each pair of vertices.
ELI5 n−1 lines is the magic number. With fewer, you can't join n dots. With more, you're forced into a loop.
analogy Linking n towns with the fewest roads needs exactly n−1 roads. Add one more road and you've built exactly one round trip. That's the "T* + e has a unique cycle" step in every MST proof.

Weights and directions

(edge-)weighted graph

formal G together with w: E → ℕ (or ℤ).
ELI5 Every line has a number written on it.
analogy Each road's length, toll or travel time.

directed graph (digraph) D = (V, A)

formal The arcs are ordered pairs (x,y), so xy ≠ yx. Paths and cycles have to follow the directions.
ELI5 The lines are arrows, and you can only travel the way they point.
analogy One-way streets. Or following someone online: you following them doesn't mean they follow you.

2½. Lemmas 2.1 & 2.2: the first proofs

Proved on the board in lecture 1 (second half). These two lemmas are the foundation for everything in §2: every MST proof uses "an edge on a cycle can be removed safely".

Step 0: classify the statement before writing anything

This is the routine she walked through before the first line of the proof. It comes from the logic part of the course (see the refresher on quantifiers and logic).

In symbols: ∀G ( G has a spanning tree ⇔ G is connected ). For Lemma 2.1: ∀G connected, ∀e ∈ E(G): ( e is not a cut-edge ⇔ e lies on a cycle of G ).

Lemma 2.1, seen

edge cycle / detour edge being removed removed

Lemma 2.2: the board proof, line by line

Lemma 2.2 (⇐), seen: why "fewest edges" works

current subgraph a cycle in it edge to delete deleted

Carry into the next lecture

• Lemma 2.1 says a cycle edge is "safe" to delete. The MST proofs turn this around: adding an edge to a tree creates exactly one cycle, and removing another edge of that cycle keeps a tree. Look for this in the Prim proof (T* + e − e′).
• The extremal choice here ("fewest edges") comes back in Kruskal's proof ("the MST with the most edges in common with T").

3. Minimum weight spanning trees

Problem. You are given a connected graph with edge weights w: E → ℕ. Find a spanning tree T whose total weight w(T) = Σ w(e) is as small as possible. Typical uses: wiring n pins with the least wire, or the cheapest road network that still links every town.

Optimisation problems and greedy algorithms (§2.1). An optimisation problem asks for the best of all feasible solutions under some cost. Here the feasible solutions are the spanning trees and the cost is w(T), to be minimised. A greedy algorithm makes the choice that is locally best at each step and never reconsiders it, hoping that this leads to a global optimum. In general it doesn't. For MST it provably does, and that proof is Theorem 2.4. (The general theory of when greedy works involves matroids and is optional reading.)

Facts to know. A graph has a spanning tree ⇔ it is connected (Lemma 2.2). A spanning tree always has n−1 edges. The MST need not be unique, but its weight is.

Prim's algorithm: grow one tree

1  E_T ← ∅
2  V_T ← {u}                         any start vertex
3  for v ∉ V_T:  L(v) ← w(uv)        (∞ if no edge), e_v ← uv
4  while V_T ≠ V:
5      x ← vertex outside V_T with minimum L(x);  e ← e_x
6      E_T ← E_T ∪ {e}
7      V_T ← V_T ∪ {x}
8      for v ∉ V_T:  if w(vx) < L(v):  L(v) ← w(vx), e_v ← vx

tree current best edge e_v chosen now · orange numbers = labels L(v)

Why it's correct (Theorem 2.4), the shape of the proof. Induction on |V_T|. The claim is "T is a subtree of some MST T*". When edge e = xy is added, either e ∈ T* (done), or T* + e contains a unique cycle C. C crosses from V_T to outside once via e, so it must cross back via some other edge e′. Swap them: T** = T* + e − e′ is still a spanning tree, and w(e) ≤ w(e′) because line 5 picked the minimum. So T** is also an MST, and it contains T + e.

Cost. With an array of labels, line 5 is O(n) and runs n times, giving O(n²). With a Fibonacci heap (you'll meet it later in COMP2870) the total is O(m + n log n). For a maximum spanning tree, replace min with max.

Kruskal's algorithm: merge a forest

1  sort edges: w(e_1) ≤ w(e_2) ≤ … ≤ w(e_m)
2  E_T ← ∅,  V_T ← V                 every vertex is its own component
3  for i = 1 … m:
       if T + e_i is acyclic:  E_T ← E_T ∪ {e_i}

colour = connected component accepted examining would make a cycle

Why it's correct (Theorem 2.5). (1) T is spanning and connected. If it weren't, some edge of G would join two components of T. That edge creates no cycle, so line 3 would have accepted it. (2) T is minimum. Take the MST T* that shares the most edges with T. Let e_i be the first edge (in sorted order) that is in T but not in T*. T* + e_i has a cycle containing some e_j ∉ T with j ≥ i, so w(e_i) ≤ w(e_j). Then T* + e_i − e_j is an MST sharing more edges with T, which contradicts the choice of T*. This is the same exchange trick as for Prim, framed as a contradiction.

Cost. Sorting takes O(m log m) = O(m log n), since m ≤ n². The cycle test uses a union–find structure: find tells you which component a vertex is in, and union merges two components. That gives O(m log n) in total. Rule of thumb: Prim is better for dense graphs, Kruskal is better in practice for sparse ones.

Aside: a Steiner tree only has to span a chosen subset V′ ⊂ V. That small change makes the problem NP-complete, so no efficient algorithm is known.

Carry into the lecture

• Greedy fails for many problems. What property of spanning trees makes it safe here? (Hint: the swap e ↔ e′.)
• Prim and Kruskal produced the same tree above. Must they always? What if weights are tied?
• Why does the Prim proof need the cycle to cross the boundary V_T | V∖V_T twice?
• Kruskal's "is T + e acyclic?" can be answered with BFS or DFS. Why is that too slow, and what does union–find buy you?

4. Shortest paths

Setting. A weighted directed graph (think of one-way streets). The weight of a path is the sum of its edge weights. dist(u,v) is the minimum weight of a (u,v)-path, or ∞ if no such path exists. A shortest path is one that achieves dist.

Dijkstra: single source, non-negative weights

1  for v ≠ s:  L(v) ← w(sv)          (∞ if no edge)
2  L(s) ← 0
3  T ← {s}
4  while T ≠ V:
5      v′ ← vertex ∉ T with minimum L(v′)
6      T ← T ∪ {v′}
7      for v ∉ T:  if L(v′) + w(v′v) < L(v):  L(v) ← L(v′) + w(v′v)

shortest-path tree edge giving current L(v) just finalised / relaxed · black vertex = in T (final)

Spot the similarity. This is Prim's skeleton with a different label. Prim uses L(v) = w(xv), the cost to attach one more edge. Dijkstra uses L(v) = L(v′) + w(v′v), the cost of the whole path from s.

Why it's correct (Theorem 3.1). Induction on |T| with two invariants: (a) for v ∈ T, L(v) = dist(s,v); (b) for v ∉ T, L(v) = the shortest path to v whose other vertices are all in T. The key step: suppose v′ is picked but L(v′) is not the true distance. Then a genuinely shorter path leaves T at some earlier vertex v″, with L(v″) ≤ (part of that path) < L(v′). But line 5 picked v′ as the minimum, a contradiction. The step "a prefix of a path is no longer than the path" needs w ≥ 0.

Cost. O(m + n log n) with a Fibonacci heap, the same analysis as for Prim.

Why negative weights break Dijkstra

Floyd–Warshall: all pairs, negative edges allowed

Running Dijkstra from every vertex works when all weights are positive. Floyd–Warshall handles integer weights of either sign, as long as there is no closed walk of negative weight. Otherwise "shortest" is meaningless, because you could go round the negative loop forever.

1–6  d_0 ← adjacency weights (0 on diagonal, ∞ for non-edges)
7    for k ← 1 to n:                  k MUST be the outer loop
8      for u ∈ V:
9        for v ∈ V:
10         d_k(u,v) ← min{ d_{k−1}(u,v), d_{k−1}(u,k) + d_{k−1}(k,v) }

shaded = row k and column k, the only entries each update reads · orange = entry improved in this round

Why it's correct (Theorem 3.2). Induction on k. The claim is d_k(u,v) = the distance from u to v in G[{u,v,1,…,k}]. The proof has two inequalities. (≤) Joining a shortest u→k path and a shortest k→v path gives a walk. Split off any closed part, which has weight ≥ 0 because there are no negative closed walks, and you're left with a path that is no longer. (≥) A shortest path either avoids k or splits at k into two shorter subproblems.

Cost. Three nested loops, so O(n³).

Carry into the lecture

• In Dijkstra, at the moment v′ is chosen, why can no future discovery ever lower L(v′)?
• Where exactly does the Dijkstra proof use w ≥ 0? Find the line in the animation above where the negative edge "arrives too late".
• In Floyd–Warshall, why must k be the outermost loop? What goes wrong if you loop over u first?
• How would a negative cycle show up in the final matrix? (Look at the diagonal.)
• Why is the longest path problem hard (NP-complete) when the shortest path problem is easy?

5. Maximum flow

Setting. A network is a digraph with capacities c: E → ℕ, a source s and a sink t. A flow f: E → ℕ is feasible if it satisfies two constraints:

• capacity: 0 ≤ f(e) ≤ c(e) on every edge, and
• conservation: flow in = flow out, f⁻(v) = f⁺(v), at every v ≠ s,t.

The value of the flow is val(f) = f⁻(t) − f⁺(t), the net flow into t. The goal is a feasible flow of maximum value.

f-augmenting path

An s→t path that ignores edge directions. Forward edges must have spare capacity (f < c). Backward edges must carry some flow (f > 0). Pushing flow "backwards" means cancelling flow that was sent earlier, i.e. rerouting it.

leeway ε

The minimum over the path of (c − f) on forward edges and f on backward edges. Adding ε forward and subtracting ε backward gives a feasible flow with value val(f) + ε (Lemma 4.1).

source/sink cut [S,T]

A partition of V with s ∈ S and t ∈ T. Its capacity cap(S,T) is the sum of c over edges from S to T only.

Weak duality (Cor. 4.3)

val(f) ≤ cap(S,T) for every feasible flow and every cut, because all flow has to cross the cut. So if you ever find a flow and a cut with equal values, both are optimal.

Ford–Fulkerson (labelling algorithm)

R ← {s}, S ← ∅
repeat:  pick v ∈ R∖S
   for each edge vw leaving v:   if f(vw) < c(vw)  → add w to R   (forward)
   for each edge uv entering v:  if f(uv) > 0      → add u to R   (backward)
   add v to S
   if t ∈ R:  trace back → augmenting path
   if R = S:  return cut [S, V∖S]

labels f/c empty full forward on path backward on path · black = searched (S), orange ring = reached (R∖S)

Max-Flow Min-Cut Theorem (4.4). In every network, the maximum flow value equals the minimum cut capacity. Proof idea: each augmentation raises val by at least 1 and the capacities are integers, so the algorithm stops. When it stops, every S→T edge is full and every T→S edge is empty, so val(f) = cap(S,T).

Cost. Each labelling pass is O(m) (a DFS or BFS), and there are at most val(f*) ≤ nU augmentations, where U = max capacity. That gives O(nmU). This is exponential in the input length, because U is written in binary. Capacity scaling improves it to O(nm log U).

Carry into the lecture

• In the animation (level 2), the path s→x←v→t uses a backward edge. Physically, what happens to the unit of flow that was on vx?
• Why does the cut capacity count only S→T edges and not T→S edges?
• Where does the proof use that capacities are integers? What could go wrong with irrational capacities?
• Weak duality gives you a way to certify optimality without trusting the algorithm. Why is that valuable (e.g. when checking GenAI output)?

6. Maximum matchings in bipartite graphs

A matching M ⊆ E is a set of edges no two of which share a vertex. A vertex is M-saturated if some edge of M touches it. M is perfect if every vertex is saturated, and maximum if no matching has more edges. A graph is bipartite (V₁, V₂) if every edge goes between V₁ and V₂. Example: people and jobs, where each person does at most one job and each job needs one person.

Reduction to maximum flow

forward on augmenting path backward = "un-match" flow 1 / matched

Why it's correct (Theorem 5.1). Each u ∈ V₁ has only one incoming edge (su, capacity 1). By conservation, at most one of its outgoing edges can carry flow, and symmetrically for V₂ with t. So flow-1 edges form a matching. In the other direction, any matching M′ gives a feasible flow of value |M′|. So a bigger matching would give a bigger flow, which contradicts maximality.

Notice. The last augmenting path in level 2, s→2→a←1→b←3→c→t, alternates between unmatched and matched edges. That is exactly an M-augmenting path in G, and it is the bridge to the next section.

Cost. O(nm). Faster methods exist: Hopcroft–Karp runs in O(√n·m).

Carry into the lecture

• Why must every capacity be 1, including on the s- and t-edges? What would capacity 2 on su allow?
• Why does "Ford–Fulkerson from the zero flow gives integer flows" matter for this reduction?
• Relate each augmentation to the matching: one more matched pair each time, and backward edges = swapping partners.

7. Beyond bipartite: Berge & Edmonds optional in the notes (§5.2)

An M-alternating path uses edges that alternate between not-in-M and in-M. It is M-augmenting if both of its ends are unsaturated. Flipping it (matched ↔ unmatched) grows |M| by 1.

In bipartite graphs, searching for alternating paths is easy. In general graphs, odd cycles cause trouble: a vertex can be reached along a path of either parity. Edmonds' fix (1965) is to spot the odd cycle (a blossom), contract it to a single super-vertex, keep searching, and expand it again at the end.

This is Figure 15/16 from the notes. Edmonds' original algorithm runs in O(n⁴). The fastest known, Micali–Vazirani, runs in O(√n·m).

8. Self-test (do this tomorrow, not today)

R1 · Number sets and ∞

R2 · Sets

R3 · Set-builder notation {x ∈ A | P(x)}

  { u ∈ V(G)  |  uv ∈ E(G) }
    ─┬─ ──┬──  ┬  ────┬────
     │    │    │      └── condition: which elements to keep
     │    │    └── "such that"   ( | and : mean the same thing )
     │    └── where to look (the domain)
     └── the variable (a dummy name)
  read: "the set of all u in V(G) such that uv is an edge of G"   =  N_G(v)

Two forms. Filter: {x ∈ A | P(x)} keeps the elements of A that satisfy P. Image: {f(x) : x ∈ A} computes f(x) for each x, e.g. {w(e) : e ∈ E} is the set of all edge weights.

Bound vs free variables. In {u ∈ V | uv ∈ E}, u is a dummy (bound) variable, so renaming it to x changes nothing. v is free: it must already be fixed outside ("for a vertex v…"), and the set depends on it.

R4 · Ordered pairs, sequences, indices

• (u, v) is an ordered pair: (u,v) ≠ (v,u) unless u = v. Compare the set {u,v} = {v,u}. Digraph arcs are ordered pairs; graph edges are sets.
• A × B = {(a,b) : a ∈ A, b ∈ B}, the Cartesian product. A digraph's arc set satisfies A ⊆ V × V.
• G = (V, E) is itself an ordered pair: a graph is "a pair of sets".
• Sequences with indices: v₀, v₁, …, v_k has k+1 terms. "For every i ∈ {1,…,k}, e_i is incident with v_i−1 and v_i." Always check where the index starts and stops, since off-by-one mistakes are the classic slip.
• Relabelling: "Relabel E = {e₁,…,e_|E|} so that w(e₁) ≤ … ≤ w(e_|E|)" just means sort the edges and name them in that order.

R5 · Functions

• f : A → B is read "f is a function from A to B". A is the domain and B the codomain. It assigns exactly one f(a) ∈ B to every a ∈ A.
• w : E → ℕ: every edge gets one natural-number weight. c (capacity) and f (flow) are also functions E → ℕ.
• Labels are functions on vertices: L : V → ℕ ∪ {∞} in Prim and Dijkstra. "L(v) ← …" in pseudocode means "update the value of L at v".
• Two-argument functions: dist : V × V → ℕ ∪ {∞}, and d_k(u,v) in Floyd–Warshall.
• Extending a function to a set: w(T) := Σ_e∈E(T) w(e) is a new definition that reuses the name w. You'll see this "overloading" often.
• ← vs = vs := "x ← y" (pseudocode) means assign y to x. "=" is a claim that two things are equal. ":=" means "is defined as".

R6 · Sums, min, max

  Σ         w(e)        "the sum, over all edges e in E(T), of w(e)"
 e∈E(T)

  Σ    d(v) = 2m        "the sum of the degrees is twice the number of edges" (handshake lemma)
 v∈V

  Σ_{i=1}^{k} w(v_{i−1} v_i)   "sum for i from 1 to k"  = weight of the path v_0,…,v_k

• The index under Σ is a dummy variable. The condition under Σ filters which terms to include, like set-builder notation.
• An empty sum = 0. By convention, min ∅ = ∞, which is why dist(u,v) = ∞ when no path exists.
• "Find x for which L(x) = min{L(v) : v ∈ V ∖ V_T}" picks an element that achieves the minimum (an "argmin"). It may not be unique, and then any choice works.
• Weak vs strict: ≤ allows equality and < doesn't. Proofs often hinge on this (e.g. w(e) ≤ w(e′) in the Prim proof).

R7 · Propositional logic: ¬ ∧ ∨ ⇒ ⇔

Ways of saying P ⇒ Q (all the same)

if P then Q · P implies Q · Q if P · P only if Q · P is sufficient for Q · Q is necessary for P · whenever P, Q

Related statements

Lemma 2.1 is an iff: both the original and the converse hold. That's why the notes use ⇔, and why its proof needs two directions, (⇒) and (⇐).

Laws you use without noticing

• P ⇔ Q ≡ (P ⇒ Q) ∧ (Q ⇒ P)
• P ⇒ Q ≡ ¬P ∨ Q
• De Morgan: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q, and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
• ¬¬P ≡ P
• Theorem 2.3 says "(a), (b), (c), (d) are equivalent". The usual way to prove this is a cycle of implications, (a)⇒(b)⇒(c)⇒(d)⇒(a), and "(a) ⇒ (d)" in a proof quotes one link of that cycle.

R8 · Quantifiers: ∀ (upside-down A) and ∃ (backwards E)

Order matters

∀v ∈ V ∃u ∈ V: uv ∈ E means "every vertex has a neighbour" (u may depend on v).
∃u ∈ V ∀v ∈ V∖{u}: uv ∈ E means "one vertex is adjacent to all the others". This is much stronger.
Connected is ∀u,v ∃ a (u,v)-path. The path may differ for each pair.

Negating: flip each quantifier, then negate the inside

¬ ∀x P(x)  ≡  ∃x ¬P(x)          ¬ ∃x P(x)  ≡  ∀x ¬P(x)

"G is connected"      ∀u,v ∈ V  ∃ (u,v)-path
"G is NOT connected"  ∃u,v ∈ V  such that there is NO (u,v)-path

Hidden quantifiers and how a proof handles them

• "A tree on n vertices has n−1 edges" has a hidden ∀: it holds for every tree.
• To prove ∀x P(x): write "Let x be arbitrary" and prove P(x) using only what you're given. A drawing of one example is not enough (her point in lecture 1).
• To prove ∃x P(x): construct or exhibit one x. "Since G is connected, there is a (u,v)-path P" uses an ∃ you already know.
• To disprove ∀: one counterexample is enough. To disprove ∃: you need a proof for all.
• Vacuous truth: "∀v ∈ ∅: …" is automatically true. For example, when T = V the loop "for all v ∉ T" does nothing.

R9 · Proof methods, and where each appears in the notes

INDUCTION TEMPLATE
Claim: for every n ≥ n₀, S(n).
Base case (n = n₀):  … so S(n₀) holds.
Induction hypothesis: assume S(k) holds for some k ≥ n₀.        (strong: for all n₀ ≤ j ≤ k)
Induction step: we show S(k+1). … by the induction hypothesis … hence S(k+1).
By induction, S(n) holds for all n ≥ n₀.  □

R10 · Proof language (fixed phrases)

Avoid "clearly" and "obviously" unless it really is one line. Avoid "it" when two objects are in play: name them. Don't start using a symbol you haven't introduced.

R11 · Words that have precise meanings

R12 · Big-O and running time

f(n) = O(g(n)) means f grows no faster than g, up to a constant: ∃c > 0 ∃n₀ ∀n ≥ n₀: f(n) ≤ c·g(n).
In practice, drop constants and lower-order terms: 3n² + 5n + 7 = O(n²).

Growth order: 1 < log n < n < n log n < n² < n³ < 2ⁿ. The notes' algorithms sit between n log n and n³.

• n = |V|, m = |E| throughout. In a simple graph m ≤ n(n−1)/2, so m = O(n²) and log m = O(log n). That's why O(m log m) = O(m log n) for Kruskal.
• Dense graph: m is about n². Sparse: m is about n. O(m + n log n) is roughly n² for dense graphs and n log n for sparse ones.
• Σ_v d(v) = 2m is the trick behind "the inner loop runs d(x) times, so O(m) in total" (Prim, Dijkstra).
• Polynomial in the input length: numbers are stored in binary, so a capacity U takes about log U bits. O(nmU) is exponential in the input length, while O(nm log U) is polynomial.
• Amortized O(log n): averaged over a sequence of operations, as in the Fibonacci heap. You'll meet it later in the module.