Skip to content
Tutorials Center
My learning

Topics

Lesson 126 of 225 ยท Graphs

Graph Oddities: Universal Sink, Degree Sequences, Petersen, Random Graphs

Learn five classic graph topics in Python: the O(V) universal sink search, Havel-Hakimi degree sequences, the Petersen graph, Erdos-Renyi random graphs and offline dynamic connectivity.

Every graph course has a handful of results that do not fit under "traversal", "shortest path" or "spanning tree", yet they keep coming back in interviews, contests and textbooks. This lesson gathers five of them. Each one teaches a different way of thinking: reading a matrix cleverly, testing whether a graph can exist, checking properties of one famous example, understanding what random graphs look like, and answering connectivity questions while edges come and go.

You should be comfortable with graph representations, BFS and union-find.

1. The universal sink in O(V)

In a directed graph, a universal sink is a vertex that every other vertex points to, and that points to nothing. With an adjacency matrix, matrix[i][j] = 1 means an edge i -> j, so a sink s has an all-zero row s and a column s that is 1 everywhere except the diagonal.

Checking every vertex costs O(V^2), which is the size of the matrix. Surprisingly, O(V) is enough, because each look at one cell eliminates one candidate. Keep a candidate c, starting at 0, and examine matrix[c][j] for j = 1, 2, ...:

  • If matrix[c][j] = 1, then c has an out-edge, so c cannot be a sink. Make j the new candidate (everything between was already ruled out).
  • If it is 0, then c does not point to j, so j cannot be a universal sink (a sink needs an edge from everyone). Keep c.

After one pass only one candidate is left, and we verify it with one row and column check, O(V) more.

Python Universal sink with one pass

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 first call finds vertex 2. After adding the edge 2 -> 0 the candidate no longer has an empty row, so the answer becomes -1. A graph has at most one universal sink: if two existed, each would have to point at the other, contradicting "points to nothing".

2. Degree sequences and Havel-Hakimi

A degree sequence lists the degree of every vertex, such as [3, 3, 2, 2, 2]. A sequence is graphical if some simple undirected graph (no loops, no repeated edges) realizes it. Two quick necessary checks: the sum must be even (every edge adds 2), and no degree may be larger than n - 1. They are not sufficient: [3, 3, 3, 1] passes both and still fails.

The Havel-Hakimi algorithm decides exactly:

  1. Sort the sequence in non-increasing order and remove the first value d.
  2. Subtract 1 from the next d values. If there are fewer than d values left, or a value drops below 0, the sequence is not graphical.
  3. Repeat. If all values become 0, it is graphical.

The idea: the vertex with the largest degree can always be wired to the next-largest d vertices without losing any realizable graph, so we reduce the problem to a smaller sequence.

Python Havel-Hakimi test

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.

[4, 3, 3, 2, 2, 1] fails the parity test (its sum is 15), [3, 3, 3, 1] fails inside the algorithm, and [5, 1, 1, 1, 1, 1] is a star: one centre joined to five leaves. The trace for [3, 3, 2, 2, 2] shows the reduction: wire the first 3 to the next three vertices, then a 2, then a 1. Recording which vertices you connected at each step turns this test into a constructor that builds an actual graph.

3. The Petersen graph

The Petersen graph has 10 vertices and 15 edges: an outer 5-cycle, an inner pentagram (a 5-point star, which is a 5-cycle with step 2) and five spokes joining them. It is the standard counterexample for graph theory conjectures because it is so symmetric yet so unusual. We can verify its famous properties with the tools you already have.

Python Checking the Petersen graph's properties

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 output reads like a list of surprises. Every vertex has degree 3 (a 3-regular graph), the diameter is only 2 (any two vertices are at most two edges apart), and the girth is 5 (no triangles and no 4-cycles). It has a Hamiltonian path but no Hamiltonian cycle, even though it is so well connected; it needs 3 colours; and it has 120 automorphisms, so it looks the same from many angles. These facts make it the usual test case for the Hamiltonian cycle and colouring ideas.

