Directed Graph Skeletons

Definition

The skeleton of the directed graph $(V, E)$ is the undirected graph $(V, F)$ where

\[ F = \Set*{\set{v, w} \subset V}{(v, w) \in E \text{ or } (w, v) \in E}. \]

In other words, the skeleton is an undirected graph whose vertex set is $V$ and whose edges are all (unordered) pairs which appear as an ordered pair in the directed graph.

In the case that $(V, E)$ is a directed graph and $E$ is a symmetric relation, the skeleton of $(V, E)$ is a natural undirected graph to associate with $(V, E)$. An orientation of an undirected graph $G$ is a directed graph whose skeleton is $G$.

An oriented graph is a directed graph without self-loops satisfying the property for any two vertices $x$ and $y$, either $(x,y)$ or $(y,x)$ is an edge, but not both. An oriented graph can be obtained from an undirected graph by selecting an “orientation” of the undirected edges.