Appendix: The Proofs We Skipped, and the Matrix That Does Not Fit

There are three things that the main text used without justification: (i) Euler’s conditions are not only necessary but also sufficient; (ii) a product of matrices counts the number of walks; and (iii) an adjacency matrix can be stored in a fraction of N^2 numbers. Here they are.

Why Euler’s conditions are enough

The concepts page proved the first half of Euler’s theorem: if a route crosses every edge exactly once, then there are at most two nodes with an odd degree. This is why the Königsberg problem is impossible. The second half — if a connected graph has zero or two odd-degree nodes, then such a route always exists — requires a construction, and the construction is short.

Suppose that in a connected graph every node has even degree. Start walking anywhere, never re-using an edge, until you are stuck. The only node you can get stuck at is the one you started from, because every other node was entered and left in pairs, so having just arrived, you have used an odd number of its edges, and since its degree is even, there is always at least one unused edge to depart by. Thus your walk eventually closes on itself and becomes a circuit.

If that circuit misses some edges, then connectivity guarantees an unused edge at one of the nodes on the circuit. Start a second closed trail there, by exactly the same argument, and splice it into the first at that node — walk the original circuit until you reach the node, take the detour, then continue. Repeat until no edges are left. The result is an Eulerian circuit.

In the case of two odd-degree nodes, add a temporary extra edge joining the two odd nodes. Because every degree is now even, the construction above gives a circuit. After deleting the temporary edge from that circuit, an Eulerian trail remains, running from one odd node to the other. This is Hierholzer’s algorithm, and it is also how you would code it.

The same rule when edges have direction

Nothing above used symmetry, so the argument survives one-way streets — but the quantity it is about has to change, because degree splits in two when edges have direction.

Total degree is the wrong thing to look at. A node with three edges in and one out has degree four, an even number, and is still hopeless: a route passing through it consumes one arriving edge and one departing edge, one of each, never two of the same kind. So a node entered and left t times spends t of its in-edges and t of its out-edges. What has to match is not parity but balance:

k^{\text{in}}_i = k^{\text{out}}_i \quad \text{for every } i,

and then, on a graph that is connected once you ignore the arrows, an Eulerian circuit exists. Evenness was never the real condition; it was what balance looks like when an edge has no direction and each visit spends two interchangeable edge-ends.

The open case works the same way. A route that starts at s leaves it once without having arrived, and one that ends at e arrives without leaving again, so an Eulerian trail exists exactly when

k^{\text{out}}_s - k^{\text{in}}_s = 1, \qquad k^{\text{in}}_e - k^{\text{out}}_e = 1,

with every other node balanced — the directed reading of “exactly two odd nodes, and they are where you start and finish”. The construction is unchanged: add a temporary edge from e to s, which balances the whole graph, take the circuit, then delete that edge.

It is worth noticing how little connectivity we had to assume. You might expect a closed tour along one-way streets to require strong connectivity — being able to get anywhere from anywhere, following the arrows. Weak connectivity is enough, because balance supplies the rest: if every node has as many ways out as in, then any node you can reach you can also come back from, and the graph is strongly connected whether you asked for it or not.

Why matrix powers count walks

Let us write {\bf A} for the adjacency matrix of the graph, where A_{ij} is the number of edges between node i and node j.

A walk of length 2 from i to j is composed of a choice of intermediate node \ell, an edge from i to \ell, and an edge from \ell to j. There are A_{i\ell} choices for the first selection and A_{\ell j} choices for the second, resulting in A_{i\ell}A_{\ell j} walks passing through that particular \ell. The intermediate node can be anything, and the possibilities do not overlap, so add them up:

\#\{\text{walks of length } 2 \text{ from } i \text{ to } j\} = \sum_{\ell} A_{i\ell} A_{\ell j} = \left({\bf A}^2\right)_{ij}.

You run along row i, down column j, multiply entry by entry, and add. That is the definition of the matrix product. So the answer is \left({\bf A}^2\right)_{ij}, not merely something resembling it.

