Orientable Graphs
Table of Contents

Orientable Graphs

Definition: A digraph $D$ is said to be Orientable if there exists an orientation (a selection of arc directions) that makes $D$ strongly connected (there exists a directed path between each pair of vertices).
Definition: An Orientation of a graph $G$ is the replacement of all edges $\{ x, y \} \in E(G)$ with either the arc $(x, y)$ or $(y, x)$.

A good example of an orientable graph is the following digraph $D$:

Screen%20Shot%202014-04-11%20at%2010.58.34%20AM.png

When we reorient the edges, we can easily get a strongly connected digraph:

Screen%20Shot%202014-04-11%20at%2010.58.37%20AM.png

Hence, the original digraph $D$ is orientable.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License