Return to Answer

Assume now that we have a jumping block $G$ with $A(G)\le \frac 18L(G)-\frac 12$. Then we can use the Matt F's graph $H=142341243$ to create the graph $[G,\dots,G]_H$ in which every path from the beginning to the end either does not use the interblock jumps at all (so no gain is possible here), or misses an entire block (so the gain is at most $-L(G)+8A(G)+4\le 0$ again), thus providing a pure octopus counterexample.

Assume now that we have a jumping block $G$ with $a(G)\le \frac 18L(G)-\frac 12$. Then we can use the Matt F's graph $H=142341243$ to create the graph $[G,\dots,G]_H$ in which every path from the beginning to the end either does not use the interblock jumps at all (so no gain is possible here), or misses an entire block (so the gain is at most $-L(G)+8a(G)+4\le 0$ again), thus providing a pure octopus counterexample.

Edit 2: Pure "octopus" construction.

First, the notation. If the graph vertices outside the path are labelled with some symbols, then the graph will be represented as a string of these symbols according to which vertex outside the path each vertex on the path is connected to. The symbol $*$ is reserved for a vertex on the path that is not connected to anything. For instance, the graph with 7 path vertices $v_0,\dots v_6$ and 3 out of the path vertices labeled $u_0,u_1,u_2$ in which $u_0$ is connected to $v_0,v_4$, $u_1$ is connected to $v_1,v_3$, $u_2$ is connected to $v_2$ and $v_6$ and $v_5$ is not connected to anything is represented as $01210*2$.

When we move from the path to an out of the path vertex and then back to the path, we say that we make a jump. For instance, making the jump between $2$'s in the above example means that we follow the route $v_2u_2v_6$ (possibly backwards).

The length of the route is the number of vertices in it. When we make a simple move to a neighboring vertex along the path, the length of the route goes up by $1$; when we jump, it goes up by $2$. The gain of the route is the excess of its length over the length of the original path. If it is negative, we call minus the gain a loss. The route we are talking about can be between any 2 vertices, not only between the beginning and the end. For instance, in our example $01210*2$ we can consider the route $1\to 1\to 2\to 2\to *\to 0\to 0$ from one of the $1$'s to $0$ of length $1+2+1+2+1+1+2=10$ with gain $10-7=3$. Of course, we can always change our symbols to any other ones: $abcba*c$ represents the same graph.

A jumping block is a graph represented by a string with a single $*$ and each other symbol appearing at least twice and such that no route from the beginning to the end with positive gain is possible. For instance, the graph in our example is not a jumping block because it satisfies the first two conditions but not the third one: the route $0\to 0\to 1\to 1\to 2\to 2$ has length $9$ and gain $2>0$ but the graph $012*210$, say, is. If $G$ is a jumping block, then we shall be concerned with 2 corresponding quantities: the length $L=L(G)$ of the underlying path and the maximal possible gain $a=a(G)$ on a route between $*$ and one of the ends. For instance, the jumping block $012*210$ has $L=7$ and $a=3$ (on the route $0\to 0\to 1\to 1\to 2\to 2\to *$). Note that we always have $a\le\frac{L-1}2$ because the gain can come only from jumps and we can execute at most $\frac{L-1}2$ jumps in any route (a jump corresponding to each symbol in the string can be used at most once). So, if we define $A(G)=2a(G)+1$, we have $A(G)\le L(G)$. Clearly, if some string is to a jumping block, the reverse string is also a jumping block with the same $L,a$.

