Is the following rephrasing correct? "Compute the number of simple graphs on $n$ vertices with specified vertex $P$ which contain a unique (edge-non-duplicating) path which begins at $P$ and passes through all vertices." One thing I am not clear on: if our path uses every bridge at most once, it forces the visits to be in order of decreasing population. Does this mean, for instance, if it is possible to visit the islands in the order 5-3-1-2-3-4 (so no duplicated edges, but multiple visits to the same island) the setup is bad? Or is that okay?

I think your reformulation is OK. But just one thing about the last condition: It's clear you can't pass through the same island twice, because the third condition says that each island of your path has less inhabitants that the former one. So you cannot have repeated islands in such a path

Did you find the problem uninteresting, or too easy? Please posts your solutions... I think the problem's nice...

Jutaro wrote: The Olimpia country is formed by $n$ islands. The most populated one is called Panacenter, and every island has a different number of inhabitants. We want to build bridges between these islands, which we'll be able to travel in both directions, under the following conditions: a) No pair of islands is joined by more than one bridge. b) Using the bridges we can reach every island from Panacenter. c) If we want to travel from Panacenter to every other island, in such a way that we use each bridge at most once, the number of inhabitants of the islands we visit is strictly decreasing. Determine the number of ways we can build the bridges. First of all, notice that any 3 islands in Olimpia can't be connect directly or indirectly by bridges. In words of the VIII OMCC they can´t be in a cycle (truth is I had 6 in this problem, I only mentioned cycles connectd directly). If this is breaked, we would be able to travel from Panacentro to another island "revealing against c)". After this, is easy to see: each island can olny be connect with exactly one island with more population, excep Panacentro. Let's denote with: $I_{1},I_{2},...,I_{n}$ each island, where if $i<j$ means $I_{i}$ has more population than $I_{j}$ and vice versa. Then: $I_{2}$ can be connect with only one island with more population, $I_{1}$ (Panacentro) $I_{3}$ can be connect with one of two islands with more population, $I_{1}$ or $I_{2}$ in general $I_{k}$ can be connect with one of $k-1$ islands We conclude there are $(n-1)!$ ways we can build the bridges.