In graph theory, the Cheeger constant of a graph 
, also called the Cheeger number, isoperimetric constant, or
edge edxpansion 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.
