Possible Increasing Paths in Cubes

We claim the minimum number of paths is 8. Indeed, 8 can be achieved; label the top face 5-7-6-8 and the bottom face 9-11-10-12, and have paths 1, 2, 3 and 4 connecting them (anything unspecified doesn't matter). Clearly, no path can have its middle edge one of the 1,2,3,4 edges, and no path can lie entirely within the top of bottom face. This gives 4 paths with two edges in the top face, and 4 with two in the bottom face, and thus 8 in total.

To show that there must be 8, consider a vertex. It has three edges $a, b, c$ such that WLOG $a < b < c$ . Thus there are two paths with $b$ as their middle edge; if $x$ is some label at the other end of $b$ , there is either a path through $a$ or $c$ if $x > b$ or $x < b$ respectively.

Hence, for each vertex, there are at least two paths with that vertex on the middle edge. But each path has two vertices on the middle edge, giving $\boxed{8}$ paths in total.

Consider any edge. On both ends, it is connected to two other edges, hence there are four paths for which this edge is in the middle (ignoring direction). How many of these four constitute an increasing path? There are three possibilities:

• A) All four neighboring edges have a smaller label (or all have a larger label); in this case, none of the four paths is increasing.
• B) On one side, both neighboring edges have a smaller label, on the other side both have a larger label; in this case, all four paths are increasing (in one direction or the other).
• C) On one of the sides (or both), one neighboring edge has a smaller label and the other a larger one; in this case, there are two increasing paths.

If we want to minimize the total number of increasing paths, we would thus like to maximize the number of edges of type A, and minimize the number of type B.

The 12 edges can be divided into three sets of four parallel edges. Let us put the four smallest numbers, 1 through 4, on one of these sets. Since these edges do not touch each other, it is easy to see that these edges will only have neighbors with larger labels, hence they are of type A.

Similarly, we can put the four largest numbers, 9 through 12, on another set of parallel edges, and then these edges are all of type A as well.

The four remaining edges, labeled 5 through 8, are easily seen to be of type C, regardless of the precise way in which all edges are labeled. In total, we thus have 8 edges of type A and 4 edges of type C, which gives a total number of increasing paths of $8 \times 0 + 4 \times 2 = 8$ .

Now to prove that this is the minimum. If we want to do better, we must have at least 9 edges of type A (since we cannot reduce the number of type B). This means that we must have at least 5 edges with neighbors that all have a smaller label, or at least 5 for which all neighbors have a larger label. Since both cases are equivalent, let us assume without loss of generality that the former is the case.

When we have 5 edges, at least two of them must touch each other. This can be seen from what follows: consider the four vertices $(0,0,0)$ , $(0,1,1)$ , $(1,0,1)$ and $(1,1,0)$ . All edges connect to one of these vertices. Therefore, when we have 5 edges, at least two of them must connect to the same vertex, and hence they are neighbors. However, it is clearly impossible for two neighboring edges to both have only neighbors with smaller labels, since one of them must be larger than the other.

We therefore conclude that it is impossible to have 5 edges that all have only neighbors with smaller labels, and similarly, that it is impossible to have 5 edges for which all neighbors have larger labels. Therefore, the total number of edges of type A is at most 8. Since the total number of edges of type B is at least 0, we can conclude that the solution we found earlier must be an optimal one. The answer is thus $\boxed{8}$

Nobody's posted a solution yet so I'm going to write something hoping to get a bit of discussion...

I can show that there are solutions with $8$ increasing paths, but couldn't show that no smaller value is possible.

To do this: let $A$ be the edges parallel to the $x$ -axis, and so on. Then we can describe all the possible ordered paths as one of the following:

$ABC, ACB, BAC, BCA, CAB, CBA, ABA, ACA, BAB, BCB, CAC, CBC$

In fact we can check and see that there are 8 possible paths for each of these categories.

If we assign edges so that $A = \{1,2,3,4\}, B = \{5,6,7,8\}, C = \{9,10,11,12\}$

then none of the paths is increasing except for $ABC$ which has 8 paths in it.

I tried to find a way of dividing the paths up into $8$ categories and showing that each category must have an increasing path in it, but I couldn't. For example,the cube has 8 vertices, but it's possible to have assignments so that there are no increasing paths starting or ending at a given vertex.