4. Random graphs: Erdos-Renyi

How does a typical graph behave? In the Erdos-Renyi model G(n, p) you start with n vertices and include each of the n(n-1)/2 possible edges independently with probability p. Remarkably, properties flip suddenly at thresholds:

  • When p is around 1/n (average degree about 1), a giant component containing a constant fraction of all vertices appears.
  • Once p exceeds about ln(n) / n, the graph becomes connected with high probability.
Python Watching the giant component appear

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.

With average degree 0.5 the largest piece has only about 8 vertices; near average degree 1 it is still small (about 31); at 1.5 it jumps to more than half of the graph (about 109), and at 3 nearly everything is in one piece (about 189). Only at c = 6, above ln 200 = 5.3, is the graph usually connected (13 of 20 samples). Real networks behave in similar ways, which is why random graphs are used as a baseline for social and communication networks.

5. Offline dynamic connectivity

Suppose edges are added and deleted over time and you are asked "are u and v connected right now?" Union-find handles insertions only; deletions break it. If all events are known in advance (offline), there is an elegant trick:

  1. Every edge is alive during a time interval. Insert that interval into a segment tree over time, so the edge is stored in O(log T) nodes.
  2. Walk the tree depth first. On entering a node, union all edges stored there; at a leaf, answer the query for that time; on leaving, roll back those unions.

Rollback needs a union-find without path compression (use union by size), so each union can be undone by restoring one parent link. Every edge is unioned O(log T) times at O(log n) each.

Python Offline dynamic connectivity with rollback union-find

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.

Read the answers against the events: after adding 0-1 and 1-2, vertices 0 and 2 are connected (time 2); once 1-2 is deleted they are not (time 4); later the new edges 2-3 and 0-3 reconnect 1 and 2 through 0 and 3 (time 7), until 0-1 goes away (time 9) and 0 and 2 stay connected through 3 (time 10). The random test confirms the method against a naive rebuild at every query. For online dynamic connectivity (answers needed before future events are known), much heavier structures such as link-cut trees or Holm-de Lichtenberg-Thorup are needed.

Common mistakes

  • Scanning the whole matrix for a sink. The one-pass candidate method is the point; the check afterward is only one row and one column.
  • Using only the parity test for degree sequences. [3, 3, 3, 1] has an even sum and is still impossible.
  • Compressing paths in the rollback union-find. Path compression changes many parents at once and cannot be undone cheaply.
  • Closing intervals one step off. An edge deleted at time t is alive up to t - 1.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the O(V) universal sink search, what does a 1 at matrix[c][j] tell you?

    A sink has no outgoing edges. If c points to j, c is eliminated and j takes over as the candidate.
  2. 2. Which degree sequence passes the even-sum test but is NOT graphical?

    Havel-Hakimi removes a 3 and leaves [2, 2, 0], then removes a 2 and leaves [1, -1], which has a negative degree.
  3. 3. Which statement about the Petersen graph is true?

    The Petersen graph has girth 5 and needs 3 colours; despite its symmetry it has no Hamiltonian cycle, only a Hamiltonian path.
  4. 4. Why must the union-find used for offline dynamic connectivity avoid path compression?

    Rolling back a union must restore exactly the state before it; with union by size only one parent link and one size changed.

Summary

  • A universal sink can be found in O(V) from an adjacency matrix by eliminating one candidate per cell.
  • Havel-Hakimi decides whether a degree sequence is realizable as a simple graph.
  • The Petersen graph is 3-regular, has diameter 2, girth 5, no Hamiltonian cycle and 120 automorphisms.
  • In G(n, p), a giant component appears near p = 1/n and the graph becomes connected near p = ln(n)/n.
  • Offline dynamic connectivity uses a segment tree over time and a rollback union-find.

Next: Karger's Algorithm and Global Minimum Cut.