Degrees, the degree sum, and even and odd vertices

Vertex degree and the degree sum

The degree of a vertex is the number of edge-ends attached to it. The degrees of all vertices add to twice the number of edges

1. Count edge-ends Count each edge-end attached to the named vertex \(\displaystyle \deg(A)=1+1+1=3\)
2. Count a loop twice A loop contributes two to the degree of its vertex \(\displaystyle \text{degree contribution of one loop}=2\)
3. Keep parallel edges separate Each edge in a parallel pair contributes its own edge-end \(\displaystyle A\mathord{-}B,\quad A\mathord{-}B\Rightarrow\deg(A)\text{ gains }2\)
4. Use the degree sum The sum of all degrees equals twice the number of edges \(\displaystyle 3+2+3+2=10=2\times5\)

Worked example

An undirected graph has vertices A, B, C and D. At A there is one loop, two parallel edges join A to B, and one edge joins A to C. The other vertex degrees are 3, 2 and 2, and the graph has 6 edges. Find the degree of A and verify the degree sum

1. \(\displaystyle \deg(A)=2+1+1+1=5\)The loop contributes two and the three other attached edges contribute one each
2. \(\displaystyle 5+3+2+2=12\)Add the four vertex degrees to obtain the degree sum
3. \(\displaystyle 2\times6=12\)Twice the 6 edges is 12, so the degree sum is verified

Common mistakes

Difficulty levels

Questions about this topic

In this chapter