Operate an aviation network without condition: Each city has a direct flight to 3 other cities; There is always a flight visiting all cities once each

Question

Problem. A country has $10$ cities. Operate an aviation network within $2$ following conditions:
a. Each city has a direct flight to exactly $3$ other cities.
b. From a beginning city, there is always a non-direct flight visiting all of other $9$ cities once for each.

My plan of solving.
I only can solve if the Original Problem has different things like:
New Problem. A country has $6$ cities. Operate an aviation network within $2$ following conditions:
a. $4$ cities, each of them has a direct flight to exactly $3$ other cities.
b. From a beginning city, there is always a non-direct flight visiting all of other $5$ cities once for each.
Construction.
Operate an aviation network among cities called $\mathsf{A}, \mathsf{B}, \mathsf{C}, \mathsf{D}, \mathsf{E}, \mathsf{F}.$ We obtain $$\begin{matrix} \mathsf{B}\rightleftharpoons\mathsf{A}, \mathsf{D}, \mathsf{E}, \mathsf{F} & \mathsf{C}\rightleftharpoons\mathsf{D}, \mathsf{E}, \mathsf{F}\\ \mathsf{F}\rightleftharpoons\mathsf{A}, \mathsf{B}, \mathsf{C} & \mathsf{E}\rightleftharpoons\mathsf{A}, \mathsf{B}, \mathsf{C}, \mathsf{D} \end{matrix}$$ Pairs $\mathsf{A}$ and $\mathsf{D}$ have the same role in this situation, similarly with pairs $\mathsf{B}$ and $\mathsf{C},$ pairs $\mathsf{E}$ and $\mathsf{F}.$
Without loss of generality, consider three paths:
Path $\mathsf{AB}$ and we just need to focus on four inner vertices $\mathsf{C}, \mathsf{D}, \mathsf{E}, \mathsf{F}$ $$\begin{matrix} \mathsf{B}\rightleftharpoons\mathsf{D}, \mathsf{E}, \mathsf{F} & \mathsf{C}\rightleftharpoons\mathsf{D}, \mathsf{E}, \mathsf{F}\\ \mathsf{F}\rightleftharpoons\mathsf{C} & \mathsf{E}\rightleftharpoons\mathsf{C}, \mathsf{D} \end{matrix}$$ $$\begin{matrix} \mathsf{B}\rightleftharpoons\mathsf{D}, \mathsf{E}, \mathsf{F} & \mathsf{C}\rightleftharpoons\mathsf{D}, \mathsf{E}\\ \mathsf{F}\rightleftharpoons\mathsf{C} & \mathsf{E}\rightleftharpoons\mathsf{C}, \mathsf{D} \end{matrix}$$ Routes: $\mathsf{BDECFA}, \mathsf{BEDCFA}$
Path $\mathsf{AE}$ and we just need to focus on four inner vertices $\mathsf{B}, \mathsf{C}, \mathsf{D}, \mathsf{F}$ $$\begin{matrix} \mathsf{B}\rightleftharpoons\mathsf{D}, \mathsf{F} & \mathsf{C}\rightleftharpoons\mathsf{D}, \mathsf{F}\\ \mathsf{F}\rightleftharpoons\mathsf{B}, \mathsf{C} & \mathsf{E}\rightleftharpoons\mathsf{B}, \mathsf{C}, \mathsf{D} \end{matrix}$$ $$\begin{matrix} \mathsf{B}\rightleftharpoons\mathsf{D} & \mathsf{C}\rightleftharpoons\mathsf{D}, \mathsf{F}\\ \mathsf{F}\rightleftharpoons\mathsf{B} & \mathsf{E}\rightleftharpoons\mathsf{B}, \mathsf{C}, \mathsf{D} \end{matrix}$$ $$\begin{matrix} \mathsf{B}\rightleftharpoons\mathsf{D} & \mathsf{C}\rightleftharpoons\mathsf{D}, \mathsf{F}\\ \mathsf{F}\rightleftharpoons\mathsf{B} & \mathsf{E}\rightleftharpoons\mathsf{C}, \mathsf{D} \end{matrix}$$ Routes: $\mathsf{ECDBFA}, \mathsf{EDBFCA}$
Path $\mathsf{BE}$ and we just need to focus on four inner vertices $\mathsf{A}, \mathsf{C}, \mathsf{D}, \mathsf{F}$ $$\begin{matrix} \mathsf{B}\rightleftharpoons\mathsf{A}, \mathsf{D}, \mathsf{F} & \mathsf{C}\rightleftharpoons\mathsf{D}, \mathsf{F}\\ \mathsf{F}\rightleftharpoons\mathsf{A}, \mathsf{C} & \mathsf{E}\rightleftharpoons\mathsf{A}, \mathsf{C}, \mathsf{D} \end{matrix}$$ Routes: $\mathsf{EAFCDB}, \mathsf{EDCFAB}$
Comment. I just write two routes for each. My way of thinking is totally bad, so many unnecessary moves here. Even that, I can't applied it for the Original Problem. I can't continue with the idea..
Inspiration.
The combinations of matches in the round of $16$ here inspired me. Does it work ? I need to the help.
Edit (07/11/21). I describe my operation by this big picture $$\begin{matrix} \mathsf{flight} & A & B & C & D & E & F & G & H & I & J\\ A & \times & & \times & \times & \times & & \times & \times & \times & \\ B & & \times & & \times & \times & \times & & \times & \times & \times\\ C & \times & & \times & & \times & \times & \times & & \times & \times\\ D & \times & \times & & \times & & \times & \times & \times & & \times\\ E & \times & \times & \times & & \times & & \times & \times & \times & \\ F & & \times & \times & \times & & \times & & \times & \times & \times\\ G & \times & & \times & \times & \times & & \times & & \times & \times\\ H & \times & \times & & \times & & \times & \times & \times & & \times\\ I & \times & \times & \times & & \times & & \times & \times & \times & \\ J & & \times & \times & \times & & \times & & \times & \times & \times\\ \mathsf{route(s)} & A & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc \end{matrix}$$ Its validation is shown by the main diagonal line, hence, we just need to work with the upper bound. The original conditions all here, let's start with the flight $\mathsf{AB}$ $$\begin{matrix} \mathsf{flight} & A & B & C & D & E & F & G & H & I & J\\ A & \times & \times & \times & \times & \times & & \times & \times & \times & \\ B & & \times & & \times & \times & \times & & \times & \times & \times\\ C & & & \times & & \times & \times & \times & & \times & \times\\ D & & & & \times & & \times & \times & \times & & \times\\ E & & & & & \times & & \times & \times & \times & \\ F & & & & & & \times & & \times & \times & \times\\ G & & & & & & & \times & & \times & \times\\ H & & & & & & & & \times & & \times\\ I & & & & & & & & & \times & \\ J & & & & & & & & & & \times\\ \mathsf{route(s)} & A & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc & B \end{matrix}$$ $$\begin{matrix} \mathsf{flight} & A & B & C & D & E & F & G & H & I & J\\ A & \times & \times & \times & \times & \times & \checkmark & \times & \times & \times & \times\\ B & & \times & & \times & \times & \times & & \times & \times & \times\\ C & & & \times & & \times & \times & \times & & \times & \times\\ D & & & & \times & & \times & \times & \times & & \times\\ E & & & & & \times & & \times & \times & \times & \\ F & & & & & & \times & & \times & \times & \times\\ G & & & & & & & \times & & \times & \times\\ H & & & & & & & & \times & & \times\\ I & & & & & & & & & \times & \\ J & & & & & & & & & & \times\\ \mathsf{route(s)} & A & F & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc & B \end{matrix}$$ $$\begin{matrix} \mathsf{flight} & A & B & C & D & E & F & G & H & I & J\\ A & \times & \times & \times & \times & \times & \checkmark & \times & \times & \times & \times\\ B & & \times & & \times & \times & \times & & \times & \times & \times\\ C & & & \times & & \times & \times & \times & & \times & \times\\ D & & & & \times & & \times & \times & \times & & \times\\ E & & & & & \times & \times & \times & \times & \times & \\ F & & & & & & \times & \checkmark & \times & \times & \times\\ G & & & & & & & \times & & \times & \times\\ H & & & & & & & & \times & & \times\\ I & & & & & & & & & \times & \\ J & & & & & & & & & & \times\\ \mathsf{route(s)} & A & F & G & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc & \bigcirc & B \end{matrix}$$ $$\begin{matrix} \mathsf{flight} & A & B & C & D & E & F & G & H & I & J\\ A & \times & \times & \times & \times & \times & \checkmark & \times & \times & \times & \times\\ B & & \times & \checkmark & \times & \times & \times & \times & \times & \times & \times\\ C & & & \times & & \times & \times & \times & & \times & \times\\ D & & & & \times & & \times & \times & \times & & \times\\ E & & & & & \times & \times & \times & \times & \times & \\ F & & & & & & \times & \checkmark & \times & \times & \times\\ G & & & & & & & \times & \checkmark & \times & \times\\ H & & & & & & & & \times & & \times\\ I & & & & & & & & & \times & \\ J & & & & & & & & & & \times\\ \mathsf{route(s)} & A & F & G & H & \bigcirc & \bigcirc & \bigcirc & \bigcirc & C & B \end{matrix}$$ $$\begin{matrix} \mathsf{flight} & A & B & C & D & E & F & G & H & I & J\\ A & \times & \times & \times & \times & \times & \checkmark & \times & \times & \times & \times\\ B & & \times & \checkmark & \times & \times & \times & \times & \times & \times & \times\\ C & & & \times & \checkmark & \times & \times & \times & \times & \times & \times\\ D & & & & \times & & \times & \times & \times & & \times\\ E & & & & & \times & \times & \times & \times & \times & \\ F & & & & & & \times & \checkmark & \times & \times & \times\\ G & & & & & & & \times & \checkmark & \times & \times\\ H & & & & & & & & \times & \checkmark & \times\\ I & & & & & & & & & \times & \\ J & & & & & & & & & & \times\\ \mathsf{route(s)} & A & F & G & H & I & \bigcirc & \bigcirc & D & C & B \end{matrix}$$ $$\begin{matrix} \mathsf{flight} & A & B & C & D & E & F & G & H & I & J\\ A & \times & \times & \times & \times & \times & \checkmark & \times & \times & \times & \times\\ B & & \times & \checkmark & \times & \times & \times & \times & \times & \times & \times\\ C & & & \times & \checkmark & \times & \times & \times & \times & \times & \times\\ D & & & & \times & \checkmark & \times & \times & \times & \times & \times\\ E & & & & & \times & \times & \times & \times & \times & \checkmark\\ F & & & & & & \times & \checkmark & \times & \times & \times\\ G & & & & & & & \times & \checkmark & \times & \times\\ H & & & & & & & & \times & \checkmark & \times\\ I & & & & & & & & & \times & \checkmark\\ J & & & & & & & & & & \times\\ \mathsf{route(s)} & A & F & G & H & I & J & E & D & C & B \end{matrix}$$ Done. We need to do the same thing with the flights $\mathsf{AC}$ and $\mathsf{AD}$ here. I can do end my work, huh ? And how about my plan ? Just let your comment here.

