A Graph Theory Primer

You have probably noticed that most of the mathematical exposition has been deferred to an appendix. However, basic graph theory shall be the exception to the rule.

Graphs are important to understand even for people who only seek cursory, informal understanding. They aren't just a theoretical instrument, but they underwrite all of the visual language used to illustrate and demonstrate pretty much everything throughout this book. Besides, they are easy and fun, so why not?

Graphs

A (directed) graph is nothing but a bunch of circles called nodes or vertices, and a bunch of arrows between them called edges. For example:

A whacky graph

We are usually interested in less whacky graphs, so we assume there are no multiple arrows between the two same vertices, and no loopy arrows going from a vertex to itself, for example:

a simple graph

This is called a simple (directed) graph.

In most textbooks, directed graphs are considered an intermediate topic, and the discussion start with undirected graphs. These are graphs where for any two vertices $A$, $B$ there is an arrow from $A$ to $B$ if and only if there is an arrow from $B$ to $A$. In this case, the two arrows are compressed into a single, arrowless line. For example:

an undirected graph

Unlike most textbooks, we will be concerned almost exclusively with directed graphs, so we will employ a backward convention: a graph is assumed to be directed unless explicitly stated otherwise.

Usually undirected graphs are used to describe reciprocal affinities: for example, the graph whose nodes are Facebook users, and there is an edge between any two people if and only if they are friends on Facebook, is undirected. That's because being friends on Facebook is subject to mutual agreement and is thus reciprocal. In contrast, Twitter allows users to follow other users without being followed back, so a similar graph will be directed.

DAGs

We want to use graphs to describe causality or chronology. It makes sense that such a graph would be directed, because it does not make sense that an event $A$ caused or preceded event $B$ while event $B$ caused or preceded event $A$.

However, how will you understand the chronology described by this graph:

A closed timelike curve

Does it say that event $A$ happened before event $B$ that happened before event $C$, that happened before event $A$? Well, if we are being completely honest, the existence of closed timelike curves is still very much an open question. Nevertheless, we will make the assumption that our blockchain will never traverse such a loop. Let us carefully define what this means, the terms we introduce for that purpose will accompany us for the rest of the book.

Given a simple directed graph, we say that the vertex $B$ is reachable from the vertex $A$ if there is some way to get from $A$ to $B$ by only following arrows. For example:

$A$ and $A'$ are both reachable from $B$. However, $B$ is reachable from $A$ but not from $A'$.

Each way to reach $B$ from $A$ is called a path. A path is just a list of arrows such that the first arrow leaves $A$, the last arrow enters $B$, and any arrow in between leaves the vertex entered by the previous arrow.

For example, in the graph above:

There is a single path from $A$ to $B$ (red), but three different paths from $B$ to $A'$ (orange, blue, and green)

Note that in our convention, a path must have at least one arrow. Staying in place doesn't count. Under this convention, a cycle is a path from any vertex $A$ to itself. Given the name, the following definition should not come as a surprise.

Definition: A directed acyclic graph (DAG) is a simple directed graph with no cycles.

The DAGs that will interest us have one more useful property, they are rooted. That is, there is a vertex that we call $G$ (alluding to the genesis block) with the property that it is reachable from all other vertices. We call this vertex the root of the DAG.

Note that I assumed above that if the DAG is rooted then it only has one root. It is easy to prove that this is indeed the case, and there could not be a rooted DAG with two roots.

Trees

In the context of block chains, we are interested in a particular type of rooted DAG called a tree:

Definition: A rooted DAG is called a tree if all vertices have at most one arrow leaving them

One can see that the definition is less flexible than seems. The properties of a rooted DAG actually imply that there are zero arrows leaving the root vertex, and one arrow leaving any other vertex. A node that has no arrow going into it is called a tip or a leaf.

Given any node beside the root, we call the nodes it is pointing at its parent. Given any node that is not a tip, we call the nodes pointing at it its children. Note that a vertex can have many children but only one parent. Hence, for any non-root vertex $B$ we can define without ambiguity that $B.Parent$ is the unique vertex that $B$ points to:

In any other graph theory book you open, you will find an opposite convention. Trees are either undirected, or directed with the arrows pointing away from the root, making the parents further from the root than the children. This is not because computer scientists think that trees grow from foliage to root, but because trees are often used to describe many possible routes that all converge to the same conclusion, and from this vantage the root is the "end of time" and not the "beginning of time". However, in this book we assume that the root is the oldest block, encouraging an inverse convention.

Note that in a rooted tree there is only one path from any (non-root) vertex to the root (in the exercises you will show the converse, that a rooted DAG where there's only one path from any non-root vertex to the root is a tree). We call this path the chain of $B$, and denote it $B.Chain$.