1.1 Basic Definitions

A graph, G = ( V, E, ?) , consists of a vertex-set V, edge-set E and boundary-function ? : which identifies the pair of vertices (not necessarily distinct) incident to each edge. Graphs are often represented by diagrams where vertices are points, and edges are curves connecting the pair of incident vertices. For any graph G, and S ? V, we define

and call it the edge-boundary of S. Then given a graph G, and k ? ⁺, the edge-isoperimetric problem (EIP) is to minimize ? ( S) over all S ? V such that S = k. Note that ? ( S) is an invariant, i.e. if : G ? H is a graph isomorphism, then ? S ? V _G, ? ( ( S)) = ? ( S). Thus subsets of vertices which are equivalent under an automorphism will have the same edge-boundary.

Loops, i.e. edges incident to just one vertex, are irrelevant to the EIP so we shall ignore them. Most, but not all, of our graphs will be ordinary graphs, i.e. having no loops and no more than one edge incident to any pair of vertices. The representation of an ordinary graph may be shortened to ( V, E), where , and ?