Answer 1

The question is somewhat unclear and admits different answers depending on how we understand the condition (b) "There is always a non-direct flight visiting all of 10 cities once each.". I'll provide two such interpretations and the corresponding answers; hopefully at least one of them will match the intended one.

In order to simplify matters, let the cities be named $C_i$ with $0\leq i<10$, where the indices are considered modulo $10$ (i.e. $C_{10}$ is the same as $C_{0}$).

Now, if the condition (b) means: "For every pair of cities $X$ and $Y$ that are connected by a direct flight, there is a sequence of nine flights which starts in $X$, ends in $Y$ and visits every city once." (in graph-theoretical language, it corresponds to a Hamiltonian path), we can use direct flight from every $C_i$ to $C_{i-1}$, $C_{i+1}$ and $C_{i+5}$. This construction has a very high level of symmetry; if we increase/decrease (modulo $10$) the numbers of all cities by the same amount, the resulting network of flights will look exactly the same. In other words, no city is "privileged" and it suffices to check the direct flights from $C_0$ and find the corresponding Hamiltonian paths for the three of them. This can be done as follows:

• $C_0-C_1$ can be flown indirectly as $C_0-C_9-C_8-C_7-C_6-C_5-C_4-C_3-C_2-C_1$,
• $C_0-C_9$ can be flown indirectly as $C_0-C_1-C_2-C_3-C_4-C_5-C_6-C_7-C_8-C_9$ and
• $C_0-C_5$ can be flown indirectly as $C_0-C_1-C_2-C_3-C_4-C_9-C_8-C_7-C_6-C_5$.

