Let \(G\) be a simple graph on a finite vertex set. Then the number of orientations of \(G\) is \(2^{\left\lvert E(G)\right\rvert }\), where \(\left\lvert E(G)\right\rvert \) denotes the number of edges of \(G\); that is, each edge may be directed in either of its two ways, and every such choice yields a distinct orientation.

Let \(D\) be a digraph on a finite vertex set \(V\), and write \(\varepsilon \) for its number of arcs. Then both the sum of the indegrees and the sum of the outdegrees over all vertices equal \(\varepsilon \):

Let \(D\) be a digraph on a finite, nonempty vertex set that contains no directed cycle. Then \(D\) has a vertex \(v\) whose indegree vanishes, \(d^{-}(v) = 0\); that is, no arc of \(D\) has \(v\) as its head.

Let \(D\) be a digraph on a finite vertex set \(V\) with \(n = |V|\), and suppose \(D\) is acyclic: it contains no directed cycle, that is, no closed directed walk of positive length whose vertices, apart from the coinciding endpoints, are distinct. Then \(V\) admits a topological ordering: there is a bijection \(f \colon V \to \{ 0, 1, \dots , n-1\} \) such that \(f(u) \lt f(v)\) for every arc of \(D\) from \(u\) to \(v\).

Let \(D\) be a digraph on a vertex set \(V\). Reversing every arc twice recovers the original digraph, so the converse of the converse of \(D\) equals \(D\); that is, \(\breve{\breve{D}} = D\).

Let \(D\) be a digraph on a finite vertex set, and let \(\breve{D}\) be its converse, obtained by reversing the orientation of every arc. Then for each vertex \(v\) the indegree and outdegree interchange:

where \(d^{-}\) counts the arcs with head \(v\) and \(d^{+}\) the arcs with tail \(v\).

Let \(D\) be a digraph with vertices \(u\) and \(v\), and let \(\breve{D}\) denote its converse, the digraph obtained by reversing the orientation of every arc. Then \(v\) is reachable from \(u\) in \(\breve{D}\) if and only if \(u\) is reachable from \(v\) in \(D\).

Let \(D\) be a digraph on a finite, nonempty vertex set \(V\). If \(D\) contains no directed cycle, then there is a vertex \(v \in V\) whose outdegree vanishes, \(d^{+}(v) = 0\).

Let \(D\) be a strict digraph — a loopless directed graph — on a finite, nonempty vertex set. Write \(\delta ^-(D)\) for the minimum indegree and \(\delta ^+(D)\) for the minimum outdegree, each taken over all vertices of \(D\). Then \(D\) contains a directed path — a directed walk in which no vertex is repeated — whose length (its number of arcs) is at least \(\max \{ \delta ^-(D),\, \delta ^+(D)\} \).

Let \(D\) be a strict digraph on a finite, nonempty vertex set, and let \(k\) be a positive integer such that \(\max \{ \delta ^{-}(D),\delta ^{+}(D)\} =k\), where \(\delta ^{-}(D)\) and \(\delta ^{+}(D)\) denote the minimum indegree and minimum outdegree of \(D\). Then \(D\) contains a directed cycle of length at least \(k+1\).

Let \(D\) be a digraph on a finite vertex set \(V\), and let \(A\) be its \(0/1\) adjacency matrix over \(\mathbb {N}\), so \(A_{uv} = 1\) when there is an arc from \(u\) to \(v\) and \(A_{uv} = 0\) otherwise. Then for every \(k \in \mathbb {N}\) and all vertices \(u, v \in V\), the entry \((A^k)_{uv}\) equals the number of directed walks of length \(k\) from \(u\) to \(v\) in \(D\), that is, the number of sequences of \(k\) arrows \(u = w_0 \to w_1 \to \cdots \to w_k = v\).