We now proceed by induction on the length. A walk of length k+1 from i to j is a walk of length k from i to some node \ell, followed by a single edge from \ell to j. Assuming the claim holds for k, the number of such walks is

\sum_{\ell} \left({\bf A}^{k}\right)_{i\ell} A_{\ell j} = \left({\bf A}^{k}{\bf A}\right)_{ij} = \left({\bf A}^{k+1}\right)_{ij},

which is the claim for k+1. The base case k=1 is the definition of {\bf A} itself.

There are two footnotes. This argument never asks whether a node or an edge is reused, which is exactly why it counts walks and not paths. It never uses symmetry either, so it holds verbatim for directed networks, where A_{ij} counts the edges pointing from i to j.

Storing a matrix that does not fit

A dense adjacency matrix for Earth’s 8 billion people would have (8\times 10^{9})^2 = 6.4\times 10^{19} entries. If each entry takes 8 bytes, that is a total of 512 exabytes. Real networks are sparse, and this notebook focuses on exploiting that sparsity.

If you store an adjacency matrix as a full table, almost all of the space is wasted. In a real network, each node has only a handful of edges, and therefore nearly every entry is zero. The fix is to write down only the entries that are not zero.

Start from an adjacency list — for each row of the matrix, the column IDs that carry a value, and the values themselves:

\{\text{Row ID}: (\text{Column ID}, \text{Value})\}

Compressed Sparse Row (CSR) is nothing more than this list flattened into three plain arrays:

Array	What it holds
indices	the column IDs of every non-zero entry, row after row
data	the matching values, in the same order
indptr	where each row starts inside those two arrays

indptr is the only one that needs a moment’s thought. It is the running total of how many entries each row contributed, beginning at 0 — so indptr[i] is the position in indices where row i begins, and indptr[i+1] is where it ends. Row 0 occupies positions 0 … indptr[1]-1, row 1 picks up at indptr[1], and so on.

Once you see that, these two network operations become library-free one-liners:

• Degree of node i: indptr[i+1] - indptr[i] — the number of non-zero entries in row i.
• Neighbours of node i: indices[indptr[i]:indptr[i+1]] — the column IDs in row i, which are exactly the nodes i connects to. The matching edge weights are data[indptr[i]:indptr[i+1]].

Both one-liners are easier to believe once you have watched CSR get built. The stage below starts from the adjacency list of a small five-node graph — no parallel edges, so every value is a 1 — and lays its rows end to end. What survives that gluing is indices. What it destroys is the row breaks, and writing those down is all indptr is. Then drag the knob: the degree is the distance between the two marked cells in indptr, and the neighbours are what lies between them in indices.

CSR is the format every network library reaches for, because it makes the operation you perform most often — “give me this node’s neighbours” — a contiguous slice.

Now go and build it.

NoteWhere the code lives

Open the sparse-matrix notebook

Prefer to work locally? The same notebook is in the repository at notebooks/m01-euler-tour/sparse-matrices.py. Run it with marimo edit notebooks/m01-euler-tour/sparse-matrices.py.

What you will build

1. Construct a CSR matrix from an edge list with scipy.sparse.
2. Take the format apart and read data, indices and indptr directly.
3. Recover a node’s degree and its neighbour list straight from indptr and indices, without any library call.
4. Measure the memory a dense array and a CSR matrix need for the same network, as the network grows.
5. Use sparse matrix-vector products to run the component-finding code from earlier in the module at a scale where dense arrays would not fit.

What to watch for

• Plot the memory usage against the size of the network for both formats. The curves diverge faster than intuition would suggest, because dense storage grows with the square of the number of nodes, while CSR grows in proportion to nodes plus edges.
• CSR is fast at row-based operations and matrix-vector products, and slow at repeated reads of a single entry. Time both and you’ll remember which is which.
• Compare CSR against COO and CSC on the same operations. Choose the format based on what you are about to do with the matrix.

A good visual introduction to sparse formats by Matt Eding.