The King needs your help (the end!)

For the graph to be viable, it must not contain the following sub-graphs (most of this was discussed in earlier iterations of this problem):

Loops (place 1 person in each city on the loop for a break-even situation)...thus the graph must be a tree,

Cities with 4 or more neighbors (place 2 people in the central city and 1 person in 4 of its neighbors for a break -even situation).

More than 1 city with 3 neighbors. Indeed, if we had 2 cities A and B with 3 neighbors each, we could place 2 people in each of these cities as well as all the cities along the road connecting them. Also, we place 1 person in each of the 4 neighbors of A and B besides the 2 that have already been populated, again, making for a break-even situation.

Thus we may assume, without loss of generality, that we have 1 central city, C, and 3 roads of various lengths emanating from C. Let's say that these three roads involve m, n, and p cities, respectively, not counting the central city, C. We may assume that $n\leq{m}\leq{p}$ .

If we complete the squares of our quadratic form, starting at the ends of the three roads and working our way towards the center, the coefficient of the central city ends up being $c=1-\frac{n}{2n+2}-\frac{m}{2m+2}-\frac{p}{2p+2}$ (we leave this as an exercise to the reader; obviously, it suffices to do the computation for one of the roads). The graph will be viable if (and only if) this coefficient c is positive.

If $n\geq2$ , then $c\leq0$ , so that the plan isn't viable... thus we must have $n=1$ .

We already know the solutions $n=m=1$ , with arbitrary p... that's one of the "boring" solutions.

If $m\geq3$ , then $c\leq0$ , so that the plan isn't viable... thus we must have $m=2$ to get a "new solution"

Now $c=1-\frac{1}{4}-\frac{1}{3}-\frac{p}{2p+2}=\frac{5}{12}-\frac{p}{2p+2}$ , which is positive for $p=2,3,4$ . There are $\boxed{3}$ graphs that work, besides the "boring" ones.

With this playful example, we have taken a look at an important and well-understood branch of algebra... the graphs we found are the Dynkin Diagrams , and the quadratic form we studied is the Tits Form.

Hi again. I didn't see this ^^ post right away (this is the only one of the three threads that I'm not subscribed to). Nice solution. :)

Interestingly, my approach was a lot different, but ultimately boilded down to the same expression $1- \frac{n}{2n+2}- \frac{m}{2m+2}- \frac{p}{2p+2}$ that you have. (Btw, I think you meant to put $n \le m\le p$ .)