Let \(D\) be a digraph on a finite vertex set, and let \(\hat{D}\) denote its condensation: the digraph whose vertices are the strongly connected components (dicomponents) of \(D\), with an arc from one component to another precisely when \(D\) has an arc whose tail lies in the first and whose head lies in the second. Then \(\hat{D}\) contains no directed cycle; that is, for every dicomponent \(c\) and every closed walk in \(\hat{D}\) from \(c\) to \(c\), that walk is not a directed cycle — it does not have positive length together with distinct vertices apart from its coinciding endpoints.

Let \(G\) be a finite simple graph. Then \(G\) admits an orientation \(D\) in which the in- and outdegrees at every vertex differ by at most one; that is, \(\left\lvert d^{+}(v) - d^{-}(v)\right\rvert \le 1\) for every vertex \(v\), where \(d^{+}(v)\) and \(d^{-}(v)\) denote the outdegree and indegree of \(v\) in \(D\).

(Roy, 1967; Gallai, 1968.) Let \(D\) be a digraph on a finite, nonempty vertex set \(V\), and suppose the underlying simple graph of \(D\) has chromatic number \(k\). Then \(D\) contains a directed path — a directed walk \(v_0, v_1, \dots , v_\ell \) whose consecutive vertices are joined by arcs \(v_{i-1} \to v_i\) and whose vertices are pairwise distinct — of length at least \(k - 1\), that is, with \(\ell \ge k - 1\) arcs.

Let \(G\) be a simple graph on a finite vertex set that admits a proper colouring with \(k\) colours. Then \(G\) has an orientation \(D\) — a digraph whose underlying graph is \(G\) and in which no pair of vertices is joined by arcs in both directions — such that every directed path in \(D\) (a directed walk that repeats no vertex) has length at most \(k-1\), that is, passes through at most \(k\) vertices.

Let \(D\) be a tournament on a finite, nonempty vertex set \(V\) — a directed graph with no loops in which, for every pair of distinct vertices \(u\) and \(v\), exactly one of the arcs \(u \to v\) and \(v \to u\) is present. Then \(D\) has a directed Hamilton path: there exist vertices \(u, v\) and a directed path from \(u\) to \(v\) that visits every vertex of \(V\) exactly once.

(Chvátal and Lovász, 1974.) Let \(D\) be a loopless digraph on a finite vertex set \(V\); that is, no vertex has an arc to itself. Then \(D\) admits an independent set \(S \subseteq V\) — no two distinct vertices of \(S\) are joined by an arc of \(D\) in either direction — such that every vertex \(v \notin S\) is reachable from some vertex \(u \in S\) by a directed path of length one or two: either \(u \to v\) is an arc of \(D\), or there is a vertex \(w\) with arcs \(u \to w\) and \(w \to v\).

Let \(D\) be a tournament on a finite, nonempty vertex set \(V\); that is, for each pair of distinct vertices exactly one of the two directed edges between them is present, and no vertex has an edge to itself. Write \(u \to v\) when the edge from \(u\) to \(v\) is present. Then \(D\) has a king: a vertex \(u\) such that every other vertex \(v\) is reached from \(u\) by a directed path of length at most two — that is, either \(u \to v\), or there is a vertex \(w\) with both \(u \to w\) and \(w \to v\).

Let \(D\) be a tournament on a finite, nonempty vertex set \(V\). Then either \(D\) is diconnected, or there is an arc \(x \to y\) of \(D\) whose reversal makes it so: deleting the arc \(x \to y\) and inserting the arc \(y \to x\), while leaving every other arc unchanged, yields a diconnected digraph.

Let \(D\) be a digraph on a finite, nonempty vertex set \(V\). Then \(D\) is unilateral if and only if there exist vertices \(u, v \in V\) and a directed walk from \(u\) to \(v\) — a finite sequence of edges, each traversed in the direction it points — whose vertices include every vertex of \(V\). In other words, \(D\) is unilateral exactly when it admits a spanning directed walk.

