Degree Bounds in Simple Graphs

Why Degree Bounds Come First

A degree list records how many neighbors each vertex has. Before asking whether a list can come from a graph, there is a quick first test: in a simple graph, a vertex cannot be adjacent to itself, and it cannot be joined to the same other vertex more than once. Thus the number of its neighbors is limited by the number of other vertices. This elementary restriction is useful because it can rule out a proposed list immediately, and equality at either end of the range has a precise structural meaning.

Throughout, graphs are finite and simple: they have no loops and no multiple edges. The order of $G=(V,E)$ is $n=|V|$. The degree $d(v)=\deg(v)$ of a vertex $v$ is the number of vertices adjacent to it; its neighborhood $N(v)$ is the set of those vertices. A degree list for a graph of order $n$ has one degree for each of its $n$ vertices. A list is realizable if some simple graph has exactly those degrees.

The Bounds and What Equality Means

Theorem: If $G$ is a simple graph of order $n\geq 1$, then every vertex $v\in V(G)$ satisfies $$ 0\leq d(v)\leq n-1. $$ Moreover, $d(v)=0$ exactly when $v$ is isolated, and $d(v)=n-1$ exactly when $v$ is adjacent to every other vertex.

Proof. The degree $d(v)$ is the size of the neighborhood $N(v)$, so it cannot be negative. Since the graph has no loops, $v\notin N(v)$; every possible neighbor of $v$ therefore belongs to $V(G)\setminus\{v\}$, a set of size $n-1$. Hence $N(v)\subseteq V(G)\setminus\{v\}$, giving $d(v)=|N(v)|\leq n-1$. The equality $d(v)=0$ means $N(v)=\varnothing$, which is exactly the definition of an isolated vertex. If $d(v)=n-1$, then $N(v)$ is a subset of $V(G)\setminus\{v\}$ with the same finite size, so it equals that whole set: $v$ is adjacent to every other vertex. Conversely, adjacency to every other vertex gives $n-1$ neighbors and degree $n-1$. $\square$

A vertex adjacent to every other vertex is called universal. The theorem describes the equality cases vertex by vertex: degree zero means isolated, while degree $n-1$ means universal. In a one-vertex graph, these descriptions coincide: its sole vertex is both isolated and universal, since there are no other vertices.

Corollary: For a simple graph of order $n\geq1$, every degree lies in the integer range from $0$ to $n-1$. If every vertex has degree $0$, the graph has no edges. If every vertex has degree $n-1$, the graph is complete.

Proof. The degree bounds follow by applying the theorem to each vertex. If every degree is zero, no vertex is incident with an edge; since every edge has endpoints, there can be no edges. If every vertex has degree $n-1$, each vertex is adjacent to every other vertex. Thus every pair of distinct vertices is an edge, which is the definition of a complete graph. Conversely, a graph with no edges has degree zero at every vertex, and in a complete graph every vertex is adjacent to all $n-1$ other vertices. $\square$

For $n\geq1$, write $\delta(G)$ for the minimum degree and $\Delta(G)$ for the maximum degree. The vertex bounds imply $0\leq\delta(G)\leq\Delta(G)\leq n-1$. In particular, $\delta(G)=n-1$ forces every vertex to have degree $n-1$, so $G$ is complete; and $\Delta(G)=0$ forces every vertex to have degree zero, so $G$ has no edges. The other endpoint conditions have a different interpretation: $\delta(G)=0$ means at least one vertex is isolated, and $\Delta(G)=n-1$ means at least one vertex is universal.

Using the Bounds on Degree Lists

A degree list proposed for a graph of order $n$ must have exactly $n$ entries, and each entry must be an integer between $0$ and $n-1$, inclusive. These are necessary conditions: every realizable list satisfies them. Passing this test does not by itself prove that a list is realizable. The bounds are a first filter, not a complete characterization of degree lists.

Worked Example: Rejecting a List Outside the Range

Could the list $5,4,2,1,0$ be the degree list of a simple graph of order $5$?

The list has five entries, so the proposed graph would have $n=5$ vertices. The upper bound for each degree is therefore $n-1=5-1=4$, and the lower bound is $0$. The entries $4,2,1,0$ are within the interval from $0$ to $4$, but the entry $5$ is not: $5>4$. A vertex of degree $5$ would need five distinct neighbors, while only four other vertices are available.

Check: the largest possible degree is $n-1=5-1=4$. Since the proposed list contains $5$, it cannot be realized by a simple graph of order $5$.

Worked Example: A Vertex Attaining the Upper Bound

