Skip to content
Tutorials Center
My learning

Topics

Lesson 66 of 68 ยท Practice and Review

Exercises: Graphs and Recurrences

Seventeen graded exercises on graphs, trees, coloring, shortest paths, matching and recurrence relations, each with a runnable Python solution.

The last two big topics of the course get their own exercise set: graph theory and recurrence relations. Seventeen exercises in four rounds take you from degrees and connectivity through spanning trees, coloring, shortest paths and matching, then to closed forms, the Master theorem and recurrences that come from counting problems. Each round ends with one runnable block that solves every exercise in code. The code is deliberately plain Python (lists, dictionaries, heapq) so you can read every step.

The grades are โ˜… (warm-up), โ˜…โ˜… (two ideas or some care) and โ˜…โ˜…โ˜… (a real puzzle). Work on paper first and commit to an answer; running the check afterwards is the point. If a round feels hard, revisit Graphs: Terms and Representations, Euler and Hamilton Paths, Trees and Spanning Trees, Graph Coloring and Planarity, Shortest Paths, Matching and Flows, Recurrence Relations and Solving Recurrences.

Four rounds

Graph basics Degrees, walks, components, Euler, trees.
Algorithms MST, coloring, Dijkstra, matching.
Solving recurrences Closed forms and growth rates.
Modeling Strings, Hanoi, tilings.
1 / 2

Round 1: graph basics

Exercise 1 (โ˜…โ˜…). Can a simple graph on 4 vertices have degrees 3, 3, 3, 1? What about 3, 2, 2, 1? How many different (sorted) degree sequences occur among all graphs on 4 vertices?

Exercise 2 (โ˜…โ˜…). The graph with vertices 0 to 4 and edges 0-1, 1-2, 2-3, 3-0, 0-2, 3-4 has an adjacency matrix A. Use Aยณ to count walks of length 3 from 0 to 2, and count the triangles with trace(Aยณ)/6.

Exercise 3 (โ˜…). Count the connected components of the graph on vertices 0 to 8 with edges 0-1, 1-2, 3-4, 5-6, 6-7, 7-5.

Exercise 4 (โ˜…โ˜…). Which of these have an Euler circuit: Kโ‚…, Kโ‚„, the 6-cycle, and the Kรถnigsberg bridge multigraph (land masses A, B, C, D with bridges A-B twice, A-C twice, A-D, B-D, C-D)?

Exercise 5 (โ˜…โ˜…โ˜…). How many labeled trees are there on 4 vertices and on 5 vertices? Count them by checking subsets of edges, then compare with Cayley's formula nโฟโปยฒ.

Python Solutions for Round 1

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Exercise 1: degrees (3, 3, 3, 1) are impossible, because three vertices of degree 3 must each touch every other vertex, so the fourth vertex would have degree 3. (3, 2, 2, 1) is possible. The enumeration of all 64 graphs finds 11 different sorted degree sequences. In Exercise 2, the matrix power counts walks (not paths): there are 5 walks of length 3 from 0 to 2, and the two triangles are 0-1-2 and 0-2-3. Exercise 3 has four components, because vertex 8 is alone. In Exercise 4 a connected graph has an Euler circuit exactly when every degree is even: Kโ‚… (all degrees 4) and the 6-cycle qualify, Kโ‚„ (degrees 3) does not, and the Kรถnigsberg graph has four odd degrees (5, 3, 3, 3), which is Euler's famous "no". Exercise 5 confirms Cayley: 16 labeled trees on 4 vertices and 125 on 5 vertices.

Round 2: algorithms on graphs

Exercise 6 (โ˜…โ˜…). For the weighted graph with edges A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, D-E 2, D-F 6, E-F 3, find a minimum spanning tree with Kruskal's algorithm and its total weight.

Exercise 7 (โ˜…โ˜…). Find the chromatic number of Kโ‚„, the 5-cycle, the 6-cycle and the Petersen graph by trying k = 1, 2, 3, โ€ฆ colors.

