32.05Intermediate / Advanced5 topics12 min5 interactive animations

Core graph properties

A few counting facts every graph algorithm relies on: the handshaking lemma, degree sums, the n - 1 edges of a tree, edge counts of directed graphs and the complement.

Learning goals

State and use the handshaking lemma
Compute edge-count limits for undirected and directed graphs
Use the n - 1 rule to test and bound trees and forests
Build the complement of a graph

Prerequisites

Graph taxonomyRepresentations

These facts are the sanity checks of graph work. If your degrees do not add up to twice the edges, your input is wrong; if a 'tree' has 12 edges on 10 vertices, it is not one. They also bound the running time of every traversal.

32.05.1

Handshaking lemma

The **handshaking lemma**: in any undirected graph the sum of all degrees equals twice the number of edges, because every edge has two ends and each end adds 1 to one degree. A consequence: the number of vertices with odd degree is always even. (At a party, the number of people who shook an odd number of hands is even.)

The preset "Undirected, five edges" prints Degrees [2, 2, 2, 3, 1]; they add up to 10 = 2 × 5. Use the lemma as a check on input: if the sum of degrees is odd, the edge list has an error. It also shows that the adjacency list of an undirected graph has exactly 2m entries.

Java

1static int oddDegreeVertices(int n, int[][] edges) {     // always even, by the handshaking lemma
2    int[] deg = new int[n];
3    for (int[] e : edges) { deg[e[0]]++; deg[e[1]]++; }
4    int odd = 0;
5    for (int d : deg) if (d % 2 == 1) odd++;
6    return odd;
7}

One graph, three representations: matrix, adjacency list, edge list

Interactive · edit the input

grid · 6 × 6

012345

Just addedChanged entryHeader

undirected graph · 5 vertices · 0 edges

Just addedChanged entryHeader

list[0]

empty

list[1]

empty

list[2]

empty

list[3]

empty

list[4]

empty

edge list (a-b, weight)

empty

Setup

An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.

Step 1 / 7

Java

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

Live state

0 edges added0 list entries

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.
2	L10	edge=0-1 matrix cells changed=2 list entries=2	Add the edge 0-1: both mirror cells [0][1] and [1][0], two list entries and one edge-list entry.
3	L10	edge=0-2 matrix cells changed=2 list entries=4	Add the edge 0-2: both mirror cells [0][2] and [2][0], two list entries and one edge-list entry.
4	L10	edge=1-3 matrix cells changed=2 list entries=6	Add the edge 1-3: both mirror cells [1][3] and [3][1], two list entries and one edge-list entry.
5	L10	edge=2-3 matrix cells changed=2 list entries=8	Add the edge 2-3: both mirror cells [2][3] and [3][2], two list entries and one edge-list entry.
6	L10	edge=3-4 matrix cells changed=2 list entries=10	Add the edge 3-4: both mirror cells [3][4] and [4][3], two list entries and one edge-list entry.
7	L13	return=[2, 2, 2, 3, 1] sum of degrees=10 edges=5	Degrees (row sums) [2, 2, 2, 3, 1]; they add up to 10 = 2 × 5: every edge has two ends (handshaking lemma).

32.05.2

Trees with n-1 edges

A tree on n vertices has exactly n - 1 edges. Proof sketch: start with n isolated vertices (n components) and add edges; each edge that joins two different components lowers the component count by one, and a tree is built from n - 1 such edges. If any edge joined two vertices already connected, it would close a cycle. A forest with c components has n - c edges, so edges = n - components characterises acyclic graphs, and any extra edge creates a cycle.

The preset "n - 1 edges but disconnected" (0-1 1-2 2-0 3-4 on 5 vertices) has exactly n - 1 = 4 edges but is not a tree: the triangle uses 3 edges for 3 vertices (one too many) and the vertices 3 and 4 are cut off. Both conditions, connected and acyclic, are needed.

Java

1static boolean isForest(int n, int[][] edges) {          // undirected: acyclic exactly when edges == n - components
2    int[] parent = new int[n];
3    for (int i = 0; i < n; i++) parent[i] = i;
4    int comps = n;
5    for (int[] e : edges) {
6        int a = e[0], b = e[1];
7        while (parent[a] != a) a = parent[a];
8        while (parent[b] != b) b = parent[b];
9        if (a != b) { parent[a] = b; comps--; }
10    }
11    return edges.length == n - comps;
12}

