Strongly Connected Mixed Graphs and Connected Detachments of Graphs

C.St.J.A. Nash-Williams1
1Department of Mathematics University of Reading Whiteknights, P.O. Box 220 Reading RG6 6AF, England

Abstract

Let \(G\) be a finite strongly connected mixed graph (i.e., a graph with both undirected and directed edges, in which each vertex can be reached from every other vertex if directed edges can only be traversed in their direction of orientation). We establish a necessary and sufficient condition for it to be possible to transform some undirected edges of \(G\) into directed edges so that each vertex becomes the head of a prescribed number of newly directed edges and \(G\) remains strongly connected. A special case of this result yields a new proof (not requiring matroid techniques) of a necessary and sufficient condition for it to be possible to split each vertex of a finite connected graph into a prescribed number of vertices whilst preserving connectedness.