Degrees, the degree sum, and even and odd vertices practice questions | General Mathematics (Year 12, VCE Units 3 & 4, Graphs and networks, Graphs and networks)

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

\sum_{v\in V}\deg(v)=2e

Count edge-ends Count each edge-end attached to the named vertex \(\displaystyle \deg(A)=1+1+1=3\)
Count a loop twice A loop contributes two to the degree of its vertex \(\displaystyle \text{one loop at }A\Rightarrow\deg(A)=2\)
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\)
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

\deg(A)=2+1+1+1=5,\quad 5+3+2+2=12

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

Common mistakes

Counting a loop once

✕\(\displaystyle \deg(A)=1+1+1=3\)✓\(\displaystyle \deg(A)=2+1+1=4\)

A loop has two attached ends at the same vertex, so it contributes two to the degree

Counting distinct neighbours

✕\(\displaystyle \deg(A)=2\)✓\(\displaystyle \deg(A)=2+1+1+1=5\)

Degree counts attached edge-ends, not just distinct neighbours, so the loop and parallel edges must be counted separately

Equating the degree sum with the edge count

✕\(\displaystyle 5+3+2+2=6\)✓\(\displaystyle 5+3+2+2=12=2\times6\)

Every edge contributes two edge-ends, so the sum of the degrees is twice the number of edges

Difficulty levels

introRead two degrees in a simple graph and calculate the degree sum

standardCount degrees with a loop and parallel edges, then count odd or even vertices

challengeUse a degree list to find edges, a missing degree or a degree from an adjacency matrix

examSelect a degree from five values using the loop and edge-end conventions

Questions about this topic

What is the degree of a vertex?+

It is the number of edge-ends attached to that vertex. A loop contributes two because both ends are attached there

Why does a loop add two to degree but one to the edge count?+

A loop is one edge, so it adds one to the number of edges. Its two ends are both attached to the same vertex, so it adds two to that vertex's degree

Why is the sum of degrees twice the number of edges?+

Every edge has two ends, so counting all attached ends counts each edge twice

Can I use a calculator?+

No. This topic is practised without a calculator

Which year level and chapter is this?+

Year 12, VCE Units 3 & 4, General Mathematics, chapter 13: Graphs and networks

In this chapter

Count the vertices, edges and loops of a graph Degrees, the degree sum, and even and odd vertices Graph types, subgraphs, connection models and method selection Connected graphs and bridges Identify isomorphic graphs Planar graphs and drawings in planar form Faces and Euler's formula Represent a network in a matrix Identify the network a connection matrix describes Classify a route: walk, trail, path, circuit or cycle Eulerian trails and circuits: existence and identification Hamiltonian paths and cycles Read a weighted graph The shortest path by inspection Dijkstra's algorithm for shortest distances and routes Trees and spanning trees Minimum spanning trees by Prim's and Kruskal's algorithms A full network investigation