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$ ...