The Cheeger constant 
of a graph 
,
also called the Cheeger number, isoperimetric constant, or edge expansion constant
(Brouwer and Haemers 2012), is a measure of how hard it is to separate 
into two large pieces by cutting edges. Under one common convention,
the Cheeger constant is characterized by the minimum ratio of boundary edges to the
size of a vertex set of at most half the graph, namely
 |
where the edge boundary 
is defined by
 |
However, other conventions using slightly different normalizations are also in use.
A common normalized variant is graph conductance, which replaces the size of the vertex set by its volume, meaning the sum of the degrees of its vertices. For regular graphs, graph conductance is just the Cheeger constant divided by the common degree, but for irregular graphs, the two notions do not generally coincide.
The name "Cheeger constant" is also used for an analogous isoperimetric quantity in geometry, especially for Riemannian manifolds, of which the graph-theoretic notion is a discrete analog.
