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


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


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