Vtyjkyuk

The frog game on a graph:

• Default start of the game is placing one frog on each node (vertex).


• The goal is to move all the frogs to one single node.


• A single move consists of moving all $n$ frogs from node $A$ to nonempty node $B$, which is allowed only if there exists a path from $A$ to $B$ containing exactly $n$ unique edges. Node $B$ is called nonempty if there is at least one frog on it.


• If it is possible for all frogs to end up on some node $N$ (the game is solvable), then that implies that the frog on node $N$ never moves during the game (during one of possible solutions), hence that node is called a lazy toad.

Given a tree with one frog per node, how can one tell if the frog game is solvable on it or not?

How can one determine which nodes will be lazy toads?

Fully solving the simplest case ($2$-leaf trees)

If our graph is the simplest tree, a case with only $2$ leaves, then the frog game is trivial.

For example, if we have $7$ nodes:

We can move frogs as: $Drightarrow E rightarrow C rightarrow F rightarrow B rightarrow G rightarrow A$ to solve it by simply jumping back and forth from the middle node $D$ to end up at $A$. Or if the first move was $Drightarrow C$, end up at $G$.

It is clear that in the case of any $n$ node tree with $2$ leaves, the game is solvable applying this method; and the leaves are trivial lazy toads ($A$ and $G$ in the above example).

From this it follows that every other node is a lazy toad as well: Any $n$ node case with $2$ leaves can be split into two such smaller cases connected at selected node. For example, we can split the above example at $C$ and solve $A-B-C$ at $C$ and solve $C-D-E-F-G$ at $C$, which solves the entire thing at $C$.

This case is basically the Frog Jumping game showed on Numberphile.

After seeing the frog jumping, I wanted to try it on graphs.

Solving $3$-leaf trees

The fact that every node on a $2$-leaf tree is a lazy toad gives us a trivial lazy toad on every $3$-leaf tree, which means that this case is always solvable as well. We can split every $3$-leaf case into two $2$-leaf cases and solve at the intersection. For example:

Here node $D$ is the trivial lazy toad. We can solve $A-B-C-D-F$ and $D-E-G$ at $D$.

But I'm not sure how can we tell which nodes are not lazy toads in the $3$-leaf case?

In the above $3$-leaf example, all nodes are lazy toads (solved it at every node).

But in the following $3$-leaf example, all nodes except $D$ are lazy toads:

(brute force checked by trying all possible frog moving sequences)

So sometimes not all nodes in a $3$-leaf case are lazy toads, unlike the $2$-leaf case.

Trivial $k$-leaf tree case

If our tree consists of $k$ $2$-leaf trees all joined in a single node (common leaf - a node of degree $k$ if observed on the graph as a whole), then that single node is a trivial lazy toad and the game is solvable.

If all of those $k$ trees are $2$-node trees, then trivial toad is the only lazy toad (blue node). Examples:

But if those $2$-leaf trees are not simple $2$-node trees but have more nodes, then we can have more lazy toads in some cases:

Here trivial lazy toad is colored green, other lazy toads are blue, and non-lazy nodes are red.

Other than those easy cases, how can we in general tell if some
tree(s) will be solvable or not?

Can nontrivial lazy toad nodes be found faster or in a better way other than brute force check?

Brute-force solving small examples

I have brute-force checked all trees with $9$ or less nodes, and out of $1+1+1+2+3+6+11+23+47=95 $ unlabeled trees, only $5$ are not solvable:

I have decided to sort trees based on the amount of leaves:

• We've already shown $2$-leaf trees are always fully-lazy.




• The $3$-leaf trees seem to always be fully-lazy except for this particular type of those trees, where only one same node is not lazy (and except for the 4 node case with only one lazy toad):

If we can show that $3$-leaf trees with $ngt4$ nodes are always fully-lazy except when they are of the type seen in this image, then this fact can be used to prove trivial lazy toads on $4$-leaf trees.

The idea is to prove the similar facts for other cases as well, so one can then prove more trivial lazy toads for more cases;

• $4$-leaf trees are sometimes fully-lazy, and sometimes have one, two or more non-lazy toads.
  They seem to always be solvable.




• $5$-leaf trees have no fully-lazy examples among cases with $9$ nodes or less. Similarly to $4$-leaf trees, we have cases with one, two, three, or more non-lazy toads.
  They seem to always be solvable as well.




• $6$ and $7$ leaf trees have few unsolvable cases so far as already shown above, and as for $8$ or more leaf trees, I have only one (trivial) example since I've solved only trees with $9$ or less nodes with brute force, so far.

Some observations based on observing the frog game on solvable trees:

It seems that every set of $k$-leaf trees should have only finitely
many unsolvable cases.

Looks like $k$-leaf trees with $n$ nodes will all be solvable for
sufficiently large $n_0$ such that $nge n_0$

If that is true, one could try to find and prove all unsolvable cases for given set of $k$-leaf trees?