1. ## Travelling problem/puzzle

In Flyland, each city has 2-way direct flights to a maximum of 3 other cities.
Every city is reachable from every other city with at most 3 flights.
What is the maximum number of cities in Flyland?

I get 20. Anybody beat that?

2. ## Re: Travelling problem/puzzle

what is a 2-way direct flight?

a touch and go and returning?

but seriously does this mean that if $(a,b)$ exists then $(b,a)$ exists and doesn't count as one of $b$'s flights?

3. ## Re: Travelling problem/puzzle

I think he means that if you can fly from A-to-B you can also fly from B-to-A. And that the route counts as one of the 3 available flights to A and also as one of the three available to B. But I must say, after noodling on this for a few minutes I can't get anywhere near twenty cities.

4. ## Re: Travelling problem/puzzle

Originally Posted by DenisB
In Flyland, each city has 2-way direct flights to a maximum of 3 other cities.
Every city is reachable from every other city with at most 3 flights.
What is the maximum number of cities in Flyland? I get 20. Anybody beat that?
This is rather simple problem about connected graphs. However, I am not sure that any such graph can exist.
It appears that the degree of any vertex has a minimum of one and a maximum of three.
One of the most important theorems in graph theory is: $m\le \dfrac{2\|\mathscr{E}\|}{\|\mathscr{V}\|}\le M$.
That says the minimum vertex-degree is less than or equal to twice the number of edges divided the number of vertices which is less or equal to the maximum vertex-degree.
I cannot make your twenty work.
Here are two more graph facts:
There must be at least two vertices of the same degree and an even number of odd vertices.

5. ## Re: Travelling problem/puzzle

Graph (c) on page 14 of this document is the solution:

http://www.combinatorics.org/ ojs/index.php/eljc/article/ view/DS14/pdf

6. ## Re: Travelling problem/puzzle

The correct URL is this:

Moore Graphs and Beyond: A survey of the Degree/Diameter Problem | Miller | The Electronic Journal of Combinatorics

Below is the graph - but note that there are nodes with as many as six connections, which violates the premise of the puzzle (three 2-way connections per city). A better description would have been "there are at most 3 flights that may depart from any city, but an unlimited number of flights may terminate in a city."