What's the conditions for equality of Cheeger inequality?

Question

I have learnt the Cheeger inequality for a graph $G$:

$$\lambda_2/2\le h(G)\le\sqrt{2\lambda_2}.$$

But does the equality hold? For a non-connected graph, it is obvious. But for a connected graph, I have tried some examples and find the first equality may hold, but fail at the second one. Are there any conditions for equality of Cheeger inequality?

Answer 1

Equality holds in the Cheeger inequality under certain conditions. Specifically, equality holds if and only if the graph $G$ is a regular graph or a bipartite graph. Regular graphs are graphs where every vertex has the same degree, and bipartite graphs are graphs where the vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex in the other set.

• Equality holds in the Cheeger inequality for regular graphs.
• Equality holds in the Cheeger inequality for bipartite graphs.

For general connected graphs, equality may not hold, as you observed in your examples.