The monadic second-order logic of graphs VIII: Orientations Original Research Article

In every undirected graph or, more generally, in every undirected hypergraph of bounded rank, one can specify an orientation of the edges or hyperedges by monadic second-order formulas using quantifications on sets of edges or hyperedges. The proof uses an extension to hypergraphs of the classical notion of a depth-first spanning tree. Applications are given to the characterization of the classes of graphs and hypergraphs having decidable monadic theories.