-
Let
be the number of edges needed to separate from its complement. That is We define the edge conductance to be the ratio of the cut defined above with the smaller of
and . That is The graph conductance (also called isoperimetric number) is defined as
- Intuition: The isoperimetric number is a measure of the level of connectedness in the graph (and hence, how robust it is to edge deletion)
-
Cheeger’s Inequality Let
be an undirected graph and be the second smallest eigenvalue of the Laplacian matrix. Then