Exercise 8 (โ˜…โ˜…โ˜…). Using the weighted graph from Exercise 6, find the shortest path from A to F with Dijkstra's algorithm. Is it also the path in the minimum spanning tree?

Exercise 9 (โ˜…โ˜…โ˜…). Four workers and four jobs: worker 0 can do jobs 0 or 1, worker 1 only job 0, worker 2 jobs 0 or 1, worker 3 jobs 2 or 3. Find a maximum matching, and find a set of workers that violates Hall's condition.

Python Solutions for Round 2

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For Exercise 6 Kruskal takes the edges B-C (1), A-C (2), D-E (2), E-F (3) and B-D (5), and skips A-B (4) because it closes a cycle. The total weight is 13, with five edges for six vertices. Exercise 7 gives 4 for Kโ‚„, 3 for the odd cycle Cโ‚…, 2 for the even cycle Cโ‚† (even cycles are bipartite) and 3 for the Petersen graph. In Exercise 8, the shortest path is A โ†’ C โ†’ B โ†’ D โ†’ E โ†’ F with length 13. It uses exactly the edges of the minimum spanning tree here, but that is a coincidence of this graph: in general a shortest path need not lie inside the MST. In Exercise 9 the maximum matching has size 3, so no perfect matching exists. Workers 0, 1 and 2 only know jobs 0 and 1, so three workers compete for two jobs, which violates Hall's condition.

Round 3: solving recurrences

Exercise 10 (โ˜…). The sequence has aโ‚€ = 0 and aโ‚™ = 2aโ‚™โ‚‹โ‚ + 1. Guess a closed form and check it for n up to 30.

