MathDB

Zscoder has an simple undirected graph

G

with

n\ge 3

vertices. Navi labels a positive integer to each vertex, and places a token at one of the vertex. This vertex is now marked red. In each turn, Zscoder plays with following rule:

\bullet

If the token is currently at vertex

v

with label

t

, then he can move the token along the edges in

G

(possibly repeating some edges) exactly

t

times. After these

t

moves, he marks the current vertex red where the token is at if it is unmarked, or does nothing otherwise, then finishes the turn.
Zscoder claims that he can mark all vertices in

G

red after finite number of turns, regardless of Navi's labels and starting vertex. What is the minimum number of edges must

G

have, in terms of

n

?
Proposed by Yeoh Zi Song

Problem Statement