---
tag: Y7S6W12N64
kind: concept
name: Cheeger constant
msc: [05C50, 05C40, 05C48]
sources:
  - url: https://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory)
same_as:
  wikidata: Q5089262
  wikipedia: Cheeger constant (graph theory)
---

## Summary

The Cheeger constant of a finite graph measures its worst bottleneck.
It is the least ratio of the number of edges leaving a set of vertices to the size of the set.
The minimum runs over the sets with at most half of the vertices.
It is zero exactly for disconnected graphs, and it is large when every set of vertices has many edges to its complement.
It is also called the edge expansion or isoperimetric number, and bounded-degree graphs with Cheeger constant bounded below are [[expander graphs|DXJXVFV79H]].
The Cheeger inequalities compare it with the second smallest eigenvalue of the [[Laplacian matrix|TN6M6DVZRP]].

## Explanations

### L1 human

Try to cut a graph into two parts so that few edges cross the cut, while the smaller part is still big.
The Cheeger constant is the best ratio you can get: crossing edges divided by the size of the smaller part.
A long path has a tiny Cheeger constant, since one edge cuts it in half.
A complete graph has a large one, since every cut crosses many edges.