Spectral bisection of graphs and connectedness

We present a refinement of the work of Miroslav Fiedler regarding bisections of irreducible matrices. We consider graph bisections as defined by the cut set consisting of characteristic edges of the eigenvector corresponding to the smallest non-zero eigenvalue of the graph Laplacian (the so-called Fiedler vector). We provide a simple and transparent analysis, including the cases when there exist components with value zero. Namely, we extend the class of graphs for which the Fiedler vector is guaranteed to produce connected subgraphs in the bisection. Furthermore, we show that for all connected graphs there exist Fiedler vectors such that connectedness is preserved by the bisection, and estimate the measure of the set of connectedness preserving Fiedler vectors with respect to the set of all Fiedler vectors.