Let \(D\) be a tournament on a finite vertex set \(V\) — an orientation of the complete graph on \(V\). Let \(v_1, v_2, \dots , v_k\) be a directed path in \(D\): a nonempty list of distinct vertices such that \(v_j \to v_{j+1}\) is an arc of \(D\) for every \(1 \le j \lt k\). Suppose this path cannot be extended at either end, meaning that for every vertex \(w\) not among \(v_1, \dots , v_k\) there is no arc from \(w\) to \(v_1\) and no arc from \(v_k\) to \(w\). Then for every vertex \(v\) not on the path there is an index \(i\) with \(1 \le i \lt k\) such that \(v_i \to v\) and \(v \to v_{i+1}\) are both arcs of \(D\); that is, \(v\) can be inserted between two consecutive vertices of the path.

Let \(D\) be a digraph on a finite vertex set \(V\), let \(f : V \to \mathbb {R}\) be a real-valued function on the vertices, and let \(m\) and \(n\) be natural numbers. Write \(\chi (D)\) for the chromatic number of the underlying simple graph of \(D\) (in which two vertices are joined whenever there is an arc between them in either direction). If \(\chi (D) \gt mn\), then at least one of the following holds: either \(D\) contains a directed path \(u_0 \to u_1 \to \cdots \to u_m\) on \(m+1\) distinct vertices along which \(f\) is nondecreasing, \(f(u_0) \le f(u_1) \le \cdots \le f(u_m)\); or \(D\) contains a directed path \(v_0 \to v_1 \to \cdots \to v_n\) on \(n+1\) distinct vertices along which \(f\) is strictly decreasing, \(f(v_0) \gt f(v_1) \gt \cdots \gt f(v_n)\).

Let \(m, n, N\) be natural numbers with \(mn \lt N\), and let \(g_0, g_1, \dots , g_{N-1}\) be a sequence of \(N\) distinct integers. Then the sequence has an increasing subsequence of length \(m\) — indices \(i_1 \lt i_2 \lt \dots \lt i_m\) with \(g_{i_1} \lt g_{i_2} \lt \dots \lt g_{i_m}\) — or a decreasing subsequence of length \(n\) — indices \(j_1 \lt j_2 \lt \dots \lt j_n\) with \(g_{j_1} \gt g_{j_2} \gt \dots \gt g_{j_n}\).

Let \(G\) be a finite simple graph with maximum degree \(\Delta (G)\). Then \(G\) admits an orientation \(D\) — a digraph on the same vertex set whose underlying graph is \(G\) and in which no two vertices are joined by arcs in both directions — such that every directed path in \(D\), that is, every directed walk that repeats no vertex, has length at most \(\Delta (G)\), where the length of a path is the number of arcs it traverses.

Let \(D\) be a diconnected tournament on a finite vertex set with at least three vertices, and let \(u\) be any vertex of \(D\). Then for every integer \(k\) with \(3 \le k \le \left\lvert V(D)\right\rvert \) there is a directed cycle of length \(k\) passing through \(u\).

Let \(D\) be a loopless finite digraph on a vertex set of size \(n \gt 2\), and suppose that every vertex \(v\) satisfies \(d^{-}(v) \ge n/2\) and \(d^{+}(v) \ge n/2\), where \(d^{-}(v)\) and \(d^{+}(v)\) denote the indegree and outdegree of \(v\). Then \(D\) contains a directed cycle of length \(n\); that is, a closed directed walk of positive length whose vertices, apart from the coinciding endpoints, are distinct, and which passes through every vertex of \(D\).

Let \(D\) be a digraph on a finite, nonempty vertex set \(V\) whose underlying undirected graph is connected. Then \(D\) admits a directed Euler tour—a closed directed trail that traverses every arc of \(D\) exactly once—if and only if every vertex \(v \in V\) is balanced, meaning its outdegree and indegree agree, \(d^{+}(v) = d^{-}(v)\).

Let \(D\) be a finite digraph, let \(x \neq y\) be two of its vertices, and let \(l\) be a natural number. Suppose that \(d^{+}(x) - d^{-}(x) = l\) and \(d^{-}(y) - d^{+}(y) = l\), and that every other vertex \(v\) (that is, \(v \neq x\) and \(v \neq y\)) satisfies \(d^{+}(v) = d^{-}(v)\), where \(d^{+}\) and \(d^{-}\) denote outdegree and indegree. Then \(D\) contains \(l\) pairwise arc-disjoint directed paths from \(x\) to \(y\).

