Is every path with this property shorter than another path with the same endpoints?

Question

Suppose that $G=(V,E)$ is a simple graph and $P=(V_1,E_1)$ is a path in $G$ where $$V_1=\{v_0,v_1,\cdots,v_n\},\ E_1=\{v_0v_1,v_1v_2,\cdots,v_{n-1}v_n\}.$$ I found that if the path $P$ satisfies:

For any $v_i\in V_1$, there exist $v_j\in V_1\setminus \{v_i\}$ and $u\in V\setminus V_1$ such that $uv_i,uv_j\in E$.

Then you can always find a longer $v_0$-$v_n$ path in $G$.

I have tried to find a counterexample to this for a long time but still cannot find one. So I think maybe the above conjecture is true. Is it true or is there any known result about this? Any ideas are welcome!

Answer 1

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.

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.

Answer 2

A very natural special case is the following:

For any $v_i\in V_1$, there exists exactly one $v_j\in V_1\setminus \{v_i\}$ such that there is a $u\in V\setminus V_1$ such that $uv_i,uv_j\in E$. This means that all $u\in V\setminus V_1$ have degree two.

In this case we can show that a longer $v_0v_n$ path exists as follows.

Proof: Define the graph $G'$ by replacing each length-two path $v_iuv_j$ with an edge $v_iv_j$, and also add $v_0v_n$.
(This might possibly give a multigraph, but that won't be a problem, and even if it were, we could reduce it to the case when $G'$ is a simple graph with a simple case analysis.)
$G'$ is a 3-regular graph and $v_0,..,v_n$ is a Hamiltonian-cycle in it.
By Smith's theorem, there is another Hamiltonian cycle in $G'$ which contains the edge $v_nv_0$.
This necessarily gives a longer $v_0v_n$ path in the original graph $G$, finishing the proof. $\square$

The more general case is when any $v_i\in V_1$ has exactly one neighbor $u\in V\setminus V_1$ (whose degree, $deg(u)$, might be more than two) can also be transformed into a cubic graph $G'$ by converting each $u$ into a cycle of length $deg(u)$, whose vertices are each connected to one neighbor of $u$ in $G$.
Then we would need to use a generalization of Smith's theorem that given a cycle $v_0,..,v_n$ in a cubic graph, we can find another cycle covering $v_0,..,v_n$ and containing the edge $v_nv_0$.
I conjectured that this was also true, but a counterexample was given by Martin and by Zachary in the comments, see below.

This method also fails when some $v_i$ can have more than one neighbor from $V\setminus V_1$.
In this case if one of $v_i$'s neighbors, $u$, has $deg(u)>2$, then we could simply delete the $uv_i$ edge from $G$.
Also if $deg(u)=2$, and $u$'s other neighbor is some $v_j$ that also has another neighbor from $V\setminus V_1$, then we could delete $u$ from $G$ without violating the conditions.
But the issue is if some $v_i$ is connected to several degree-two vertices from $V\setminus V_1$, whose other neighbors from $V_1$ have degree three. Maybe this will help in finding a counterexample, or a proof.

Answer 3

