algorithm for approximating the expansion of $G$ and giving a corresponding partition of the vertices.

\[th:cheeger\] For any graph $G$, we have $\frac{\lambda_2}{2}\leq \Phi(G) \leq \sqrt{2 \lambda_2}$ and there is an algorithm that finds $S\subseteq V$ such that $\Phi(S) \leq \sqrt{2 \lambda_2}$ in time polynomial in $n=|V(G)|$. In particular, $\Phi(G) \geq \Phi(S)^2/4$.

The inequality $\frac{\lambda_2}{2}\leq \Phi(G) \leq \sqrt{2 \lambda_2}$ is often referred to as Cheeger’s inequality. There is an analogue of Cheeger’s inequality for the largest eigenvalue $\lambda_n$ and the *bipartiteness ratio* $\beta(G)$. For $y\in \{-1,0,1\}^{V(G)}\setminus \{\textbf{0}\}$ we define $$\beta(y):= \frac{\sum_{uv\in E(G)} |y_u+y_v|}{\sum_{v\in V(G)} d_G(v)  |y_v|}$$ and $\beta(G):= \min_{y\in \{-1,0,1\}^V\setminus \{\textbf{0}\}} \beta(y)$. We can think of a small value $\beta(G)$ to mean that $G$ is close to bipartite. In particular, if we set $A = \{v \in V(G): y_v = 1\}$ and $B = \{v \in V(G): y_v = -1\}$ then $$\label{eq:beta}
\beta(y)= \frac{2e_G(A) + 2e_G(B) + e_G(A\cup B, V(G) \setminus (A \cup B))} {{\text{vol}}_G(A \cup B)}.$$

\[th:trevisan\] For any graph $G$, we have $\frac{2-\lambda_n}{2}\leq\beta(G)\leq\sqrt{2(2-\lambda_n)}$ and there is an algorithm that finds $y\in \{-1,0,1\}^{V(G)}$ such that $\beta(y)\leq\sqrt{2(2-\lambda_n)}$ in time polynomial in $n=|V(G)|$. In particular, $\beta(G) \geq \beta(y)^2 /4$

The algorithms from both Theorem \[th:cheeger\] and \[th:trevisan\] run in time $O(|E(G)|+|V(G)|\log|V(G)|).$

