Sufficient Conditions for Circuits in Graphs †

Certain lower bounds on the valencies of the vertices in a graph, and/or on the total number of edges, suffice to ensure the existence in the graph of a circuit of at least, or exactly, a certain specified length. Many theorems of this type are listed, some old and some new. The culminating result on undirected graphs shows how many edges are needed in a graph on n vertices, with minimal valency at least k , in order to ensure the existence of a circuit of length exactly n − r . (Erdös mentioned the case k = 0, as an unsolved problem, in 1969: see [5].) A few of these results have been extended to directed graphs. The main extension proved here is that if G is a directed graph on n vertices, in which ρ out (a) + ρ in (b) ⩾ n for every pair of distinct vertices a and b such that a is not joined to b (by an edge of G ), then G has a (directed) Hamiltonian circuit.