[Update: Now testing paths where $u$ can connect any number of $v$'s.]

Here is some Mathematica code to test the conjecture, which reports that it is true for $n\le7$.

n = 7;
jumpy[x_] := Min[Rest[x] - Most[x]] > 1
noncons = Select[Subsets[Range[n + 1] - 1, {2, Floor[n/2] + 1}], jumpy]
enough[setup_] := Length[Union[Flatten[setup]]] > n
noexcessl[setup_] := Or[Length[Last[setup]] == 2, Not[Or @@ 
    Table[enough[Delete[setup, {-1, i}]], {i, Length[Last[setup]]}]]]
easy = {___, {___, a_, ___, b_, ___}, ___, {___, c_, ___ ,d_, ___}, ___} /; 
      Or[And[c == a + 1, d == b + 1], And[c == a - 1, d == b - 1]]
setups0 = Select[Subsets[noncons, n - 1], enough];
setups0 // Length
setups1 = Select[setups0, noexcess];
setups1 // Length
setups2 = Select[setups1, And[nointer[#], noexcessl[#], ! MatchQ[#, easy]] &];
setups2 // Length
setups2 // Last

A setup in this code is a list of the $v$'s connected by each $u$, e.g. $$\{\{1, 7\}, \{2, 7\}, \{3, 7\}, \{4, 6\}, \{5, 7\}, \{0, 4, 7\}\}$$

We restrict to set ups where

• the $u$'s connect only non-consecutive $v$'s (since the conjecture holds trivially for any path with consecutive $v$'s connected by some $u$)
• all $v$'s are connected to some $u$ ($\tt{enough}$)
• every $u$ is needed to connect some $v$ ($\tt{noexcess}$)
• no pair of $v$'s is connected by more than one $u$ ($\tt{nointer}$); no $v$ can be disconnected from a $u$ while retaining a legitimate setup ($\tt{noexcessl}$); and no pair of the form $\{a,b\}$ has a counterpart of form $\{a+1,b+1\}$ which would make finding a path easy ($\tt{easy}$).

For $n=7$, we find respectively $4692858$, $16632$ and $332$ setups to consider after these last three bulletpoints.

paths0 = Prepend[0] /@ Append[n] /@ Permutations[Range[n - 1], n - 1];
jumpsin[path_] := Select[Sort /@ Partition[path, 2, 1], jumpy]
paths = Select[paths0, Length[#] + Length[jumpsin[#]] > n + 1 &]
covered[jumps_, setup_] := Outer[Complement[#1, #2] === {} &, jumps, setup, 1] // Boole
good[mat_] := And[Min[Plus @@ Transpose[mat]] == 1, Max[Plus @@ mat] == 1]
solutions[setup_] := Select[paths, good[covered[jumpsin[#], setup]] &]
solutions[setups2 // Last]
shortpaths = jumpsin /@ paths;
solcount[setup_] := Count[shortpaths, jumps_ /; good[covered[jumps, setup]]]
Min[solcount /@ setups2]

For each set up, we consider paths from $v_0$ to $v_n$ which are longer than the original path. We construct a matrix ($\mathtt{covered}$) whose rows are the jumps in the path, and whose columns are the $u$'s in the setup, recording whether each jump is covered by that $u$. Then we check ($\mathtt{good}$) that:

• the minimum row-sum checks that every jump in the path goes via some $u$ in the setup
• the maximum column-sum checks that each $u$ is used at most once.

So, for instance, the setup above works with the path $$\{0, 1, 2, 3, 4, 6, 5, 7\}$$ which is also abbreviated by its jumps $$\{\{4,6\},\{5,7\}\}$$

We find that all setups for $n\le 7$ work with at least $1$ path.

This enumeration of setups was too memory-intensive to work readily for higher $n$, but a variant looking for setups with $n=8$ and at most $5$ $u$'s turned up the following interesting case: The setup $$\{\{0,5\}, \{1,4,7\}, \{2,6\}, \{3,8\}\}$$ has some longer paths than the original, but none hit every vertex of the original path.

Answer 4

Here's some more computational data and ideas. I definitely intend to edit this later, to include a clean version of the code, and clarify my ideas, but I wanted to get this out now while there's all this attention from the bounty, in the hope that it inspires further progress. Feel free to leave comments if anything is unclear.

Model: For such a graph $G$, with $V_1$ specified, we can associate a hypergraph $H(G)$ on the vertex set $V_1$. Here, for $u \in V\setminus V_1$, there is an edge $e \in E(H)$ which contains each $v \in V_1$ which is adjacent to $u$ in $G$. For $G$ to satisfy the conditions of the prompt, there must be no isolated vertices in $H$.

WLOG, we may assume that each component $C$ in $H$, that $C$ is either a star graph (using only hyperedges with cardinality 2), or that $C$ only has one hyperedge. Otherwise, there will be $e_1,e_2$ in $C$ where $e_1$ has cardinality 3+ and there will be some $v \in e_1 \cap e_2$, in which case we can replace $e_1$ with $e_1\setminus \{v\}$, or there will be be a path/cycle in $C$ with 3 edges with cardinality 2, $v_1,v_2,v_3,v_4$, in which case we can remove $(v_2,v_3)$.

General verification: I did my work in Python, I believe the key speed-up was that I added the common neighbors one at a time, and then would prune whenever we had enough connections to find a longer path. It has been verified on all possible $G$ with $n\le 13$ (so the claim holds true when $V_1$ has at most 14 vertices). I have not fully cleaned the code yet, but intend to do so soon. You can find the code at the bottom, though I'm afraid it is not very readable currently.

It should be noted that I actually verified a stronger, weighted variant, where all "non-central" vertices $v$ that belong to a star graph component $C$ had weight 2. See below for what "non-central" vertices are.

Weighted variants: I also ran some weighted cases. We consider when the components of $H(G)$ are all star graphs. For each component $C$, we establish a center vertex, which will be the non-leaf if $C$ has at least 3 vertices, and is decided arbitrarily decided if $C$ only has two vertices. We then give each non-center vertex arbitrarily large weight (say 1000), so that it must be visited by any successful path in $G$, while the central vertices and $u \in V\setminus V_1$ both have weight 1. The motivation behind this weighted case is we can replace each non-central vertex $v_i$ with an arbitrarily long interval of non-central vertices $v_{i,1},\dots, v_{i,1000}$ which are now all connected to the same center as $v_i$ was. This mainly preserves the structure of $H$, with one small exception.

Here, with a bit of a more ad hoc search, we do find counter-examples to this weighted case. Here is one such example: [(0, [0, 2, 6]), (1, [1, 5, 10]), (8, [3, 8]), (11, [4, 11]), (7, [7, 9])] (in each tuple, the number on the left represents the chosen central vertex, and the list of the right represent the vertex set of the star graph component).

The "small exception" comes from the fact that when we replace non-central vertices with intervals, we can hop from a non-center $v_i$ to a center $v_j$, and then hop back from $v_j$ to $v_i$. Thus, in the given example, we have the walk 0,2,3,4,5,6,7,8,9,10,1,10,11, which makes use of this ability to "hop back". I have thought hard about finding a way to thwart this "backhopping" ability, but found no success, a lot of local properties seem to get in my way.

Messy code:

I have already cut out roughly half the lines from original program, which were deprecated because they investigated niche subproblems. There's still a good amount of trimming to be done, and I'll try to add some comments explaining how it works soon.

from collections import deque

def cleanInnerLists(L):
    out = []
    for a in L:
        if type(a) == list:
            out.append([])
            tail = []
            for b in a:
                tail.append(b)
                if b != 0:
                    out[-1] += tail
                    tail = []
        else:
            out.append(a)
    return out       
def Lsum(L1,L2):
    return [L1[i]+L2[i] for i in range(len(L1))]
def listify(p):
    return [sorted(list(part)) for part in p]
def mirroring(t):
    if len(t[1]) == 2:
        return (t[1][0],t[1])
    return t
def simplify(pointing,removing=False):
    seen = set()
    for y,part in pointing:
        seen |= set(part)
    if removing != False:
        seen -= {removing}
    missing = 0
    d = {}
    d[None] = None
    for a in range(max(seen)+1):
        if a in seen:
            d[a] = a-missing
        elif a-1 not in d:
            missing += 1
    return tuple([((d[y],tuple(sorted([d[x] for x in L if x in seen])))) for (y,L) in pointing])
def simplify2(pointing,removing=False):
    seen = set()
    for y,part in pointing:
        seen |= set(part)
    if removing != False:
        seen -= {removing}
    missing = 0
    d = {}
    for a in range(max(seen)+1):
        if a in seen:
            d[a] = a-missing
        elif a-1 not in d:
            missing += 1
    return tuple([mirroring((d[y],tuple(sorted([d[x] for x in L if x in seen])))) for (y,L) in pointing])
    
def tuplify(pointing):
    return tuple([(y,tuple(sorted(list(part)))) for y,part in pointing])
def valid(avoid,part):
    for i,a in enumerate(reversed(part)):
        if i == len(avoid):
            break
        if avoid[i] == None:
            continue
        if part[-1]-a < avoid[i]:
            return False
    return True
def part_builder(S,k=0,ell=0,avoid=[None,2]):
    L = sorted(list(S))
    todo = deque([(0,0,[])])
    while todo:
        cur, skipped, part = todo.pop()
        if cur == len(S):
            if ell > 0:
                if 0 < len(part) < ell:
                    continue
            yield S-(set(L[:skipped])|set(part)),skipped,set(part)
            continue
        
        if len(part) == 0:
            if skipped < k:
                todo.append((cur+1,skipped+1,part))
        else:
            todo.append((cur+1,skipped,part))
        new_part = part + [L[cur]]
        '''if avoid != None:
            if not valid(avoid, new_part):
                continue'''
        '''if len(part) == 2:######
            if len(L) != 3:
                continue'''
        if L[cur]-1 in part:
            continue
        todo.append((cur+1,skipped,new_part))
def pointersplus(p,ell=0):
    if len(p) == 0:
        yield []
    elif ell > 0 and any(len(part)<ell for part in p):
        pass
    else:
        for pointing in pointersplus(p[1:],ell):
            yield [(None,set(p[0]))]+pointing
            for y in p[0]:
                yield [(y,p[0])]+pointing
def pointers(p,ell=0):
    if len(p) == 0:
        yield []
    elif ell > 0 and any(len(part)<ell for part in p):
        pass
    else:
        for pointing in pointers(p[1:]):
            for y in p[0]:
                yield [(y,p[0])]+pointing
def pointers1(p,ell=0):
    if len(p) == 0:
        yield []
    elif ell > 0 and any(len(part)<ell for part in p):
        pass
    else:
        for pointing in pointers(p[1:]):
            yield [(p[0][0],p[0])]+pointing
            #yield [(p[0][-1],p[0])]+pointing
def pointers2(p,ell=0):
    if len(p) == 0:
        yield []
    elif ell > 0 and any(len(part)<ell for part in p):
        pass
    else:
        for pointing in pointers(p[1:]):
            if len(p[0]) < 3:
                yield [(p[0][0],p[0])]+pointing
            else:
                for y in p[0][1:-1]:
                    yield [(y,p[0])]+pointing
def trydo(S,k,ell,D,A,hist=[[],[],set([])],printing=True,MEM={}):
    count1,count2,nobreak,loops,desperados,counters = [0,0,0,0,[0 for _ in range(len(D)+1)],0]
    i_local = len(D)
    
    for data in part_builder(S,k,ell):
        count1 += 1
        Snew,klost,part = data
        
        knew = k-klost

        Dnew = {x:D[x] for x in D}
        for x in part:
            Dnew[x] = set(part)-{x}
        if i_local-1 in part:
            if 0 not in S:
                if len(part) > len(hist[0][0]):
                    continue
        
        
        for pointing in pointersplus(listify([part]),ell):
            count2 += 1
            Anew = {x:A[x] for x in A}            

            if 0 in part:
                if pointing[0][0] != 0:
                    continue
            elif 0 in S:
                print(S,part,Snew)

            y = pointing[0][0]
            if y == None:
                Y = part
            else:
                Y = {y}
            for x in part:
                Anew[x] = (part&Y)-{x}
            if y != None:
                Anew[y] = part-Y
            else:
                if len(Y) == 2:
                    continue
                #Y = set()
           
            
                
            newhist = [hist[0]+[part],hist[1]+pointing,hist[2]|Y]
           
            '''if 0 in part and 0 != y:
                continue'''
            
           
            
            w = {v:2*int(v not in newhist[2])+1 for v in D}#w = {v:int(v not in newhist[2])*100+1 for v in D}#
            total = sum(w[v] for v in w)
            todo = deque([(0, w[0], {0}, set())])
            todoDesperate = deque([])
            for x in D:
                break#(testing)
                if x in Anew[0]:
                    pass#todoDesperate.append((x, w[0]+w[x]+1, {0,x}, set()))
                else:
                    if len(Anew[x]&newhist[2]) > 0 and x != i_local-1:
                        for v in Anew[x]:
                            if v == i_local-1:
                                continue
                            todoDesperate.append((v, w[0]+1+w[v]+1, {0,v}, set()|Anew[v]))
                        todoDesperate.append((x, w[0]+w[x], {0,x}, set()))
            despLevel = 0
            #search for a longer path
            while todo and (breaking == False):
                loops += 1
                #superhit is the set of vertices where we have used up the u vertex
                cur, length, hit, superhit = todo.pop()
                if cur == i_local-1:
                    if length > total:
                        #MEM[key] = 1
                        break
                    '''else:
                        for x in Anew[cur]:
                            if x not in hit:
                                if x not in superhit:
                                    if w[x] == 100:
                                        todoDesperate.append((cur,length+w[x]+1, hit | {x}, superhit | Anew[cur] ))''' #not necesary because we don't need to weight the last vertex
                else:       
                    if cur+1 not in hit:
                        todo.append((cur+1, length+w[cur+1], hit | {cur+1}, superhit))
                    
                    for x in Anew[cur]:
                        if x not in hit:
                            if x not in superhit:
                                todo.append((x, length+w[x]+1, hit | {x}, superhit | Anew[cur]))
                                '''if w[x] == 101:
                                    todoDesperate.append((cur,length+w[x]+2, hit | {x}, superhit | Anew[cur] ))'''
                    if cur > 0 and cur-1 not in hit:
                        todo.append((cur-1, length+w[cur-1], hit | {cur-1}, superhit))
                if len(todo) == 0 and len(Snew) == 0:
                    desperados[despLevel] += 1
                    despLevel += 1
                    todo.extend(todoDesperate)
                    todoDesperate = deque([])
            else:
                #MEM[key] = 0
                if len(Snew) == 0:
                    counters += 1
                    if printing == False:
                        continue
                    print(newhist[0],[y for y,part in newhist[1]])
                    print(newhist[1])
                    #print(Anew)
                else:
                    L = trydo(Snew,knew,ell,Dnew,Anew,newhist,printing)
                    count1 += L[0]
                    count2 += L[1]
                    nobreak += L[2]
                    loops += L[3]
                    desperados = Lsum(desperados,L[4])
                    counters += L[5]
    if 0 in S:
        if len(MEM) > 0:
            print(len(MEM))
    return count1,count2,nobreak,loops,desperados,counters


i = 9
k = 0
while 1:
    S = set(range(i))
    D0 = {x:set([]) for x in S}
    A0 = {x:set([]) for x in S}
    
    L = list(trydo(S,k,2,D0,A0))
    L = [i]+L
    L = cleanInnerLists(L)
    print(*L)
    #count1,count2,nobreak,loops,counters = trydo(S,k+1,2,D0,A0,printing=False)
    #print(i, count1, count2, nobreak, loops, counters)

    #print('\n')

    i += 1 

Answer 5

Disclaimer: this is not a proof but rather some ideas which may or may not help.

If we identify the pairs $v_i, v_j$ such that there's $u$ with $v_iuv_j \in E$ with a segment $[i, j]$, we are going to have at least $\frac{n+1}{2}$ segments.

Now we can argue similarly to the Vitali covering lemma. We have a collection of segments, covering $1, \ldots, n$ (let's assume we count starting from $1$ rather then from $0$). We can find two families of segments $\{ I \}$ and $\{ J \}$ such that

1. Segments in each family are either disjoint or nested
2. There are disjoint subfamilies $\tilde I$ and $\tilde J$ such that each segment intersect at most two neighbouring.

Now at least one of the families has measure at least $\frac{n+1}{2}$. Assume wlog that $$ | \cup I_j | \geq | \cup J_j | $$

If we order the segments in $\tilde I$ and $\tilde J$ so that $J_k$ intersects exactly two neighbours say $I_{l-1}$ and $I_{l}$ and $|J_k \cap I_{l-1}| + |J_k \cap I_{l}| = |J_k|$, then it would suffice to walk trough the nested segments in $I_{l-1}$, then "jump" using $J_k$ to $I_l$ and walk through the nested family in $I_l$.

The scheme above assumes that all $u$'s are distinct.