Graphs and Networks

The idea in one sentence

A graph is a set of dots and a set of lines joining some of them, and stripping a problem down to just that — who is connected to whom — is often enough to solve it.

Vertices, edges, degree

The dots are vertices, the lines are edges, and the degree of a vertex is how many edges meet it.

Nothing else is part of the definition. Where you draw the dots does not matter, nor how long or curved the lines are. Two drawings that look completely different are the same graph if the same pairs are joined. That is the whole trick: throw away distance and position, and what is left is connection.

Which is why a metro map is a graph. It lies about distances and directions on purpose, because a passenger only needs to know which stations connect.

The handshake lemma

Add up the degrees of every vertex and you get exactly twice the number of edges:

Every edge has two ends, and each end contributes 1 to the degree of the vertex it lands on. Counting ends is the same as counting edges twice.

It has an immediate consequence worth stating: the number of odd-degree vertices is always even. The total is even, so the odd contributions have to pair up.

In party terms: at any gathering, the number of people who have shaken hands an odd number of times is even. You cannot arrange otherwise, however you try.

A complete graph joins every pair. With \(n\) vertices each has degree \(n-1\), so the degree total is \(n(n-1)\) and

Five vertices give \(\frac{5 \times 4}{2} = 10\) edges — which is also \(\binom{5}{2}\), the number of ways to choose a pair.

The bridges of Königsberg

The subject starts with a real question. Königsberg had seven bridges, and townspeople wondered whether a walk could cross each exactly once.

Euler’s answer, in 1736, was no — and the argument invented the field. Shrink each landmass to a vertex and each bridge to an edge. Now, every time your walk enters a vertex it must also leave, so it uses up edges in pairs. A vertex with odd degree therefore has to be the start or the end of the walk.

All four Königsberg vertices have odd degree, and a walk has only two ends. Impossible.

This gives the general rule for an Euler path, one using every edge exactly once:

• 0 odd vertices → an Euler circuit exists, starting and ending in the same place.
• 2 odd vertices → an Euler path exists, starting at one odd vertex and ending at the other.
• 4 or more odd vertices → no such route.

The nice thing is that you can settle it by counting degrees, without searching for a route at all.

Where graphs are used

• Routing. Road networks, delivery rounds, the travelling salesman problem.
• Social networks. People as vertices, friendships as edges; “degrees of separation” is literally a path length.
• The web. Pages as vertices, links as edges — PageRank is a calculation on that graph.
• Scheduling and colouring. Exams that share a student get an edge; the minimum number of timeslots is the graph’s chromatic number.
• Circuits, molecules, dependency trees, family trees. Anything where the relationships matter more than the positions.

Common mix-ups

• Confusing this with a graph of a function. Same word, unrelated object. This one is dots and lines; that one is a picture of \(y = f(x)\).
• Thinking the drawing matters. Curved or straight, crossing or not, it is the same graph.
• Mixing Euler with Hamilton. An Euler path uses every edge once; a Hamiltonian path visits every vertex once. The first has an easy test, the second has no known efficient one.
• Counting each edge twice when totalling edges, or once when totalling degrees.
• Assuming every graph is connected. Some come in separate pieces.

Check yourself

How many edges has a complete graph on 5 vertices, what does the degree sum equal, and how many odd-degree vertices does a graph with an Euler circuit have?

\(\frac{5 \times 4}{2} = 10\). The degree sum is twice the number of edges, since each edge has two ends. And a circuit enters and leaves every vertex in pairs, so it needs 0 odd vertices.