Degree Sequences and Sorting Conventions

From Vertex Degrees to a Degree Sequence

A graph assigns a degree to each vertex, but listing those degrees in the order that vertices happen to be named is not a consistent way to summarize the graph. The degree sequence gives a standard order: arrange all vertex degrees from largest to smallest. This keeps the degree information while making the result independent of the names or order of the vertices.

All graphs in this tutorial are finite and simple: they have no loops or multiple edges. A graph \(G=(V,E)\) has vertex set \(V\) and edge set \(E\). The degree \(\deg(v)\) of a vertex \(v\) is the number of vertices adjacent to \(v\), or equivalently the number of edges incident with \(v\). A vertex with degree zero is isolated. When computing degrees from an edge list, the vertex set matters as well as the edges: a listed vertex incident with no edge still contributes a zero.

The notation \(d_1,\ldots,d_n\) here means the sorted degree values, not degrees attached to particular vertex names. If two or more vertices have the same degree, their relative order in the sorted list makes no difference. The sequence is a list, so repetitions are essential: the sequence \(3,2,2,1\) is not the same as the set \(\{1,2,3\}\).

A Reliable Method for an Edge List

For a graph given by vertices and edges, first make a degree count for every vertex. For each edge \(uv\), increase the count of \(u\) by one and the count of \(v\) by one. Since the graph is simple, each edge has two distinct endpoints and appears only once in the edge set. After processing all edges, check that every vertex in \(V\) has a count, including vertices whose count is zero. Finally, sort the counts from largest to smallest without deleting repeated values.

Repeated Values and Sorting Ties

Sorting a degree list changes its order, not its contents. If several vertices have equal degree, all those equal values remain in the sequence. There is no need to choose a special order among tied vertices, because the degree sequence does not record which vertex occupies a tied position. A useful working habit is to keep the vertex-by-vertex count beside the sorted list until the calculation has been checked.

What Sorting Guarantees

Proof. Let the degrees of the vertices, in any chosen vertex order, be \(x_1,\ldots,x_n\). Sorting this list in nonincreasing order places a largest value first, then a largest value among the remaining entries, and continues until every entry has a position. At each position the value is determined by the multiset of degrees: it is the largest value not already placed as many times as it occurs. Thus any two ways of listing the same vertex degrees produce the same sorted value in every position. The resulting sequence is unique. \(\square\)

This proposition explains why the labels do not appear in the final sequence. Changing the order in which vertices are written can change the unsorted list, but it cannot change the collection of degree values or their nonincreasing arrangement. The sequence records how many vertices have each degree, not which vertices have those degrees.

Proof. Before sorting, each vertex contributes exactly one value, namely its degree. Sorting only rearranges those values; it neither adds nor removes an entry. Therefore the number of entries equal to \(k\) is unchanged and equals the number of vertices whose degree is \(k\). A vertex has degree zero exactly when it has no incident edges, which is the definition of an isolated vertex. Applying the first statement with \(k=0\) proves the final claim. \(\square\)

The sequence always has \(n\) entries because each of the \(n\) vertices contributes one degree. This is a simple but important check: if the vertex set has six elements and the sorted list has only five entries, some vertex has been omitted. Often the missing value is a zero, because isolated vertices do not appear as endpoints in the edge list.

Worked Example: The Same Sequence Can Hide Different Edge Lists

A degree sequence summarizes degrees, but it does not specify which vertices are adjacent. The following two graphs illustrate this distinction. Let \(G_1=(V_1,E_1)\), where \(V_1=\{1,2,3,4,5,6\}\) and \(E_1=\{12,23,34,45,56,61\}\). Each vertex is incident with two listed edges: for example, vertex \(1\) has \(12,61\), and vertex \(4\) has \(34,45\). The same check for vertices \(2,3,5,6\) gives degree \(2\) for each. Thus the degree list is \(2,2,2,2,2,2\).

Now let \(G_2=(V_2,E_2)\), where \(V_2=\{a,b,c,d,e,f\}\) and \(E_2=\{ab,bc,ca,de,ef,fd\}\). Vertices \(a,b,c\) each have two incident edges: \(ab,ac\) at \(a\), \(ab,bc\) at \(b\), and \(bc,ca\) at \(c\). Vertices \(d,e,f\) also each have two: \(de,df\) at \(d\), \(de,ef\) at \(e\), and \(ef,fd\) at \(f\). Its degree sequence is also \(2,2,2,2,2,2\).

Check: Each graph has six vertices and every one of them has degree \(2\), so each sorted list has six entries, all equal to \(2\). Their edge lists differ, but the degree sequence records only the degrees, not the edge arrangement.

Common Mistakes and a Careful Check

Omitting isolated vertices. Suppose the graph in the first worked example is given with \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,ac,bc,bd,de\}\). A mistaken calculation might list only the degrees of vertices that appear in an edge and report \(3,2,2,2,1\). That list has five entries, even though the stated graph has six vertices. The correction is to include \(f\), whose degree is \(0\), giving \(3,2,2,2,1,0\).

Removing repeated values. A degree sequence is not a set of distinct degrees. In the second worked example, replacing \(3,3,2,2,2,1,1\) with \(3,2,1\) loses the information about how many vertices have each degree. Retain each vertex’s value once, then sort all the values.

Sorting in the wrong direction. The convention here is nonincreasing order: each term is at least the next. Thus \(3,2,2,1\) is correctly ordered, while \(1,2,2,3\) is the same collection of values in the opposite order, not the degree sequence under this convention.

When checking a calculation, ask three separate questions: did every vertex appear in the degree count; did every edge contribute to the count at both endpoints; and does the sorted list contain the same values, with the same repetitions, as the unsorted list? These checks catch most errors without requiring any further information about the graph.