Let's start with a few more definitions of degrees, maximum degree, and diameter of graphs. If two vertices are adjacent, they are called neighbors. The degree dG(x) of a vertex x in a graph G is the number of its neighbors. The diameter diam(G) of a connected graph G is the maximum occuring distance between vertices.
If a graph G has maximum degree Δ, then the state graph has maximum degree Δ as well. To any given state, with vertex x unoccupied, there are as many moves possible as x has neighbors in G. This equals the number of neighbors of that state in the state graph.
But the state graph is also very large---if the original graph has n vertices, then the state graph has n! = n · (n-1) · (n-2) · ... · 3 · 2 · 1 vertices. That, being huge with every vertex only few neighbors, implies that some vertices of the state graph must be very far apart. There must be states that are very far apart.
This follows from the Moore bound of graphs. If we have a connected graph with