Definitions of Expander Graph

There are several different ways to measure the expansion properties of a finite, undirected multigraph G.

Edge Expansion

The edge expansion h(G) of a graph G is defined as

where the minimum is over all nonempty sets S of at most n / 2 vertices, and stands for the set of edges with exactly one endpoint in S.

Vertex Expansion

The α-vertex expansion g_α(G) of a graph G is defined as

where Γ(S) stands for the set of vertices with at least one neighbor in S. In a variant of this definition (called unique neighbor expansion) Γ(S) stands for the set of vertices in V with exactly one neighbor in S.