Number of acyclic orientations

Task number: 4458

Count how many acyclic orientations the complete graph on \(n\) vertices has.
  • Solution

    Let the vertices of the graph be numbered from 1 to \(n\). We construct a bijection between the permutations on the set \({1,\ldots,n}\) and the acyclic orientations of the graph.

    Each acyclic orientation can be topologically ordered, yielding a permutation of vertices. Since every two vertices are connected by an edge, the topological ordering is uniquely determined.

    Each permutation \(\pi\) determines an orientation: for a pair of vertices \({i,j}\), we look at what position they lie in the permutation, and orient the edge from the smaller position to the larger one.

  • Answer

    There are \(n!\) acyclic orientations of the complete graph \(K_n\).
Difficulty level: Moderate task
Reasoning task
Cs translation
Send comment on task by email