Exercise 11 (โ˜…โ˜…). With Fโ‚ = Fโ‚‚ = 1, check that Fโ‚ + Fโ‚‚ + โ€ฆ + Fโ‚™ = Fโ‚™โ‚Šโ‚‚ โˆ’ 1 and that Fโ‚™โ‚Šโ‚Fโ‚™โ‚‹โ‚ โˆ’ Fโ‚™ยฒ = (โˆ’1)โฟ (Cassini's identity).

Exercise 12 (โ˜…โ˜…). Solve aโ‚™ = 5aโ‚™โ‚‹โ‚ โˆ’ 6aโ‚™โ‚‹โ‚‚ with aโ‚€ = 1 and aโ‚ = 4 using the characteristic equation, then verify.

Exercise 13 (โ˜…โ˜…โ˜…). For T(1) = 1 compute T(n) for n a power of 2 for the recurrences T(n) = 2T(n/2) + n, T(n) = T(n/2) + 1 and T(n) = 4T(n/2) + n. What does the Master theorem predict for each, and do the numbers agree?

Python Solutions for Round 3

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For Exercise 10, the pattern 0, 1, 3, 7, 15, โ€ฆ is 2โฟ โˆ’ 1; adding 1 to both sides gives aโ‚™ + 1 = 2(aโ‚™โ‚‹โ‚ + 1), a doubling sequence. In Exercise 11 both identities hold for all tested n; they are proved by induction. In Exercise 12 the characteristic equation rยฒ โˆ’ 5r + 6 = 0 has roots 2 and 3, so aโ‚™ = Aยท2โฟ + Bยท3โฟ; the initial values A + B = 1 and 2A + 3B = 4 give A = โˆ’1 and B = 2, i.e. aโ‚™ = 2ยท3โฟ โˆ’ 2โฟ. For Exercise 13 the Master theorem predicts ฮ˜(n log n) for the first (a = 2, b = 2, work n), ฮ˜(log n) for the second and ฮ˜(nยฒ) for the third (the recursion dominates). The exact values for powers of two are n logโ‚‚ n + n, logโ‚‚ n + 1 and 2nยฒ โˆ’ n.

Round 4: modeling with recurrences

Exercise 14 (โ˜…โ˜…). How many binary strings of length n contain no two consecutive 1s? Count by brute force for n = 1 to 12, find the recurrence and verify it.

Exercise 15 (โ˜…โ˜…). How many moves does the Tower of Hanoi need for n disks? Simulate n = 10 and give the formula. How long would 64 disks take at one move per second?

Exercise 16 (โ˜…โ˜…โ˜…). In how many ways can you tile a 2 ร— n board with dominoes (1 ร— 2)? With dominoes and 2 ร— 2 squares? Count tilings by search for n = 1 to 8 and match them with recurrences.

Python Solutions for Round 4

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In Exercise 14 the counts are 2, 3, 5, 8, 13, โ€ฆ : a valid string ends in 0 (preceded by any valid string of length n โˆ’ 1) or ends in 01 (preceded by a valid string of length n โˆ’ 2), so f(n) = f(n โˆ’ 1) + f(n โˆ’ 2), a Fibonacci recurrence, and f(10) = 144. The Tower of Hanoi needs 2โฟ โˆ’ 1 moves: move n โˆ’ 1 disks away, move the biggest, and move n โˆ’ 1 disks back, so H(n) = 2H(n โˆ’ 1) + 1, which is Exercise 10 again. For 64 disks that is 18,446,744,073,709,551,615 moves, or about 585 billion years at a move per second. In Exercise 16 the last column of the board is either one vertical domino (leaving n โˆ’ 1 columns), or two horizontal dominoes (leaving n โˆ’ 2), which gives the Fibonacci numbers 1, 2, 3, 5, 8, โ€ฆ; with squares there is a second way to fill the last two columns, so t(n) = t(n โˆ’ 1) + 2t(n โˆ’ 2), giving 1, 3, 5, 11, 21, 43, 85, 171.

Scoring yourself

  • 14 to 17 solved before running: you have the graph and recurrence toolkit; continue with Discrete Math Interview Questions.
  • 9 to 13: redo the weak rounds after rereading the lessons linked at the top, changing the inputs (another graph, a different recurrence) and predicting the output first.
  • Fewer than 9: run each solution one function at a time and print intermediate values: the union-find parents in Kruskal, the heap in Dijkstra, the first ten terms of each recurrence.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is the degree sequence (3, 3, 3, 1) impossible for a simple graph on 4 vertices?

    The sum is 10, which is even, so parity is not the problem. But each degree-3 vertex touches all other three vertices, including the fourth, which therefore has degree 3, not 1.
  2. 2. Which condition does a connected graph need for an Euler circuit?

    Each time a circuit enters a vertex it must leave, so every degree must be even; for connected graphs this condition is also sufficient.
  3. 3. What is the closed form of a(n) = 5a(n-1) - 6a(n-2) with a(0) = 1 and a(1) = 4?

    The roots of r^2 - 5r + 6 are 2 and 3. Solving A + B = 1 and 2A + 3B = 4 gives A = -1, B = 2, so a(n) = 2 * 3^n - 2^n.
  4. 4. How many binary strings of length 10 contain no two consecutive 1s?

    The counts follow f(n) = f(n-1) + f(n-2) starting 2, 3, 5, 8, ..., so f(10) = 144.
  5. 5. Hall's condition fails for a set of workers when...

    If k workers together know fewer than k jobs, they cannot all be matched, so no perfect matching exists.

Summary

  • Degrees, the handshake lemma and the even-degree test settle many questions (such as Euler circuits) without searching.
  • Cayley's formula nโฟโปยฒ counts labeled trees; Kruskal's algorithm builds a minimum spanning tree by taking the cheapest edge that does not close a cycle.
  • Chromatic numbers: bipartite graphs need 2 colors, odd cycles need 3, and Kโ‚„ needs 4.
  • Dijkstra finds shortest paths with non-negative weights; augmenting paths find maximum matchings, and Hall's condition explains when a perfect matching is impossible.
  • Closed forms come from guessing and verifying, or from the characteristic equation; the Master theorem gives growth rates; modeling a counting problem usually produces a recurrence from the last decision.

Next: Discrete Math Interview Questions.