Graph complement, edge reversal and the tree test

Interactive · edit the input

undirected graph · 5 vertices · 4 edges

New edgeOriginal edgeBeing examinedNot a tree edge

Setup

The complement has the same vertices and exactly the pairs that are NOT edges. A simple graph on 5 vertices has n(n-1)/2 = 10 possible edges; 4 are present, so the complement will have 6.

Step 1 / 12

Java

1boolean[][] complement(boolean[][] adj) {        // simple undirected graph
2    int n = adj.length;
3    boolean[][] c = new boolean[n][n];
4    for (int i = 0; i < n; i++)
5        for (int j = 0; j < n; j++)
6            if (i != j) c[i][j] = !adj[i][j];    // an edge is present exactly when it was absent
7    return c;
8}
9List<List<Integer>> reverse(List<List<Integer>> g) {     // directed: flip every edge
10    List<List<Integer>> r = new ArrayList<>();
11    for (int i = 0; i < g.size(); i++) r.add(new ArrayList<>());
12    for (int u = 0; u < g.size(); u++)
13        for (int v : g.get(u)) r.get(v).add(u);          // u -> v becomes v -> u
14    return r;
15}
16boolean isTree(int n, int[][] edges) {           // n - 1 edges and connected (no cycle then follows)
17    if (edges.length != n - 1) return false;
18    DSU d = new DSU(n);
19    for (int[] e : edges) if (!d.union(e[0], e[1])) return false;    // an edge inside one set would close a cycle
20    return true;
21}

Live state

0 edges

edges

possible edges

No condition evaluated on this step

Execution trace (dry run table)Show 12 steps

Step	Line	State	What happens
1	L1	edges=4 possible edges=10	The complement has the same vertices and exactly the pairs that are NOT edges. A simple graph on 5 vertices has n(n-1)/2 = 10 possible edges; 4 are present, so the complement will have 6.
2	L6	pair=0-1 present=true complement edges=0	0-1 is an edge of the graph, so it is missing from the complement.
3	L6	pair=0-2 present=false complement edges=1	0-2 is not an edge, so it becomes an edge of the complement.
4	L6	pair=0-3 present=false complement edges=2	0-3 is not an edge, so it becomes an edge of the complement.
5	L6	pair=0-4 present=false complement edges=3	0-4 is not an edge, so it becomes an edge of the complement.
6	L6	pair=1-2 present=true complement edges=3	1-2 is an edge of the graph, so it is missing from the complement.
7	L6	pair=1-3 present=false complement edges=4	1-3 is not an edge, so it becomes an edge of the complement.
8	L6	pair=1-4 present=false complement edges=5	1-4 is not an edge, so it becomes an edge of the complement.
9	L6	pair=2-3 present=true complement edges=5	2-3 is an edge of the graph, so it is missing from the complement.
10	L6	pair=2-4 present=false complement edges=6	2-4 is not an edge, so it becomes an edge of the complement.
11	L6	pair=3-4 present=true complement edges=6	3-4 is an edge of the graph, so it is missing from the complement.
12	L7	return=6 graph + complement=10	The complement has 6 edges, and 4 + 6 = 10: together they make the complete graph.

32.05.3

Sum degrees

Degree sums bound everything. In an undirected graph the sum of degrees is 2m; in a directed graph the sum of out-degrees equals the sum of in-degrees equals m. A traversal that looks at every neighbour of every vertex therefore does 2m (or m) steps in total, plus n for the vertices: that is where the O(V + E) of breadth-first and depth-first search comes from.

A degree sequence also limits what is possible: a vertex of a simple graph on n vertices has degree at most n - 1. The code below returns the degree sequence in decreasing order together with its sum, as a quick way to inspect a graph.

Java

1static long degreeSum(int n, int[][] edges) {    // equals 2 * edges.length for any undirected graph
2    long sum = 0;
3    for (int d : degreeSequence(n, edges)) sum += d;
4    return sum;
5}
6static int[] degreeSequence(int n, int[][] edges) {      // sorted from largest to smallest
7    int[] deg = new int[n];
8    for (int[] e : edges) { deg[e[0]]++; deg[e[1]]++; }
9    Arrays.sort(deg);
10    for (int i = 0, j = n - 1; i < j; i++, j--) { int t = deg[i]; deg[i] = deg[j]; deg[j] = t; }
11    return deg;
12}

