Vertices, Edges and Degree

Draw four dots and join some pairs. At each dot, count how many lines meet it. Now add those four counts. Compare your total with the number of lines you drew. What is the relationship?

The degree of a vertex is the number of edge-ends meeting it. Every edge has two ends, so adding the degrees counts every edge exactly twice. That gives a result that holds for every network without exception.

A vertex is one of the objects in a network, drawn as a dot. An edge is a connection between two vertices, drawn as a line.

The degree of a vertex is the number of edge-ends that meet it. For an ordinary vertex with no loops that is simply the number of lines you can see arriving there.

In the network in the diagram, $A$ has three lines meeting it, so its degree is $3$. Vertices $B$, $C$ and $E$ each have two, and $D$ has three.

Degree belongs to a vertex, not to the network. A network has many degrees, one per vertex, and questions about "the degree" always name which vertex they mean.

Degrees are written as $\deg(A) = 3$ when a compact notation is wanted.

A loop joins a vertex to itself, so both of its ends arrive at the same place.

That means a loop contributes $2$ to the degree of its vertex, not $1$. A vertex with one ordinary edge and one loop has degree $3$.

This is not an arbitrary convention chosen to make a formula work. Imagine walking along the network: arriving at the vertex along the loop and leaving along it again uses the loop twice, once in each direction, and the degree is counting the ways in and out.

The phrase "edge-ends" in the definition is doing this work. Defining degree as "the number of edges meeting the vertex" would give a loop a count of $1$ and would break everything that follows, so the definition is written in terms of ends deliberately.

Here is the central result of the lesson, and it is proved by counting one quantity in two different ways.

Count all the edge-ends in a network. Every edge has exactly two ends, so if there are $e$ edges then there are $2e$ ends altogether.

Now count the same ends a second way, by going round the vertices and adding up how many arrive at each. That total is the sum of the degrees.

Both counts count the same collection of things, so they are equal:

$\text{sum of degrees} = 2e$

Checking on the diagram: the degrees are $3$, $2$, $2$, $3$, $2$, adding to $12$, and the network has $6$ edges, with $2 \times 6 = 12$. The result holds for every network, loops and multiple edges included, because the argument never assumed otherwise.

The degree sum is $2e$, which is even. That single fact has a consequence worth more than the formula.

Split the vertices into those of even degree and those of odd degree. The even ones contribute an even total, since a sum of even numbers is even.

So the odd ones must also contribute an even total, because the whole is even and even minus even is even. But a sum of odd numbers is even only when there is an even number of them.

Therefore: every network has an even number of odd-degree vertices. Never one, never three, never five.

This is a strong claim about every network that will ever be drawn, obtained from nothing but counting ends. It is also the fact that decides the Königsberg bridge problem in Lesson 10, so it is worth being convinced by the argument rather than merely remembering the statement.

Lesson 1 noted that a network can be drawn many ways. Degrees give a quick test for telling drawings apart.

If two drawings represent the same network, then each vertex keeps its degree, so the two lists of degrees must match. Different degree lists therefore prove the networks are different, and that test is fast.

The converse fails. Two networks can have identical degree lists and still be different, because the degrees say how many connections each vertex has but not which vertices they go to.

So matching degree lists mean "not yet ruled out", and settling the question then requires comparing the edge lists properly, as in Lesson 1.

This is a general pattern in mathematics worth naming: a quick check that can only ever disprove is still useful, provided you do not read a pass as a proof.

Five items on degree. Use the degree sum as a check wherever you can.

1. 1 A network has edges $AB$, $AC$, $AD$. What is $\deg(A)$?

   Show answer
   $A$ appears in all three edges.$3$

2. 2 A network has $8$ edges. What is the sum of all its degrees?

   Show answer
   Every edge has two ends.$16$

3. 3 A vertex has one ordinary edge and one loop. What is its degree?

   Show answer
   The loop contributes both of its ends to the same vertex.$3$

4. 4 Can a network have exactly three vertices of odd degree?

   Show answer
   Odd-degree vertices must pair up, because the degree sum is even.No

5. 5 The degrees of a network are $3$, $3$, $2$, $2$. How many edges does it have?

   Show answer
   The sum is $10$, which equals $2e$.$5$