Graph and tree mathematics

A graph G = (V, E) has a set of vertices (nodes) V and a set of edges E, each joining two vertices. Edges may be directed (arrows) or undirected, and weighted or unweighted. A simple graph has no self-loops and no repeated edges.

A simple undirected graph on n vertices has at most n(n - 1)/2 edges (every pair), and a simple directed graph at most n(n - 1).

The degree of a vertex is the number of edges touching it. In a directed graph it splits into in-degree and out-degree. A leaf has degree 1. Algorithms that visit all neighbours of every vertex take time proportional to the sum of the degrees.

In an adjacency list, the length of g.get(u) is the degree of u.

1int n = 4;
2int[] degree = new int[n];
3int[][] edges = {{0, 1}, {0, 2}, {0, 3}, {1, 2}};
4for (int[] e : edges) { degree[e[0]]++; degree[e[1]]++; }
5// degree = [3, 2, 2, 1]; sum = 8 = 2 * 4 edges

A walk is a sequence of vertices where consecutive ones are joined by an edge; vertices and edges may repeat. A trail repeats no edge; a path repeats no vertex. A path with k edges visits k + 1 vertices. Shortest-path algorithms minimise the number or total weight of edges.

In a graph with n vertices every simple path has at most n - 1 edges.

A cycle is a path that returns to its starting vertex without repeating other vertices (at least 3 vertices in an undirected simple graph). A graph without cycles is acyclic. A directed acyclic graph (DAG) can be topologically sorted, and a graph with a cycle cannot.

Cycle detection uses depth-first search or union-find; this matters for dependency resolution and deadlock detection.

An undirected graph is connected if a path joins every pair of vertices; otherwise it splits into connected components. A connected graph on n vertices needs at least n - 1 edges. Directed graphs have strongly connected components, in which every vertex reaches every other.

Counting components with BFS, DFS or union-find costs O(V + E).

1static int components(int n, List<List<Integer>> g) {
2    boolean[] seen = new boolean[n];
3    int count = 0;
4    for (int s = 0; s < n; s++) {
5        if (seen[s]) continue;
6        count++;
7        Deque<Integer> stack = new ArrayDeque<>(); stack.push(s); seen[s] = true;
8        while (!stack.isEmpty()) {
9            int u = stack.pop();
10            for (int v : g.get(u)) if (!seen[v]) { seen[v] = true; stack.push(v); }
11        }
12    }
13    return count;
14}

A tree is a connected acyclic graph. Choosing a root gives each other node exactly one parent, and nodes with no children are leaves. Depth is the number of edges from the root; height is the largest depth. A binary tree allows at most two children per node.

A binary tree of height h has at most 2ʰ⁺¹ - 1 nodes, so n nodes need height at least ⌊log₂ n⌋.

A tree with n vertices has exactly n - 1 edges. Reason: starting with n isolated vertices (n components), each edge added without making a cycle merges two components, so n - 1 edges are needed to reach one component, and any further edge creates a cycle.

Consequently a connected graph is a tree exactly when it has n - 1 edges. This gives a quick test for a spanning tree and the O(V) bound on tree traversals.

In any undirected graph the sum of all degrees is twice the number of edges, because each edge adds 1 to the degree of both its endpoints: Σ deg(v) = 2|E|. Therefore the number of vertices with odd degree is even.

Use it to check an adjacency list: if the lengths of all lists do not sum to an even number, an edge was recorded in only one direction.

1// adjacency list of an undirected graph
2long total = 0;
3for (List<Integer> nbrs : g) total += nbrs.size();
4long edges = total / 2;      // exact when every edge is stored in both directions