---

However, the condition (b) can also be interpreted even more strictly. Rather than requiring a Hamiltonian path between all pairs of cities that are connected by direct flights, it can require the path to exist between all pairs. In other words: "For every pair of cities $X$ and $Y$, there is some sequence of nine flights which starts in $X$, ends in $Y$ and visits every city once."

Unfortunately, the symmetry of the solution will not be as great as in the previous case. We will still connect $C_i$ to $C_{i-1}$ and $C_{i+1}$ but the third flight from each city will go to $C_{10-i}$ if $i$ is not equal to $0$ or $5$ (it would result in a flight from the city back to itself in these two cases). These two remaining cities, $C_0$ and $C_5$, will be connected by a direct flight.

If we renumber all the cities by changing $C_i$ to $C_{10-i}$, we obtain the same network of flights. The same happens if we replace $C_i$ by $C_{i+5}$. This symmetry allows quite nice reduction in the number of different pairs of cities we need to find the Hamiltonian paths for. We can start by considering these two Hamiltonian cycles (a close path that ends in the same city it started from and which visits every city once): $$C_0-C_1-C_9-C_8-C_2-C_3-C_7-C_6-C_4-C_5-C_0$$ $$C_0-C_9-C_1-C_2-C_8-C_7-C_3-C_4-C_6-C_5-C_0$$ Each of the existing direct flights exists on at least one of them. Thus, if we are considering any pair of cities that are connected by direct flights, we can simply take a cycle which contains that flight and remove the flight connecting those two cities from it; which will result in a Hamiltonian path connecting those two cities. We have thus shown that this solution at least satisfies the weaker interpretation of condition (b); the one which we considered above.