Suppose we have a jumping block $H$ of length $L$ and $L$ jumping blocks $G_1,\dots, G_L$ (not necessarily identical) of the same length $M$. Then we can construct a new jumping block $[G_1,\dots,G_L]_H$ as follows. Represent $H$ and $G_j$ by strings so that different strings have no common symbols (except $*$) and put the $G_j$ strings together in a row. Now we have $L$ $*$-symbols in the resulting string. Replace them (from left to right) by the symbols in $H$ (so just one $*$ will remain a $*$). For example, if $H=0*0$ and $G_1=G_2=012*210, G_3=0102*21$ ($L=3, M=7$ here) , we first write $H=a*a$, $G_1=012*210$, $G_2=345*543$, $G_3=6768*87$, then make the string $012*210345*5436768*87$ and then replace $*$'s to get $[G_1,G_2,G_3]_H=012a210345*5436768a87$.

The first claim is that $[G_1,\dots,G_L]_H$ is again a jumping block. Indeed, any beginning to end route in $[G_1,\dots,G_L]_H$ corresponds to a beginning to end route in $H$. Just see in each order you enter and exit the blocks $G_j$. Note that it is possible to enter, exit, and then re-enter the same block $G_j$, but then you get stuck there, so on the route from the beginning to the end, once you enter an intermediate block and exit it, you can never return and for the endpoint blocks, once you enter them, you either reach the end of the entire string, in which case your route terminates, or exit without reaching it and then can never return. Thus any route from the beginning to the end stays for a while in $G_1$, then goes to some other block $G_j$, stays for a while there, etc. Suppose now that we have some route from the beginning to the end in $[G_1,\dots,G_L]_H$ and the corresponding route in $H$ has $J$ jumps. Then, since $H$ is a jumping block, that corresponding route must miss $\ge J$ vertices in $H$, i.e., the original route misses at least $J$ full blocks $G_j$ with the total of $JM$ vertices. What we may gain is that for each of the $2J$ blocks corresponding to the jump ends, we do not need to traverse them from the beginning to the end, but just from one endpoint to the jumping place. However, on those we can gain at most $2J\max_j a(G_j)\le J(M-1)$ extra vertices. Finally, the $J$ interblock jumps create $J$ extra vertices and the total gain is $-JM+(\le J(M-1))+J\le 0$.

We also need to bound $A([G_1,\dots,G_L]_H)$. Again, a route to $*$ in this composite graph corresponds to a similar route to $*$ in $H$ for the same reasons as before (note that it is essential here that we cannot jump to $*$ or into a $*$-block). Now denote by $J$ the number of jumps on that route in $H$. By the definition of $a(H)$ we see that we must miss at least $(J-a(H))_+$ vertices in $H$, each of which corresponds to a full block in $[G_1,\dots,G_L]_H$. So we conclude that our total gain on any route to $*$ from any of the endpoints is at most $$ -M(J-a(H))_++(2J+1)a+J \\ =-M(J-a(H))_++J(2a+1)+a\le a(H)(2a+1)+a\,. $$ Here $a=\max_j a(G_j)$, the second term corresponds to most $2J+1$ blocks $G_j$ in which we need to connect one of the endpoints to the jump position instead of the other endpoint (the ends of interblock jumps and the final $*$ block), $J$ is the gain on the interblock jumps, and the inequality $2a+1\le M$ is used in the last step. This estimate can be rewritten as $A([G_1,\dots,G_L]_H)\le A(H)\max_j A(G_j)$. In particular, when $G_1=\dot=G_L=G$, we have $$ A([G,\dots,G]_H)\le A(H)A(G)\,. $$

Assume now that we have a jumping block $G$ with $A(G)\le \frac 18L(G)-\frac 12$. Then we can use the Matt F's graph $H=142341243$ to create the graph $[G,\dots,G]_H$ in which every path from the beginning to the end either does not use the interblock jumps at all (so no gain is possible here), or misses an entire block (so the gain is at most $-L(G)+8A(G)+4\le 0$ again), thus providing a pure octopus counterexample.

To build such a jumping block, it would suffice to have any jumping block $G$ with $A(G)<L(G)$ because then we can consider the sequence of the jumping blocks $G_1=G$, $G_{k+1}=[G_k,\dots,G_k]_G$ with $A(G_k)\le A(G)^k, L(G_k)=L(G)^k$ and choose a sufficiently large $k$.

