I’m working on a computer game in which the spaces that players can occupy are connected to other spaces by exactly three pathways, always. I wrote a quick-and-dirty program which does lots of brute-force random connections among N spaces and averages the results to tell me how “far away” two spaces can be from one another given N spaces, but I was wondering if this had already been determined, in terms of the number of different arrangements possible.

So, given a number (N) of spaces (S), each of which must have three pathways § connecting to different other S (in other words, S[sub]A[/sub] cannot connect to S[sub]B[/sub] via more than one P), how many three-dimensionally, *topologically different* arrangements of Ss and Ps are possible? Is there already a formula with the answer?

What I know so far is that N must always be an even number to satisfy the “exactly 3 P from each S, no duplicates” requirement, N must be at least 4, and that if N is 4, the only possible arrangement is one in which each S is at the tip of a tetrehedron, each P being an edge. After scratching for a while with paper and pencil, I’m fairly certain that if N is 6, there is also only one configuration (imagine two triangles floating parallel to each other, their vertices connected by 3 more Ps). If N is 8, I *think* the number of possibilities is more than 1, but I’m not quite sure. And if N is 10, I’m pretty sure there’s more than one configuration which works, but I don’t have a clue as to how many configurations there really are (2? 3? More?).

This is mostly asked in curiosity, right now, since I can continue to brute-force random networks of Ss and Ps to my heart’s content. But I was thinking about this because I thought it might be interesting to make sure that getting from one particular S to another would take at *least* X pathways, and was wondering how much N would need to be to *force* a minimum traverse of X Ps.

Yeah, the question is, given N Ss, what is the maximum *mininum* number of Ps which must be traversed between two Ss (let’s call this value M), given an optimally “tight” arrangement of Ss and Ps? By “tight” I mean “minimizing the value of M,” since it’s fairly obvious that it’s easy to maximize M by arranging the Ss and Ps for a high-N network…

Oh, my brute-force program came up with an “answer” of M=16 when N=2000, if that helps at all. Of course, it came up with M=15 for N=1990, but M=16 again for something like N=1970, too, so the random-brute-force-and-averaging method doesn’t exactly “work” in any deterministic sort of sense, which is what I’m looking for.