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
```

but oneon the path, then it is easy to find a counterexample. $\endgroup$10more comments