Overview

Why infinite graphs? The EIP, or any of its variants, would not seem suited to infinite graphs. On finite graphs we can always find a solution by brute force, evaluating ? ( S) for all 2 ^V subsets of vertices. Even so, the finite problem is NP-complete, an analog of undecidability, and on infinite graphs it is very likely undecidable. Certainly there is no apparent solution.

The primary motivation for considering the EIP on infinite graphs is to develop global methods. Problems are the life blood of mathematics and there are some very large, i.e. finite but for all practical purposes infinite, graphs for which we would like to solve the EIP. The 120-cell, an exceptional regular solid in four dimensions, is the only regular solid for which we have not solved the EIP. It has 600 vertices so we prefer to call it the 600-vertex, V ₆₀₀. Another is the graph of the n-permutohedron, n ? 4, which has n! vertices. Solving those problems will require developing better methods than we have now. The regular tessellations of Euclidean space are relatively easy to work with but present some of the same kinds of technical problems as those higher dimensional semiregular and exceptional regular solids.

There are also problems arising in applications which bring us to consider isoperimetric problems on infinite graphs. The original application, solving a kind of layout problem if G is regarded as representing an...