Proof of a conjecture on the algebraic connectivity of a graph and its complement

Abstract

For a graph $G$, let ${\lambda }_2(G)$ denote its second smallest Laplacian eigenvalue. It was conjectured that ${\lambda }_2(G)+{\lambda }_2(\overline{G})\ge 1$, where $\bar{G}$ is the complement of $G$. Here, we prove this conjecture in the general case. Also, we will show that $\max \{{\lambda }_2(G),{\lambda }_2(\overline{G})\}\ge 1-O(n^{-\frac{1}{3}})$, where $n$ is the number of vertices of $G$.