Graphs

Graph

Formally, a simple graph is a pair of sets $(V,E),$ where $V$ is an arbitrary non-empty finite set, whose elements are called vertices or nodes, and $E$ is a set of pairs of elements of $V,$ which we call edges. In an undirected graph, the edges are unordered pairs or just sets of size two. We usually write ${uv}$ instead of $\left\{ u, v \right\}$ to denote the undirected edge between $u$ and $v$. In a directed graph, the edges are ordered pairs of vertices. We usually write $u\rightarrow v$ instead of $(u, v)$ to denote the directed edge from $u$ to $v$.

Following standard (but admittedly confusing) practice, we will also use $V$ to denote the number of vertices in a graph and $E$ to denote the number of edges. Thus, in any undirected graph, we have $0 ≤ E ≤ \binom{V}{2}$, and in any directed graph, we have $0 ≤ E ≤ V (V − 1)$.

The endpoints of an edge $uv$ or $u\rightarrow v$ are its vertices $u$ and $v$. We distinguish the endpoints of a directed edge $u\rightarrow v$ by calling $u$ the tail and $v$ the head.

The definition of a graph as a pair of sets forbids multiple undirected edges with the same endpoints or multiple directed edges with the same head and the same tail. (The same directed graph can contain both a directed edge $u\rightarrow v$ and its reversal $v\rightarrow u$.) Similarly, the definition of an undirected edge as a set of vertices forbids an undirected edge from a vertex to itself. Graphs without loops and parallel edges are often called simple graphs; non-simple graphs are sometimes called multigraphs. Despite the formal definitional gap, most algorithms for simple graphs extend to multigraphs with little or no modification, and for that reason, we see no need for a formal definition here.

For any edge $uv$ ...