Almost Every Randomly Near-Traceable Graph has Diameter at Most Two
Bing Zhou · SIAM Journal on Discrete Mathematics · 1988
Randomly near-traceable graphs are those graphs for which depth-first search can be completed with at most one backtracking. In this paper it is proved that every randomly near-traceable graph that is not a cycle has diameter at most two, thus confirming a conjecture of J. F. Fink. Some other special properties of randomly near-traceable graphs are also discussed.