Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 36 · Projects and Practice

Graph Theory Practice Problems

Eight graph theory exercises with worked, runnable solutions: degree sequences, two-team splits, domino tilings, edge connectivity, Mycielski graphs, planarity bounds and Laplacian components.

You learn graph theory by solving problems, not by reading about it. This lesson collects eight problems that draw on the second half of the course: coloring, matching, planarity, flows and spectra. For each one, read the statement and try to solve it on paper (or in your head) before running the solution. The code is deliberately short and every answer is checked by the program itself.

A good habit for graph problems: first ask which classical problem is hiding here? Splitting people into two groups is bipartiteness. Pairing things up is matching. "Minimum number of things to remove to disconnect" is a minimum cut. Using the right name usually gives you an algorithm for free.

flowchart TD
    Q["A graph problem"] --> A{"Split into two groups, no conflict?"}
    Q --> B{"Pair up or assign one-to-one?"}
    Q --> C{"Smallest set to separate or capacity?"}
    Q --> D{"Few resources, no clashes?"}
    A --> A1["Bipartite test, 2-coloring"]
    B --> B1["Matching, Hall, flow"]
    C --> C1["Max-flow min-cut"]
    D --> D1["Graph coloring"]

Match the problem to its classical form before coding.

Problems 1 and 2: degree sequences and two teams

Problem 1. Which of these lists can be the degrees of a simple graph (no loops, no repeated edges)? [3, 3, 2, 2, 2], [4, 4, 4, 1, 1], [3, 3, 3, 1]. If one is possible, build a graph.

The Havel-Hakimi algorithm answers it: sort descending, remove the largest d, and subtract 1 from the next d largest entries. If you ever need to subtract from fewer than d entries, or reach a negative number, the sequence is not graphical; if you reach all zeros, it is.

Problem 2. Eight people have a list of "cannot be on the same team" pairs. Can they be split into two teams? If yes, give the teams; if no, name a conflict cycle of odd length.

Python Solutions to problems 1 and 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.

The second list adds the conflict A-C to the chain A-B-C, which closes the odd cycle A-B-C. The program finds that cycle for you, however deeply it hides among even cycles in a longer list. For a larger conflict list, an algorithm spots in milliseconds what eyes miss.

Problems 3 and 4: dominoes and edge connectivity

Problem 3. A 4×4 board has two opposite corners removed (cells (0,0) and (3,3)). Can it be tiled by 1×2 dominoes? The program also tries two other removals, one of two same-colored cells and one of two neighbors.

Color the board like a checkerboard. Every domino covers one black and one white cell, so a tiling is a perfect matching in the bipartite graph of adjacent cells. If the colors are unbalanced, the matching cannot be perfect (Hall's condition fails immediately).

Problem 4. A network of 7 routers is connected by cables. What is the minimum number of cables whose failure disconnects the network (its edge connectivity)? Hint: compute the max flow (with unit capacities) from router 0 to every other router; the smallest value is the answer, because some cut must separate router 0 from some other router.

Python Solutions to problems 3 and 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.

The corners (0,0) and (3,3) have the same color (row plus column is even for both), so removing them leaves 6 cells of one color and 8 of the other: no tiling can exist. The cells (0,0) and (2,2) are also both black. Removing (0,0) and (0,1), two neighbors of different colors, leaves 7 and 7 and a perfect matching exists. Balance is necessary; the matching algorithm checks whether it is also sufficient.

Problems 5 and 6: a triangle-free surprise and color counting

Problem 5 (Mycielski). Show that triangle-free graphs can need many colors by building the Mycielski graph of the 5-cycle (11 vertices). Add a copy u_i of each vertex v_i, joined to the neighbors of v_i in the original graph, and one extra vertex w joined to every copy. Compute its largest clique size and its chromatic number.

Problem 6 (planarity). A connected simple planar graph has 10 vertices and is triangle-free. What is the largest possible number of edges? Could such a graph with 17 edges exist?

Python Solutions to problems 5 and 6

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.

The graph has a clique number of 2 (no triangles) yet needs 4 colors: the clique lower bound can be far from the truth. It is called the Grötzsch graph, the smallest triangle-free graph with chromatic number 4. For problem 6, planar triangle-free graphs satisfy E ≤ 2V − 4 = 16, so 17 edges is impossible; the bound is reached, for example, by a planar bipartite graph such as K_{2,8} (which has exactly 16 edges).

Problems 7 and 8: the Laplacian does the counting

Problem 7. Use only eigenvalues to count the connected components of a graph with 9 vertices, without searching it.

Problem 8. Rank three graphs on 8 vertices (a path, a cycle and a "barbell" of two 4-cliques joined by a bridge) by how hard they are to cut in two, using algebraic connectivity.

Python Solutions to problems 7 and 8

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.

The path and the barbell both have bottlenecks, and the numbers tell you which one is thinner. A small λ2 means a sparse cut relative to the sizes of the sides, which is exactly Cheeger's inequality from the Laplacian lesson.

More to try on your own

  1. Prove that any graph with n vertices and more than n²/4 edges contains a triangle (Mantel's theorem), then test it by brute force for n ≤ 7.
  2. Show that a tree has chromatic polynomial k(k−1)^(n−1) by checking all trees on 5 vertices with the deletion-contraction code.
  3. Use the flow construction to find the largest set of vertex-disjoint paths between two vertices (hint: split each vertex into in and out).
  4. Compute the stationary distribution of a random walk on the barbell graph and explain why the bridge endpoints have a larger share.
  5. Implement the Stoer-Wagner or Karger algorithm for the global minimum cut and compare it with Problem 4.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which test decides whether a list of integers is the degree sequence of a simple graph?

    Havel-Hakimi repeatedly removes the largest degree and decrements the next largest ones; it either reaches all zeros or fails.
  2. 2. Why can a checkerboard with two same-colored cells removed not be tiled with dominoes?

    Each domino covers exactly one cell of each color, so a tiling needs equal numbers of black and white cells.
  3. 3. How is the edge connectivity of a graph computed with max flow?

    Some minimum cut separates the fixed vertex from at least one other vertex, so the smallest of those flows is the edge connectivity.
  4. 4. What does the Grötzsch (Mycielski) graph show?

    Its clique number is 2 yet its chromatic number is 4, so clique size alone does not determine the chromatic number.

Summary

  • Recognize the classical problem behind a puzzle: bipartiteness, matching, min cut, coloring or spectral properties.
  • Havel-Hakimi decides graphical degree sequences; BFS 2-coloring finds odd conflict cycles.
  • Domino tilings are perfect matchings in bipartite grid graphs, and color balance is a necessary condition.
  • Edge connectivity is a minimum over max-flow computations.
  • Triangle-free graphs can need many colors (Mycielski), and planar triangle-free graphs obey E ≤ 2V − 4.
  • Laplacian eigenvalues count components and rank how hard a graph is to cut.

That finishes this part of the course. Return to the track overview to review other chapters.