optimization - A perfect metro map

You are working for a company and asked to create a perfect metro map where there will be as many stops as possible. But there are two constraints which limits the number of tracks (railroads) and maximum number of stations between one station to another one:

• There are at most $3$ tracks (railway) from one stop to others since it is not wanted to dig the underground too much and have the least amount of railways.


• The maximum number of stations between destination and departure stations is limited as $1$. So you can go from one station to another one with only seeing other $1$ different stations. In other words, if you move from one station (departure), there has to be at most $1$ stations between departure to destination.


• The tracks on the map can overlap to each other, since it is underground you can adjust the depth of the tunnels accordingly.

For example, if this question is asked for at most $3$ tracks with the maximum number of stations between stations as $0$ (no station between destination and departure stops), the answer would be 4 stations at most as seen below:

Answer

[EDITED: the original puzzle has been amended from "at most 4 stations between any two" to "at most one station between any two" which makes it no longer a research problem because the answer is already known. See below.]

I think this is a pure mathematical research problem in the guise of a puzzle. (Hence, no spoiler markings.)

This question asks for the largest graph with all degrees $\leq3$ and diameter $\leq5$. There is an easy upper bound on this, called the "Moore bound". Start at any vertex and start walking. You can reach 3 vertices after one step, then at most another 6 after the next, at most another 12 after the next, and so on. Even if these are all different -- i.e., the only way to repeat a vertex by this process, when walking as far as the diameter of the graph, is to retrace your steps exactly -- we can find at most 1+3+6+12+24+48=94 vertices this way.

It's been known for ages that this bound (call it $M$) can't be attained for cubic graphs. The answer can't be exactly $M-1$ for parity reasons. It was proved by Leif Jørgensen that it can't be $M-2$ either. Nor can it be $M-3$, again for parity reasons. So the most we could hope for is 90 vertices.

(That's for actual cubic graphs. Perhaps one can do a little better when, as here, we are allowed graphs of degree at most 3 rather than exactly 3. I suspect one can't, and I bet that if one can it's by only one or two vertices, but I haven't tried to prove that.)

The best actually found as of 2009 has 70 vertices. I had a brief look on the web and didn't find any descrption of the actual graph, but the paper you need is by Alegre, Fiol, and Yebra. From another table on that page it appears that no upper bound better than the one in the previous paragraph is known, but maybe I'm misunderstanding because the upper bound in the table is just the Moore bound, which is known not to be optimal for cubic graphs.

[EDIT: Here is what happens for diameter 2, the case now in the puzzle statement.]

When we allow at most one station between two others -- diameter 2, in graph-theory lingo -- the solution is the famous

Petersen graph (with 10 vertices)

which looks like this: