Directed graphs

A directed graph (or digraph) $G=(V,E)$ consists of vertices $V$ and ordered pairs of edges $E\subseteq V \times V$. Each directed edge is written as $(u,v) \in E$, meaning that this is an edge from $u$ to $v$. Notice that $|E(G)| \leq |V(G)|^2$ for directed graphs $G$.

If $(u,v) \in E$, we say that $v$ is an out-neighbor of $u$ and $v$ is an in-neighbor of $v$. Denote by $\deg^+(v)$ and $\deg^-(v)$ the numbers of out- and in-neighbors of $v$ respectively.

Exercise 25 (Directed Handshake)

Let $G$ be a digraph. Prove: $\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) = |E(G)|$

Given an undirected graph $G_0 = (V,E_0)$, we say that a digraph $G$ is an orientation of $G_0$ if it can be obtained by "giving directions" to edges in $G_0$. More formally, $E_0 = \{\{u,v\}: (u,v) \in E\}$ and for each edge $\{u,v\} \in E_0$, exactly one of $(u,v)$ or $(v,u)$ belongs to $E$. Notice that every undirected graph $G$ has $2^{|E(G)|}$ different orientations. When $G$ is an orientation of $G_0$, we say that $G_0$ is a symmetrization of $G$ (obtained by removing directions from $G$).

There are two notions of connectedness in digraphs. For a digraph $G$, if a symmetrization of $G$ is connected, we say that $G$ is weakly connected. If, for every $u,v \in V(G)$, there is a directed walk from $u$ to $v$ in $G$, then $G$ is said to be strongly connected.

Exercise 26

Prove that a weakly connected digraph contains at least $n-1$ edges and a strongly connected digraph contains at least $n$ edges.

📄️ Eulerian digraphs

A digraph is Eulerian if there is a closed walk containing all vertices and edges, each edge exactly once. The following theorem gives a nice characterization of Eulerian digraphs, analogously to the Eulerian undirected graphs.

📄️ Tournaments

One of the important classes of directed graphs is called tournaments. A tournament is an orientation of a complete graph. We can think of a tournament as the result of players participating in round-robin games where there is no tie or rematch. An edge directed from $u$ to $v$ means that player $u$ won against player $v$.