Minimum cuts, girth and a spectral threshold

Let G = (V, E) be a simple, undirected, unweighted, connected graph. A cut (A, (A) over bar) defined by a subset A of V is called trivial if either A or (A) over bar is a singleton set. Let mu be the second smallest eigenvalue of the Laplacian matrix of G. The length of the shortest cycle in the graph is called the girth g of the graph. Let the minimum degree of the graph be delta greater than or equal to 3. We show that if mu is greater than a threshold, namely 8delta/((delta - 1)([(g - 1)/2]) - 2), then every minimum cut in G is trivial. The proof is based on the observation that in graphs of large girth and minimum degree delta greater than or equal to 3, there exists a dichotomy of minimum cuts: Either the minimum cut is trivial or there must be a lot of vertices (Omega((delta - 1)([(g - 1)/2]))) on both sides of the cut. We illustrate that, for large enough values of g, the value obtained by us for this threshold is of the correct order by constructing a graph with girth at least g and minimum degree delta and mu = Omega(g(-1)(delta - 1)(-[(g - 1)/2])), but possessing a nontrivial minimum cut, assuming that a well-known conjecture about the existence of certain high girth graphs is true. Our results in this paper have the obvious algorithmic implication that when we have the a priori information that the value of mu for the given graph is greater than the threshold suggested by our theorems, the algorithmic problems of finding a minimum cut or enumerating all the minimum cuts in the graph becomes trivial. (C) 2003 Elsevier B.V All rights reserved.