## Maths in a minute: Graphs and the degree sum formula

Submitted by Marianne on April 5, 2018This is an example of a graph.

In maths a *graph* is what we might normally call a network. It
consists of a collection of nodes, called *vertices*, connected
by links, called *edges*. The *degree* of a vertex is
the number of edges that are attached to it. The *degree sum formula* says that if you add up the degree of all the vertices in a
(finite) graph, the result is twice the number of the edges in the graph.

There's a neat way of proving this result, which involves double counting: you count the same quantity in two different ways that give you two different formulae. Since both formulae count the same thing, you conclude that they must be equal.

The quantity we count is the number of *incident* pairs (*v*, *e*)
where *v* is a vertex and *e* an edge attached to
it. The number of edges connected to a single vertex *v* is the
degree of *v*. Thus, the sum of all the degrees of vertices in
the graph equals the total number of incident pairs (*v*, *e*)
we wanted to count.

For the second way of counting the incident pairs, notice that each edge is
attached to two vertices. Therefore the total number of pairs
(*v*, *e*) is twice the number of edges. In conclusion,
the sum of the degrees equals the total number of incident pairs
equals twice the number of edges. Proof complete.

(At this point you might ask what happens if the graph contains loops, that is, edges that start and end at the same vertex. The proof works in this case as well, we leave that for you to figure out.)

You can find out more about graph theory in these *Plus* articles.