Let \(D\) be a diconnected digraph on a finite vertex set, so that every vertex is reachable from every other along directed paths. Suppose the underlying simple graph of \(D\), obtained by forgetting the orientation of each arc, contains a cycle of odd length. Then \(D\) contains a directed cycle of odd length.

Let \(D\) be a finite digraph whose vertex set has at least two vertices. Then \(D\) is diconnected — every vertex is reachable from every other along a directed path — if and only if \(D\) is \(1\)-arc-connected; that is, if and only if for every nonempty proper subset \(S\) of the vertex set there is at least one arc of \(D\) with tail in \(S\) and head outside \(S\).

Let \(G\) be a finite simple graph on a vertex set with at least two vertices, let \(D(G)\) be its associated digraph (each edge of \(G\) replaced by the two oppositely oriented arcs joining its ends), and let \(k\) be a natural number. Then \(D(G)\) is \(k\)-arc-connected if and only if \(k \le \kappa '(G)\), where \(\kappa '(G)\) denotes the edge connectivity of \(G\).

Let \(n \ge 2\) be an integer, and let \(v\) be any vertex of the de Bruijn digraph \(D_n\). Then both the indegree and the outdegree of \(v\) equal \(2\); that is, \(d^{-}(v) = 2\) and \(d^{+}(v) = 2\).

Fix an integer \(n \ge 2\), and let \(D_n\) be the de Bruijn digraph whose vertices are the binary strings of length \(n-1\) and whose arcs run from each string \(p_1 p_2 \cdots p_{n-1}\) to every string of the form \(p_2 p_3 \cdots p_{n-1} b\) with \(b \in \{ 0,1\} \). Form the underlying undirected simple graph on the same vertex set, in which two distinct strings are adjacent precisely when an arc of \(D_n\) joins one to the other in either direction. Then this graph is connected: its vertex set is nonempty and any two vertices are linked by a path.

For every integer \(n \ge 2\), the de Bruijn digraph \(D_n\) admits a directed Euler tour: there exist a vertex \(u\) and a closed directed walk based at \(u\) that traverses each arc of \(D_n\) exactly once.

Let \(G\) be a finite simple graph on a nonempty vertex set, and suppose its edge connectivity satisfies \(\kappa '(G) \ge 2\). Then \(G\) has a diconnected orientation: one can assign a direction to each edge of \(G\), forming a digraph \(D\) whose underlying graph is \(G\), so that for every ordered pair of vertices \(u, v\) there is a directed path in \(D\) from \(u\) to \(v\).

Let \(G\) be a finite graph on a nonempty vertex set that admits an Eulerian trail — a walk traversing every edge of \(G\) exactly once — and let \(k\) be a natural number with \(2k \le \kappa '(G)\). Then \(G\) has an orientation that is \(k\)-arc-connected.

Let \(D\) be a diconnected tournament on a finite vertex set \(V\) with \(\nu = \left\lvert V\right\rvert \ge 5\), and let \(A\) be its \(\nu \times \nu \) adjacency matrix over \(\mathbb {N}\), so that \(A_{uv} = 1\) when there is an arc from \(u\) to \(v\) and \(A_{uv} = 0\) otherwise. Writing \(d\) for the directed diameter of \(D\), every entry of the matrix power \(A^{\, d+3}\) is strictly positive; that is, \(\bigl(A^{\, d+3}\bigr)_{ij} \gt 0\) for all \(i, j \in V\).

Let \(D\) be a tournament on a finite vertex set \(V\) (an orientation of the complete graph on \(V\)), and let \(A\) be its \(0/1\) adjacency matrix. Then \(A\) is primitive — that is, some power \(A^{k}\) has all entries positive — if and only if \(D\) is diconnected (every vertex is reachable from every other) and \(V\) has at least four vertices.