icon

Maths in a minute: Graphs and the degree sum formula

Share this page
Graph

This 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.

  • Want facts and want them fast? Our Maths in a minute series explores key mathematical concepts in just a few words.

  • What do chocolate and mayonnaise have in common? It's maths! Find out how in this podcast featuring engineer Valerie Pinfield.

  • Is it possible to write unique music with the limited quantity of notes and chords available? We ask musician Oli Freke!

  • How can maths help to understand the Southern Ocean, a vital component of the Earth's climate system?

  • Was the mathematical modelling projecting the course of the pandemic too pessimistic, or were the projections justified? Matt Keeling tells our colleagues from SBIDER about the COVID models that fed into public policy.

  • PhD student Daniel Kreuter tells us about his work on the BloodCounts! project, which uses maths to make optimal use of the billions of blood tests performed every year around the globe.