The connectivity of acyclic orientation graphs

The acyclic orientation graph, AO(G), of an undirected graph, G, Is the graph whose vertices are the acyclic orientations of G and whose edges are the pairs of orientations differing only by the reversal of one edge. Edelman (1984) has observed that it follows from results on polytopes that when G is simple, the connectivity of AO(G) is at least n - c, where n is the number of vertices and c is the number of components of G. In this paper we give a simple graph-theoretic proof of this fact. Our proof uses a result of independent interest. We establish that if H is a triangle-free graph with minimum degree at least k, and the graph obtained by contracting the edges of a matching in H is k-connected, then H is k-connected. The connectivity bound on AO(G) is tight for various graphs including K-n, K-p,K-q, and trees. Applications and extensions are discussed, as well as the connection with polytopes. (C) 1998 Elsevier Science B.V. All rights reserved.