In this paper a tight lower bound for algebraic connectivity of graphs
(second smallest eigenvalue of the Laplacian matrix of the graph) based on
connection-graph-stability method is introduced. The connection-graph-stability
score for each edge is defined as the sum of the length of all the shortest
paths making use of that edge. We prove that the algebraic connectivity of the
graph is lower bounded by the size of the graph divided by the maximum
connection graph stability of the edges.