One graph, three representations: matrix, adjacency list, edge list

Interactive · edit the input

grid · 6 × 6

012345

Just addedChanged entryHeader

undirected graph · 5 vertices · 0 edges

Just addedChanged entryHeader

list[0]

empty

list[1]

empty

list[2]

empty

list[3]

empty

list[4]

empty

edge list (a-b, weight)

empty

Setup

Step 1 / 7

Java

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

Live state

0 edges added0 list entries

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.
2	L10	edge=0-1 matrix cells changed=2 list entries=2	Add the edge 0-1: both mirror cells [0][1] and [1][0], two list entries and one edge-list entry.
3	L10	edge=0-2 matrix cells changed=2 list entries=4	Add the edge 0-2: both mirror cells [0][2] and [2][0], two list entries and one edge-list entry.
4	L10	edge=1-3 matrix cells changed=2 list entries=6	Add the edge 1-3: both mirror cells [1][3] and [3][1], two list entries and one edge-list entry.
5	L10	edge=2-3 matrix cells changed=2 list entries=8	Add the edge 2-3: both mirror cells [2][3] and [3][2], two list entries and one edge-list entry.
6	L10	edge=3-4 matrix cells changed=2 list entries=10	Add the edge 3-4: both mirror cells [3][4] and [4][3], two list entries and one edge-list entry.
7	L13	return=[2, 2, 2, 3, 1] sum of degrees=10 edges=5	Degrees (row sums) [2, 2, 2, 3, 1]; they add up to 10 = 2 × 5: every edge has two ends (handshaking lemma).

32.05.4

Directed edge counts

A simple directed graph on n vertices has at most n(n - 1) arrows: each ordered pair of different vertices can carry one arrow, twice as many as the undirected n(n - 1) / 2. Allowing self-loops adds n more, so n² in all, which is the number of cells of the adjacency matrix. The out-degrees sum to the number of arrows and so do the in-degrees.

In the preset "Directed: rows are out-edges" both degree sums are 5, the number of arrows. These bounds tell you when the quadratic matrix is justified: a graph with n = 10^5 vertices could have 10^10 arrows, far more than memory allows, so real inputs with that many vertices are sparse.

Java

1static long maxEdges(long n, boolean directed, boolean allowLoops) {
2    long pairs = directed ? n * (n - 1) : n * (n - 1) / 2;
3    return allowLoops ? pairs + n : pairs;      // one extra loop per vertex
4}

One graph, three representations: matrix, adjacency list, edge list

Interactive · edit the input

grid · 6 × 6

012345

Just addedChanged entryHeader

undirected graph · 5 vertices · 0 edges

Just addedChanged entryHeader

list[0]

empty

list[1]

empty

list[2]

empty

list[3]

empty

list[4]

empty

edge list (a-b, weight)

empty

Setup

Step 1 / 7

Java

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

Live state

0 edges added0 list entries

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.
2	L10	edge=0-1 matrix cells changed=2 list entries=2	Add the edge 0-1: both mirror cells [0][1] and [1][0], two list entries and one edge-list entry.
3	L10	edge=0-2 matrix cells changed=2 list entries=4	Add the edge 0-2: both mirror cells [0][2] and [2][0], two list entries and one edge-list entry.
4	L10	edge=1-3 matrix cells changed=2 list entries=6	Add the edge 1-3: both mirror cells [1][3] and [3][1], two list entries and one edge-list entry.
5	L10	edge=2-3 matrix cells changed=2 list entries=8	Add the edge 2-3: both mirror cells [2][3] and [3][2], two list entries and one edge-list entry.
6	L10	edge=3-4 matrix cells changed=2 list entries=10	Add the edge 3-4: both mirror cells [3][4] and [4][3], two list entries and one edge-list entry.
7	L13	return=[2, 2, 2, 3, 1] sum of degrees=10 edges=5	Degrees (row sums) [2, 2, 2, 3, 1]; they add up to 10 = 2 × 5: every edge has two ends (handshaking lemma).

32.05.5

Graph complement

The **complement** of a simple graph has the same vertices and exactly the edges that are missing from the original. The graph and its complement together make the complete graph, so their edge counts add up to n(n - 1) / 2. A set of vertices that is independent (no edges) in a graph is a clique (all edges) in its complement, which links clique and independent-set problems.

