In the exercise, you are to show that adding an expander to an arbitrary graph yields an expander.

Let $$G_1$$ and $$G_2$$ be $$d$$-regular graphs with the same set of vertices $$V$$. Construct a $$2d$$-regular graph $$H$$ by adding the edges of $$G_2$$ to $$G_1$$. Note that the normalized adjacency matrix of $$H$$ satisfies $$A_H = (A_{G_1} + A_{G_2})/2$$.

Suppose $$G_2$$ satisfies $$\lambda(G_2)\le 1-\e$$ for some $$\e>0$$. Show that then $$H$$ satisfies $$\lambda(H)\le 1-\e/2$$.

# Combinatorial characterization of positive spectral gap

Show that a regular graph $$G$$ is connected and non-bipartite if and only if $$\lambda(G)<1$$.

# Combinatorial expansion of random regular graphs

Do Exercise 21.11 in the textbook.