An (undirected) graph is a pair \(G = (V,E)\) consisting of a set \(V\) and a multi-set \(E\) of unordered pairs of elements in \(V\). Elements of \(V\) are called vertices and elements of \(E\) are called edges. For two vertices \(u,v \in V\), we say \(u\) and \(v\) are adjacent if \(\{ u,v\} \in E\). We call an undirected graph \(G\) simple if all edges are distinct (i.e., \(E\) is a set), and each edge is a pair of distinct vertices.

A directed graph is a pair \(G = (V,E)\) consisting of a set \(V\) and a multi-set \(E\) of ordered pairs of elements in \(V\). Elements of \(V\) are called vertices and elements of \(E\) are called edges. We call a directed graph \(G\) simple if all edges are distinct and each edge is a pair of distinct vertices.

Let \(G\) be a simple graph or a simple directed graph. A vertex \(v\) is reachable from \(u\) if some walk realized in \(G\) runs from \(u\) to \(v\). In the undirected case reachability is an equivalence relation on \(V(G)\); in the directed case it is only a preorder, since walks cannot be reversed.

The symmetric orientation of a simple graph \(G\) is the simple directed graph on \(V(G)\) whose arcs are the ordered pairs \((u, v)\) with \(\{ u, v\} \in E(G)\). A walk is realized in \(G\) exactly when it is realized in the symmetric orientation, so reachability and distances agree.

The distance \(\operatorname{dist}(u, v) \in {\mathbb N}\cup \{ \infty \} \) from \(u\) to \(v\) in a simple directed graph is the least length of a walk from \(u\) to \(v\), and \(\infty \) if \(v\) is not reachable from \(u\). For a simple graph it is the distance in the symmetric orientation, and is then symmetric in \(u\) and \(v\).