The answer is too large.. it's O(n)

navi_09220114 wrote: The answer is too large.. it's O(n) Did I misread the problem? or disjoint union of $K_1$ and $K_{n-1}$ is a counter example

You basically have to "reach all possible vertices" by walking along the edges of the graph, depending on the number on the label. This forces the graph to be connected already

The bound is $\boxed{n-1+\lceil \frac{n}{3} \rceil}$ Claim: $G$ is connected If it is not their is no way to move the token from one part to another. Claim: Every vertex is part of a triangle Assume there is some vertex $v$ that is not part of a triangle. Let $S(v)$ be the set of its neighbors and $R(v)$ be the set of all other vertices. If Navi assigns all elements of $S(v)$ the number $2$ and all elements of $R(v)$ the number $1$ then if the token is not originally at $v$ it is impossible for Zscoder to reach $v$. Claim: All such graphs work If the token is at a vertex $v$ then alternate along an edge until you have $1$ or $2$ moves left. Notice that from any triangle you can reach any vertex in that triangle and from any triangle you can reach any vertex adjacent to that triangle. Thus the token can reach all the vertices. Now consider a path through all the vertices of $G$ containing $n-1$ edges. Clearly there is at least $\lceil \frac{n}{3} \rceil$ triangles and each one must have at least one edge not belonging to the path. It is not hard to create such a construction and this gives the desired bound.

$\textbf{Answer.}$ $\left\lceil \frac{4n}{3} \right\rceil - 1$. $\textbf{Official Solution.}$ We say that a vertex $u$ is reachable from a vertex $v$ if one can mark $u$ red by starting from vertex $v$. We say that a graph $G$ is good if no matter how it is labeled, any two vertices are reachable from one another. Note that the problem is equivalent to asking for the minimum number of edges in a good graph on $n$ vertices. Indeed, if a graph is good, then we can mark all vertices as red no matter where we start from due to reachability. Conversely, if vertex $u$ is not reachable from vertex $v$, then starting from vertex $v$, we can never mark vertex $u$ as red. Obviously, if $G$ is good, then $G$ is connected. Observe that it is sufficient to consider the case where all labels are $1$ or $2$, since going back and forth on an edge takes $2$ steps. Now, we split the proof into two parts. $\textbf{Proof of upper bound:}$ It is sufficient to construct a good graph $G$ with $\left\lceil \frac{4n}{3} \right\rceil - 1$ edges. For $n=3$, one can take a triangle. For $n=4$, one can take a complete graph without an edge. For $n=5$, one can take two triangles sharing a single vertex. For $n \ge 6$, one can connect the construction for $n-3$ and a triangle with an edge. One can check that these graphs have exactly $\left\lceil \frac{4n}{3} \right\rceil - 1$ edges. Furthermore, one can prove that these graphs are good by induction on $n$: the base cases $n=3,4,5$ can be checked manually. For $n \ge 6$, let $G$ be constructed by adding an edge $e$ between $G'$, a good graph on $n-3$ vertices, and a triangle $T$. Let $u$ be the endpoint of $e$ in $G'$ and $v$ be the other endpoint. By the induction hypothesis, any two vertices within $G'$ and any two vertices within $T$ are reachable from one another. For any two vertices $u' \in G'$ and $v' \in T$, one can reach $v'$ from $u'$ by going from $u'$ to $u$, then go to any vertex in $T$, and then go to $v'$. Similarly, one can reach $u'$ from $v'$. Hence, $G$ is good. $\textbf{Proof of lower bound:}$ Now, we show that all good graphs must have at least $\left\lceil \frac{4n}{3} \right\rceil - 1$ edges. We prove the following important lemma. $\textit{Lemma:}$ If $G$ is a good graph, then the following conditions hold: $\bullet$ $G$ is connected. $\bullet$ Every vertex $v \in G$ is in some triangle. $\textit{Proof:}$ The first condition is obvious. Now, suppose there exists some $v \in G$ that is not in any triangle. In other words, its neighborhood $N(v)$ is an independent set. Label all vertices in $N(v)$ with $2$ and all other vertices with $1$. We claim that it is impossible to reach $v$ from any other vertex $u$. Indeed, suppose not, and let $v'$ be the last vertex visited before marking $v$. If $v' \not\in N(v)$, this is impossible, since $v'$ has label $1$. Otherwise, $v' \in N(v)$, but since no two vertices in $N(v)$ are connected, one cannot get from $v'$ to $v$ in exactly $2$ moves, a contradiction. It remains to show that any graph $G$ satisfying the two properties in Lemma 1 has at least $\left\lceil \frac{4n}{3} \right\rceil - 1$ edges. Let $H$ be an empty graph. Fix any good graph $G$ and color all vertices white. Consider the following algorithm: $\bullet$ Choose a white vertex $v$, and let $T = (v,v',v'')$ be a triangle containing $v$ (which exists by the lemma). Color $v,v',v''$ black, and add edges of $T$ to $H$ (if they don't already exist). At every step of the algorithm, we maintain the counters $C, M, N$, which denotes the number of connected components, number of edges, and number of vertices of $H$. Initially, $C=M=N=0$. $\textit{Lemma:}$ At any point of the algorithm, $3(C + M) \ge 4N$. $\textit{Proof:}$ Clearly, the inequality holds at the beginning of the algorithm. Observe that after every iteration in the algorithm, $N$ increases by $1$, $2$, or $3$ corresponding to the following cases: $\bullet$ Case 1: $N$ increases by $1$. In this case, $M$ increases by at least $2$. If it increases by $2$, then the edge $(v',v'')$ must have existed, so $C$ does not change. Otherwise, $C$ decreases by at most $1$. In any case, $M+C$ increases by at least $2$. Hence, LHS increases by at least $6$ and RHS increases by $4$. $\bullet$ Case 2: $N$ increases by $2$. In this case, $M$ increases by $3$, and $C$ is unchanged. Thus, LHS increases by $9$ while RHS increases by $8$. $\bullet$ Case 3: $N$ increases by $3$. The white subgraph has a new triangle, so $C$ increases by $1$ and $M$ increases by $3$. Hence, both sides of the inequality increases by exactly $12$. In any case, the inequality $3(C+M) \ge 4N$ is maintained, as desired. Note that by our construction, $H$ is a subgraph of $G$. Furthermore, if $H$ has $C$ connected components, then there are at least $C-1$ edges in $G$ that are not in $H$ since $G$ is connected. Hence, $|E(G)| \ge M+C-1 \ge \frac{4N}{3} - 1$, which proves the lower bound.

Seemed like the problem might have been before but I hadn't seen it yet. Pretty cute how the induction is not at all casework messy and just works naturally. https://drive.google.com/file/d/1tciH9xXC8osC271pGjjuMqHr0M5swm98/view?usp=sharing