Now we only need to deal with the non-directly-connected pairs of cities. For $C_0$, we only need to consider $C_2$ and $C_3$ and $C_4$; the remaining ones are covered by symmetry. We have the following paths:

• $C_0-C_2$ can be flown as $C_0-C_1-C_9-C_8-C_7-C_6-C_5-C_4-C_3-C_2$,
• $C_0-C_3$ can be flown as $C_0-C_9-C_1-C_2-C_8-C_7-C_6-C_5-C_4-C_3$ and
• $C_0-C_4$ can be flown as $C_0-C_1-C_9-C_8-C_2-C_3-C_7-C_6-C_5-C_4$.

For $C_1$, we have six cases to consider:

• $C_1-C_3$ can be flown as $C_1-C_2-C_8-C_9-C_0-C_5-C_4-C_6-C_7-C_3$,
• $C_1-C_4$ can be flown as $C_1-C_2-C_3-C_7-C_8-C_9-C_0-C_5-C_6-C_4$,
• $C_1-C_5$ can be flown as $C_1-C_2-C_3-C_4-C_6-C_7-C_8-C_9-C_0-C_5$,
• $C_1-C_6$ can be flown as $C_1-C_2-C_3-C_7-C_8-C_9-C_0-C_5-C_4-C_6$,
• $C_1-C_7$ can be flown as $C_1-C_2-C_8-C_9-C_0-C_5-C_6-C_4-C_3-C_7$ and
• $C_1-C_8$ can be flown as $C_1-C_9-C_0-C_5-C_4-C_6-C_7-C_3-C_2-C_8$.

Finally for $C_2$ we have another four cases (since $C_2-C_0$ has been covered already and $C_2-C_9$ is equivalent to $C_1-C_8$):

• $C_2-C_4$ can be flown as $C_2-C_3-C_7-C_8-C_9-C_1-C_0-C_5-C_6-C_4$,
• $C_2-C_5$ can be flown as $C_2-C_3-C_4-C_6-C_7-C_8-C_9-C_1-C_0-C_5$,
• $C_2-C_6$ can be flown as $C_2-C_3-C_7-C_8-C_9-C_1-C_0-C_5-C_4-C_6$ and
• $C_2-C_7$ can be flown as $C_2-C_8-C_9-C_1-C_0-C_5-C_6-C_4-C_3-C_7$.

This covers all the possible cases; since $C_1$, $C_9$, $C_4$ and $C_6$ behave the same due to symmetry; so does the quadruplet $C_2$, $C_8$, $C_3$, $C_7$; and also the pair $C_0$ with $C_5$.

All of these flights are quite easy to visualize if the cities are drawn as equally spaced points on a circle; with $C_0$ being the top point of it and $C_5$ being the bottom. The flights are then circle arcs between pairs of consecutive cities, along with one vertical chord (connecting $C_0$ and $C_5$) and four horizontal ones. In fact, the same approach can be generalized to any even number of cities; the Hamiltonian paths we seek are formed mostly by zig-zagging from one side of the circle to the other and back.