Graph theory: keeping track of connections

There are six places below. The letters give us short names for them: $A$ is home and $E$ is school. A line means there is a direct road between its ends. For now, every road can be used in either direction. The length of a drawn line does not record a distance.

The points representing places are called vertices; the lines recording direct connections are called edges. Two places without an edge between them cannot be reached in one step, although a route through other places may still connect them. We have kept the information about direct connections on its own.

First select a place and look at its connected edges. Then use the edge buttons to add or remove one connection. The places keep their positions, so you can see exactly which relationship changes.

Now return to the original seven roads. Let us ask a small question: how many roads can we take directly from one place? The number of edges meeting a vertex is its degree. This example has no edge from a place back to itself, and no multiple edges between the same two places.

$A$, for example, meets $AB$ and $AC$, so its degree is $2$. Each press of Next step below adds one edge and records one count at each end. Gold marks the edge just added; the table keeps all the counts already recorded.

Why must the total count be twice the number of edges? Every edge has two ends. Wherever those ends are, we count it once at one end and once at the other. Each added edge therefore adds $1+1=2$ to the total. After every edge has been processed, we get the equation below.

This is often called the handshaking lemma: count each handshake once for each of its two people. We derived it by counting edge ends, so it applies to any finite undirected graph of the kind described here, not just our seven-road example.

Direct connections alone do not answer our original question. Home has no direct road to school, but we can go through the shop and library. Following connected edges in order gives a walk. Here its length means the number of edges used: $A$ to $B$ uses one, then $B$ to $D$ uses one, then $D$ to $E$ uses one, giving $1+1+1=3$ edges.

We call a walk with no repeated vertex a simple path. In this simple undirected graph, a cycle starts and ends at the same vertex, repeats no other vertex, and uses at least three edges. For example, $A,B,D,C,A$ returns to the first $A$ after visiting each other place once.

Below, you may choose only a place directly connected to your current position. Try reaching school, then reset and return home. The numbered labels show the order of visits; if you visit a place again, the complete sequence remains below.

An undirected graph is connected when there is a path between every pair of vertices. Remove both roads touching school and school becomes separated from the other places. Even if the remaining five places can still reach one another, the whole graph is no longer connected.

A one-way road needs another piece of information: being able to go from $A$ to $B$ does not let us go back from $B$ to $A$. An arrow records the permitted direction, giving a directed graph. Our search can follow arrows too, but reachability must then specify a starting place and a direction.

Trying routes without a record can bring us back to the same place repeatedly. We can put discovered places whose roads we have not yet examined into a waiting line. We process the earliest entry first. This record is called a queue: its front is on the left below, and new entries join on the right.

At first we know only the starting place. Mark it as $0$ steps away and put it in the queue. Next, remove the front place and inspect its outgoing connections one at a time. When we find a place not yet discovered, record where we found it from and how many steps reach it, then put it at the back of the queue. Do not add an already discovered place again.

Why add $1$ to the current distance? We already have a route to the current place. Following the edge just inspected extends that route by one edge. If the current place was reached in $2$ steps, the new one is recorded at $2+1=3$ steps.

This method processes a nearer layer before the next layer. It is called breadth-first search, or BFS. Use Next step to inspect individual edges and queue changes; the search never advances on its own. Grey means undiscovered, green means discovered, and gold marks the connection being inspected.

Now we need to explain why the recorded number of steps is the smallest possible. The starting place needs $0$ steps. Every neighbour of the start is discovered while we process the start, and needs $1$ step. The queue places all these one-step places ahead of any two-step place discovered later.

Continue this reasoning. When we process layer $k$, the places whose shortest routes use $k$ edges, all closer layers have already been processed. An undiscovered neighbour can be reached in $k+1$ steps: use the known $k$-step route, then follow one more edge.

Could a shorter route reach this new place? If it could, the place just before it on that shorter route would have a shortest distance smaller than $k$. That place would already have been processed, including its connection to our new place. Our new place would therefore already have been discovered, contradicting its being undiscovered now. So the new record of $k+1$ is the smallest possible.

Starting with layer $0$, this argument justifies every following layer. Each discovered place enters the queue only once, and there are finitely many places, so the queue eventually becomes empty. Any place still undiscovered is unreachable: on a supposed route to it, the first undiscovered place would have been discovered when its discovered predecessor was processed.

The quantity minimised here is the number of edges. If every road takes the same time, that also minimises time. Different times need different reasoning. A direct road might take $10$ minutes, while two roads through another stop each take $2$ minutes, giving $2+2=4$ minutes in total. A number such as travel time assigned to an edge is called its weight. BFS layers do not add these weights.

Try answering before opening the worked explanations. Use the original seven edges, and return to the diagrams to check them one at a time.