Nodes and edges.

Step 1 of 5

From a town to a graph

The town of Königsberg, today Kaliningrad, was built on the river Pregel, which splits round an island. Four pieces of land, A to D, and seven bridges between them. When Leonhard Euler thought about the town in 1736, he saw that the shape of the lands and the length of the bridges change nothing: all that matters is what is joined to what.

A picture like that is called a graph: nodes (the lands) and edges (the bridges) joining pairs of nodes. The degree of a node is the number of edges touching it. Graphs describe nearly every network: social networks, roads, websites and routers. Predict, and then Look inside will shrink the town into a graph.

Step 2 of 5

Degrees

Each node in the graph is labelled with its degree. When you add up all the degrees, each edge is counted once at each of its ends.

Step 3 of 5

Handshakes

A surprising fact follows, the handshake lemma: at a party, the number of people who shook an odd number of hands is always even. The degrees add up to an even number, so the odd nodes come in pairs.

Step 4 of 5

A new bridge

In the Scene you can remove bridges or add two new ones. Each bridge touches two lands, so it changes two degrees.

Step 5 of 5

Counting back

The link between degrees and edges works both ways. In the graph of five bridges, for instance, you can count the bridges, but you can also add up the degrees and halve them.