Let $G$ have vertex set $V=\{1,2,3,4\}$ and edge set $E=\{12,13,14,23\}$. Find its degrees and identify any universal vertex.

The order is $n=4$, so each degree must be between $0$ and $n-1=4-1=3$. Vertex $1$ is incident with the edges $12,13,14$, so $d(1)=3$. Vertex $2$ is incident with $12,23$, so $d(2)=2$. Vertex $3$ is incident with $13,23$, so $d(3)=2$. Vertex $4$ is incident with $14$, so $d(4)=1$. Thus the degrees are $3,2,2,1$, all within the required range. Since $d(1)=3=n-1$, vertex $1$ is universal; indeed, its neighbors are exactly the other vertices $\{2,3,4\}$.

Check: counting incidences at the four vertices gives $3+2+2+1=8$. The listed four edges each have two endpoints, giving $2\cdot4=8$ incidences as well. Also, the edge list contains $12,13,14$, exactly the three edges from vertex $1$ to the other vertices.

Worked Example: The All-Zero Degree List

Consider the graph with $V=\{a,b,c,d\}$ and $E=\varnothing$. What are its degrees, and what equality case does it illustrate?

Here $n=4$, so the degree range is from $0$ to $n-1=4-1=3$. Each vertex has no incident edges: $d(a)=0$, $d(b)=0$, $d(c)=0$, and $d(d)=0$. All four degrees attain the lower bound. Each vertex is isolated, and the graph has no edges.

Check: the edge set is empty, so every vertex has zero incident edges. Conversely, because every vertex has degree zero, no edge can be present: any edge would give each of its endpoints degree at least $1$. Thus the all-zero list agrees with the graph having no edges.

Why Passing the Bounds Is Not Enough

The bounds examine one degree at a time. Realizability asks whether all the requested degrees can be achieved together using the same set of edges. Those requirements can conflict, even when every entry lies in the permitted interval. Recognizing this distinction prevents a common overclaim: “all degrees are at most $n-1$” is a necessary test, not a guarantee that a graph exists.

Worked Example: A List Within the Bounds That Is Impossible

Could $3,3,0,0$ be the degree list of a simple graph of order $4$?

The list has $n=4$ entries, and the permitted range is $0$ through $n-1=4-1=3$. Each entry passes the individual bounds. Suppose a graph with this list existed. A vertex of degree $3$ in a graph on four vertices must be adjacent to all three other vertices. In particular, each vertex assigned degree $3$ would have to be adjacent to each of the two vertices assigned degree $0$. But a degree-zero vertex has no incident edges, so it cannot be adjacent to either of them. This is a contradiction; the list is not realizable.

Check: the upper bound test alone accepts both entries equal to $3$, because $3\leq4-1=3$, and both entries equal to $0$, because $0\geq0$. The contradiction comes from trying to satisfy all four degrees simultaneously, not from either individual bound.

Small Orders and Common Pitfalls

The theorem assumes $n\geq1$ because it discusses the degree of a vertex. If $n=0$, the graph has no vertices, so there is no vertex degree to test; the statement “every vertex satisfies the bounds” is vacuously true, but the numerical interval from $0$ to $n-1$ should not be applied to a nonexistent vertex. For $n=1$, the only possible simple graph has one vertex and no edges. Its degree is $0$, which is both the lower bound and $n-1=1-1=0$.

When using the bounds, first determine the graph order from the number of entries, then compute $n-1$, and compare every entry with the inclusive interval from $0$ to $n-1$. Do not mistake the order $n$ for the maximum degree: a vertex cannot be adjacent to itself. Also do not conclude that a list is realizable merely because it passes the bounds. The list $3,3,0,0$ shows that individually permitted values can still be mutually incompatible.

Equality is informative, but its meaning depends on whether it occurs at one vertex or at every vertex. One vertex of degree $0$ is isolated; all vertices of degree $0$ means there are no edges. One vertex of degree $n-1$ is universal; every vertex of degree $n-1$ means the graph is complete. Keeping these cases separate makes the equality conditions precise, including for $n=1$.

Check Your Understanding

For each question, use the order of the graph and the equality cases carefully.

Can $4,2,1,0$ be the degree list of a simple graph of order $4$? Explain using the bounds.
In a simple graph of order $6$, what does a vertex of degree $5$ have to be adjacent to?
Prove that if a simple graph of order $n\geq1$ has $\delta(G)=n-1$, then it is complete.
Give the degree list of a simple graph of order $5$ with no edges, and state which equality case each vertex attains.
Explain why the list $2,2,0,0$ passes the individual bounds for order $4$, but cannot be realized.

What You'll Learn