Vertex Degrees in Simple Graphs

What Degree Measures

In a graph, degree is a local measure: it records how many edges meet a particular vertex. Calculating it from an edge list is a basic skill used throughout graph theory. The important step is to fix one vertex and count only the edges incident with it; edges elsewhere in the graph do not contribute.

Throughout this tutorial, graphs are finite and simple. Thus an edge joins two distinct vertices, and there is at most one edge between any two vertices. Write \(G=(V,E)\), where \(V=V(G)\) is the vertex set and \(E=E(G)\) is the edge set. An edge joining \(u\) and \(v\) is written \(uv\). The degree counts edges, not vertices in the whole graph and not the number of edges in \(E\).

The equivalence in the definition depends on simplicity. Each edge incident with \(v\) has exactly one other endpoint, and distinct edges incident with \(v\) have distinct other endpoints. In particular, if no edge is incident with \(v\), then \(\deg(v)=0\); such a vertex is called isolated. A vertex of degree \(1\) is called a leaf or pendant vertex.

Counting from an Edge List

Suppose the graph is specified by its vertex set and edge set. To find \(\deg(v)\), scan the entire edge list and select the entries that contain \(v\) as an endpoint. Count each selected edge once. In the notation \(uv\), the order of the letters does not change the edge: \(uv\) and \(vu\) name the same undirected edge.

The check by neighborhoods is useful because it gives a second description of the same local information. It is not a different convention for degree: in a simple graph, each neighbor corresponds to exactly one incident edge. When working from an edge list, however, counting the edges directly is often the quickest method.

Why Degree Equals Neighborhood Size

Proof. Fix a vertex \(v\). For each edge incident with \(v\), take its endpoint other than \(v\). This endpoint exists and is unique because every edge in a simple graph joins two distinct vertices. It belongs to \(N(v)\). Conversely, for every vertex \(u\in N(v)\), the edge \(uv\) is incident with \(v\). These two assignments undo one another: the edge \(uv\) corresponds to the neighbor \(u\), and the neighbor \(u\) corresponds to the edge \(uv\). Therefore the incident edges at \(v\) and the vertices in \(N(v)\) are in one-to-one correspondence. Their numbers are equal, so \(\deg(v)=|N(v)|\). This also covers an isolated vertex: both sets are empty and both numbers are \(0\). \(\square\)

This last point matters whenever a graph is specified by both \(V\) and \(E\). A vertex can belong to \(V\) without appearing in any edge. Its degree is still defined, and is \(0\). An edge list alone may not make isolated vertices visible, so read the stated vertex set as well as the edge set.

How a Single Edge Changes Degrees

Degree calculations can also be updated when one edge is added or deleted. The rule concerns only the endpoints of that edge. For an addition, the proposed edge must not already be present, and its endpoints must be distinct; these conditions ensure that the resulting graph remains simple. For a deletion, the edge must be present.

Proof. First suppose \(uv\notin E(G)\). Adding \(uv\) introduces one new edge incident with \(u\) and one new edge incident with \(v\), so each of their incident-edge counts increases by exactly \(1\). Because \(u\ne v\), no other vertex is an endpoint of the new edge. Thus no other vertex's incident-edge count changes. Now suppose \(uv\in E(G)\) and delete it. The deleted edge was counted once in the degree of \(u\) and once in the degree of \(v\), so each of those counts decreases by exactly \(1\). No other vertex was an endpoint of \(uv\), so every other degree stays the same. \(\square\)

Common Mistake: Confusing Degree with Edge Count

A graph's size \(m=|E(G)|\) is the total number of edges in the graph. The degree \(\deg(v)\) is the number of those edges that meet a particular vertex \(v\). These are different quantities, so the total edge count is not automatically the degree of any vertex.

For example, in the graph with \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd\}\), there are three edges. The incorrect calculation “\(\deg(b)=3\), because the graph has three edges” counts every edge, including \(cd\), which does not meet \(b\). The correction is to select only \(ab\) and \(bc\), giving \(\deg(b)=2\). The neighborhood check gives \(N(b)=\{a,c\}\), again of size \(2\).

Another error is to forget a vertex that does not appear in any edge. In the worked example on six vertices, \(6\) is still a vertex and has degree \(0\). Always use the full vertex set when reporting which vertices have been assigned degrees.