Finally, to build a jumping block with $A(G)<L(G)$, it would suffice to build one in which no route from the left end to $*$ can use all available jumps. If $G_0$ is such a jump block, then $G=[G_0G_0\bar G_0]_{a*a}$, where $\bar G_0$ is represented by the same string as $G_0$ but written backwards, will work because now, to reach the $*$ from either of the ends , we must either reach the jumping position in $G$ from the left end, or not to use the interblock jump and, thus, miss the opposite block entirely.

Thus, we just need a single jumping block with no route from the left end to the star position using all jumps. Fortunately, the computer search yielded the result with $L=15$ (a few seconds of computer time) and the block is $0121345*5407372$. Once you know it, the verification of the properties by hand is a routine (though somewhat boring) casework, so I'll skip it (but if you discover that there is an error here, by all means let me know :-) )

The result of our construction with this block is a graph with $45^{31}$ vertices on the path and about half that number out of the path. Note also that in the entire graph we have just a single out of the path vertex of degree 3 (the one in the Matt F. graph), which shows that the domotorp result cannot be improved.

MattF's counterexample, understood properly, is actually a counterexample. His original path sequence in my notation was 142341243 (there are 4 vertices 1,2,3,4 outside the path (octopus heads) and the number shows the leg of which octopus the path vertex is. The key property of this sequence is that if you go from the beginning to the end and make at least one jump, you have to miss at least one vertex. Now surround each vertex $*$ on this path with its own block of the type $aa\dots aa*A$ where each $a$ is connected to $A$ by its own extra vertex (so the jumps between $a$ and $A$ are possible but the jumps between $a$ and $a$ are not and there are no "A" or $a$-connections between the blocks). If we execute at least one long $*$ to $*$ jump between blocks, we will gain at most 4 vertices on the long jumps and at most 2 vertices within each used block with the total gain of $2\cdot 8+4=20$ but we will lose an entire block, so if we have $19$ $a$'s, the loss outweighs the gain. Otherwise, we have to honestly traverse each block and this does not create any gain either.

It is funny that I have thought of this block construction long ago but missed that $aa\dots aa*A$ possibility. The examples where you have only octopuses all resulted in paths to $*$ from both ends of the block with gains comparable to the total block length, so increasing block length did not help.

I hope that I haven't made a mistake here, but by all means check the details and ask questions if something looks wrong :-)

MattF's counterexample, understood properly, is actually a counterexample. His original path sequence in my notation was 142341243 (there are 4 vertices 1,2,3,4 outside the path (octopus heads) and the number shows the leg of which octopus the path vertex is. The key property of this sequence is that if you go from the beginning to the end and make at least one jump, you have to miss at least one vertex. Now surround each vertex $*$ on this path with its own block of the type $aa\dots aa*A$ where each $a$ is connected to $A$ by its own extra vertex (so the jumps between $a$ and $A$ are possible but the jumps between $a$ and $a$ are not and there are no "A" or $a$-connections between the blocks). If we execute at least one long $*$ to $*$ jump between blocks, we will gain at most 4 vertices on the long jumps and at most 2 vertices within each used block with the total gain of $2\cdot 8+4=20$ but we will lose an entire block, so if we have $19$ $a$'s, the loss outweighs the gain. Otherwise, we have to honestly traverse each block and this does not create any gain either.

It is funny that I have thought of this block construction long ago but missed that $aa\dots aa*A$ possibility. The examples where you have only octopuses all resulted in paths to $*$ from both ends of the block with gains comparable to the total block length, so increasing block length did not help.

I hope that I haven't made a mistake here, but by all means check the details and ask questions if something looks wrong :-)

Edit: Here is a picture of the graph with $19=5$. The path is the horizontal straight line.

If you just keep the bottom colored part, this would be exactly Matt F.'s original construction.