Counting Edge Ends at a Vertex
In a simple graph, an edge joins two distinct vertices and there is at most one edge between any pair. In a multigraph, parallel edges and loops are allowed, so the degree count must keep track of edge instances rather than only which vertices are adjacent. Parallel edges contribute separately. A loop contributes two because it has two ends at the same vertex.
Throughout, a multigraph is finite. To make parallel edges explicit, we give each edge instance a distinct label and specify its endpoints. Thus two labels may have the same pair of endpoints. A loop has the same vertex at both endpoints. The order of a multigraph is \(n=|V|\), and its size \(m=|E|\) counts edge instances, including loops and parallel edges.
This definition handles common cases consistently. A vertex joined to another vertex by three parallel edges receives three degree contributions from those edges. A vertex with one loop and no other incident edges has degree \(2\). An isolated vertex, with no incident edges, has degree \(0\).
For a compact calculation, let \(m_{uv}\) be the number of edge instances joining distinct vertices \(u\) and \(v\), and let \(\ell_v\) be the number of loops at \(v\). Then
The sum counts every non-loop edge at \(v\) once, according to its other endpoint. The final term counts both ends of every loop at \(v\). This formula is especially useful when an edge list contains several parallel edges.
Why the Total Degree Is Twice the Number of Edges
Proof. Consider the total degree by counting edge ends rather than first grouping them by vertex. Every edge instance has exactly two ends. If its endpoints are distinct, it contributes one end to the degree of each endpoint, for a total contribution of \(2\). If it is a loop, both ends are at the same vertex, and the loop contributes \(2\) to that vertex's degree, again a total of \(2\). Since there are \(m\) edge instances, all edge ends together contribute \(2m\). Grouping those same ends by their vertices gives \(\sum_{v\in V}\deg(v)\), so the two totals are equal. This also holds when \(E\) is empty: both sides are \(0\). \(\square\)
This identity is a useful arithmetic check, but it does not replace calculating each vertex degree from its incident edge instances. Two incorrect individual degrees can sometimes still have the right total. Check the local counts first, then use the total to catch errors in the full list.
Worked Example: Parallel Edges and Loops Together
Let \(V=\{a,b,c,d\}\), with edge instances \(e_1:ab\), \(e_2:ab\), \(e_3:bc\), \(e_4:cc\), \(e_5:cd\), and \(e_6:dd\). Thus \(e_1,e_2\) are parallel edges, while \(e_4\) and \(e_6\) are loops.
Count the contributions at each vertex. Vertex \(a\) is incident with \(e_1,e_2\), so \(\deg(a)=1+1=2\). Vertex \(b\) is incident with \(e_1,e_2,e_3\), so \(\deg(b)=1+1+1=3\). Vertex \(c\) is incident with \(e_3,e_5\) and the loop \(e_4\), so \(\deg(c)=1+1+2=4\). Vertex \(d\) is incident with \(e_5\) and the loop \(e_6\), so \(\deg(d)=1+2=3\).
Check: Adding the calculated degrees gives \(2+3+4+3=12\). There are \(6\) edge instances, so counting two ends per edge gives \(2\cdot6=12\). The totals agree.
Applying the Formula and Handling Special Cases
The multiplicity formula separates two sources of contribution: edges to other vertices and loops at the vertex itself. The number of neighbors alone is not enough to determine degree in a multigraph. For example, two vertices can have the same set of neighbors but different degrees if one pair is joined by more parallel edges, or if one vertex has loops.
Worked Example: An Isolated Vertex and a Loop-Only Vertex
Let \(V=\{u,v,w,x\}\), with edge instances \(f_1:uu\), \(f_2:uv\), \(f_3:uv\), \(f_4:ww\), and \(f_5:vw\). The two edges \(f_2,f_3\) are parallel, \(f_1,f_4\) are loops, and \(x\) is isolated.
At \(u\), the two \(uv\) edges contribute \(1+1\), and the loop \(f_1\) contributes \(2\). Hence \(\deg(u)=1+1+2=4\). At \(v\), the two \(uv\) edges and the edge \(f_5\) each contribute one, so \(\deg(v)=1+1+1=3\). At \(w\), the loop contributes \(2\) and \(f_5\) contributes \(1\), so \(\deg(w)=2+1=3\). No edge is incident with \(x\), so \(\deg(x)=0\).
Check: The degree total is \(4+3+3+0=10\). There are \(5\) edge instances, giving \(2\cdot5=10\) edge ends. In particular, the isolated vertex contributes nothing to the total, but it remains a vertex of the graph.
A systematic procedure helps avoid missing an edge or miscounting a loop:
Keep parallel edges separate by their labels; do not replace them with a single adjacency entry.
Add one for each incident non-loop edge instance, and add two for each loop.
Each such vertex has degree zero.
Add all degrees and compare with twice the number of edge instances, including loops and parallel edges.
The order matters in the check: \(m\) counts edge instances, not distinct endpoint pairs. If there are four parallel edges between two vertices, they count as four toward \(m\). A loop also counts as one edge instance toward \(m\), even though it contributes two to its vertex's degree.
Worked Example: Degrees from Multiplicities
Let \(V=\{1,2,3,4,5\}\). The edge instances are \(g_1:12\), \(g_2:23\), \(g_3:23\), \(g_4:34\), \(g_5:44\), \(g_6:45\), and \(g_7:15\). The two edges between \(2\) and \(3\) are parallel, and \(g_5\) is a loop at \(4\).
For vertex \(1\), there is one edge to \(2\) and one edge to \(5\), so \(\deg(1)=1+1=2\). For vertex \(2\), there is one edge to \(1\) and two edges to \(3\), so \(\deg(2)=1+2=3\). For vertex \(3\), there are two edges to \(2\) and one to \(4\), so \(\deg(3)=2+1=3\). For vertex \(4\), there is one edge to \(3\), one to \(5\), and one loop, so \(\deg(4)=1+1+2=4\). For vertex \(5\), there is one edge to \(4\) and one to \(1\), so \(\deg(5)=1+1=2\).
Check: The degrees sum to \(2+3+3+4+2=14\). The listed edge instances number \(7\), so the edge-end total is \(2\cdot7=14\). As a second check, count contributions by edge: \(g_1\) contributes \(1+1=2\), \(g_2\) contributes \(2\), \(g_3\) contributes \(2\), \(g_4\) contributes \(2\), \(g_5\) contributes \(2\), \(g_6\) contributes \(2\), and \(g_7\) contributes \(2\). Thus the edge-by-edge total is \(2+2+2+2+2+2+2=14\).
Common Mistakes
Counting a loop once. In the first example, a mistaken count might assign \(\deg(c)=1+1+1=3\): one for \(e_3\), one for \(e_5\), and only one for loop \(e_4\). The correction is to count the loop's two ends: \(\deg(c)=1+1+2=4\). With that correction, the total degree is \(12\), as required by the \(6\) edge instances.
Merging parallel edges. If \(e_1\) and \(e_2\) are treated as one edge, the degrees of both \(a\) and \(b\) in that example are each undercounted by one. The two edges have distinct labels and each contributes an end at each endpoint. Keep the edge instances separate when calculating both degrees and \(m\).
Dropping isolated vertices. A vertex with degree zero is still part of \(V\). Include it in a degree list and in any sum over all vertices. Its contribution to the sum is zero, but omitting it can make a description of the graph incomplete.
Check Your Understanding
For each question, count edge instances explicitly. When checking a total, count loops once as edges and twice as degree contributions.
- Let \(V=\{p,q\}\) and let the edge instances be \(pq,pq,pp\). Find both degrees and check their sum.
- A vertex \(r\) has two loops, three parallel edges to \(s\), and no other incident edges. What is \(\deg(r)\)?
- Can a vertex have degree \(0\) in a multigraph that has at least one edge? Give a precise example.
- A multigraph has \(8\) edge instances. What must the sum of its vertex degrees be, including when some edges are loops?
- Explain why replacing several parallel edges by a single edge can change vertex degrees and the number of edge instances.