\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Ordered Undirected Graphs
Directed Acyclic Graphs
Needed by:
Sheet PDF
Graph PDF

Ordered Undirected Graph Orientations


There is a natural orientation of an ordered undirected graph.

Motivating result

An ordered undirected graph can be converted into a directed graph by orienting the edges from lower to higher index. The orientation of an ordered undirected graph $((V, E),\sigma )$ is the directed graph $(V, F)$ where

\[ \set{v, w} \in V \implies (v, w) \in F \text{ and } \inv{\sigma }(v) < \inv{\sigma }(w). \]

In other words, we can “convert” the ordered undirected graph by “orienting” the edges from lower to higher index.

Let $G = ((V, E), \sigma )$ be an ordered undirected graph. The orientation of $G$ is acyclic.
Contradiction on the existence of a cycle.1

Conversely, let $(V, F)$ be directed acyclic. To each topological numbering $\sigma $ of $(V, F)$ (see Directed Paths) there exists an ordered undirected graph $((V, E), \sigma )$ where $(V, E)$ is the skeleton of $(V, F)$.


Let $G = ((V, E), \sigma )$ be an undirected graph with

\[ V = \set{a,b,c,d,e}, \]

\[ E = \set*{\set{a, b}, \set{a, c}, \set{a, e}, \set{b, d}, \set{b, e}, \set{c, d}, \set{c, e}, \set{d,e}}, \]


\[ \sigma (1) = a \quad \sigma (2) = c \quad \sigma (3) = d \quad \sigma (4) = b \quad \sigma (e) = 5. \]

We visualize $G$ and its (directed acyclic) orientation above.

  1. Future editions will expand. ↩︎
Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view