Can this problem be solved by graph theory? A nation has A airports with 1 in each city. Each city has direct flights to 3 other cities, and each of them has a return flight. Also, people can fly from a city to another with 1 layover at most. What is the maximum value of A?
 A: Here's a solution with 10 nodes:

A: Consider one city, Startville. From here there are three flights to cities Alpha, Bravo and Charlie, and from those three cities there are two more cities that could be connected (because there is a flight back to Startville also for those cities). So the limit is definitely no more than $1+3+6=10$ cities, but is that many possible?
Alpha, Bravo and Charlie are already connected under the one-layover rule, via Startville, but what about the cities beyond them? We can easily arrange for $3$ such cities, Foxtrot, Golf and Hotel, just connected in a triangle, which leaves a "spare" connection at Alpha, Bravo, Charlie for a fourth city Xanadu. So I can get $8$:

BUT
I don't promise that it is the maximum. $8$ is demonstrated, $10$ is an upper limit. 

Edit to add: And of course @DonaldSputterwit reminds me in the comments that if you want a small cubic graph with unusual properties the Petersen graph is always worth looking at:

which does the trick for the maximum $10$ cities. 