In the preset "Complement of a path" the path 0-1-2-3-4 has 4 edges, its complement has 6, and 4 + 6 = 10 = 5 × 4 / 2. The animation tests all 10 pairs in turn. Building the complement of a large sparse graph is a bad idea: it is dense and has about n² edges.

Java

1static List<int[]> complement(int n, int[][] edges) {    // simple undirected graph
2    boolean[][] has = new boolean[n][n];
3    for (int[] e : edges) has[e[0]][e[1]] = has[e[1]][e[0]] = true;
4    List<int[]> out = new ArrayList<>();
5    for (int a = 0; a < n; a++)
6        for (int b = a + 1; b < n; b++)
7            if (!has[a][b]) out.add(new int[]{a, b});         // present exactly when it was absent
8    return out;
9}

Graph complement, edge reversal and the tree test

Interactive · edit the input

undirected graph · 5 vertices · 4 edges

New edgeOriginal edgeBeing examinedNot a tree edge

Setup

The complement has the same vertices and exactly the pairs that are NOT edges. A simple graph on 5 vertices has n(n-1)/2 = 10 possible edges; 4 are present, so the complement will have 6.

Step 1 / 12

Java

1boolean[][] complement(boolean[][] adj) {        // simple undirected graph
2    int n = adj.length;
3    boolean[][] c = new boolean[n][n];
4    for (int i = 0; i < n; i++)
5        for (int j = 0; j < n; j++)
6            if (i != j) c[i][j] = !adj[i][j];    // an edge is present exactly when it was absent
7    return c;
8}
9List<List<Integer>> reverse(List<List<Integer>> g) {     // directed: flip every edge
10    List<List<Integer>> r = new ArrayList<>();
11    for (int i = 0; i < g.size(); i++) r.add(new ArrayList<>());
12    for (int u = 0; u < g.size(); u++)
13        for (int v : g.get(u)) r.get(v).add(u);          // u -> v becomes v -> u
14    return r;
15}
16boolean isTree(int n, int[][] edges) {           // n - 1 edges and connected (no cycle then follows)
17    if (edges.length != n - 1) return false;
18    DSU d = new DSU(n);
19    for (int[] e : edges) if (!d.union(e[0], e[1])) return false;    // an edge inside one set would close a cycle
20    return true;
21}

Live state

0 edges

edges

possible edges

No condition evaluated on this step

Execution trace (dry run table)Show 12 steps

Step	Line	State	What happens
1	L1	edges=4 possible edges=10	The complement has the same vertices and exactly the pairs that are NOT edges. A simple graph on 5 vertices has n(n-1)/2 = 10 possible edges; 4 are present, so the complement will have 6.
2	L6	pair=0-1 present=true complement edges=0	0-1 is an edge of the graph, so it is missing from the complement.
3	L6	pair=0-2 present=false complement edges=1	0-2 is not an edge, so it becomes an edge of the complement.
4	L6	pair=0-3 present=false complement edges=2	0-3 is not an edge, so it becomes an edge of the complement.
5	L6	pair=0-4 present=false complement edges=3	0-4 is not an edge, so it becomes an edge of the complement.
6	L6	pair=1-2 present=true complement edges=3	1-2 is an edge of the graph, so it is missing from the complement.
7	L6	pair=1-3 present=false complement edges=4	1-3 is not an edge, so it becomes an edge of the complement.
8	L6	pair=1-4 present=false complement edges=5	1-4 is not an edge, so it becomes an edge of the complement.
9	L6	pair=2-3 present=true complement edges=5	2-3 is an edge of the graph, so it is missing from the complement.
10	L6	pair=2-4 present=false complement edges=6	2-4 is not an edge, so it becomes an edge of the complement.
11	L6	pair=3-4 present=true complement edges=6	3-4 is an edge of the graph, so it is missing from the complement.
12	L7	return=6 graph + complement=10	The complement has 6 edges, and 4 + 6 = 10: together they make the complete graph.

Practice ladder

Now try it yourself

Easy

Find the Town Judge

Medium

Graph Valid Tree
Number of Connected Components in an Undirected Graph

Advanced

Minimum Number of Days to Disconnect Island
Count Unreachable Pairs of Nodes in an Undirected Graph

Key takeaways

Sum of degrees = 2 × edges, so the number of odd-degree vertices is even.
A tree has n - 1 edges; a forest has n - components; one more edge makes a cycle.
Directed graphs have up to n(n - 1) arrows; a graph and its complement make the complete graph.