The answer is $k = \lfloor \log_2 n\rfloor$. Construction Divide the vertices into groups of size $1$, $2$, $4$, \dots, $2^{k-2}$, $2^{k-1}+x$ where $x > 0$. Number these groups from $1$ to $k$ respectively, and color an edge between groups $i$ and $j$ with $\min(i, j)$. In order for a Hamiltonian path to avoid using a color $i$, the neighbors of all vertices of group $i$ in the path must be in group less than $i$. This is not possible since the number of vertices in the $i$-th group is more than vertices in group $1$, $2$, $\dots$, $i-1$. Upper bound By the Bondy-Chvatal theorem we may repeatedly remove edges until the following property holds: for any color $c$ and edge $xy$ of that color, $\deg_c(x)+\deg_c(y) \geq n$ $(\spadesuit)$. Note that now, between any two vertices, there is at most one colored edge between them, and we allow there to be no colored edges. We set the following notations. Let $C_i$ be the set of edges of color $i$. $\deg_i(v)$ be the degree of $v$ in $C_i$. $v_i$ be a vertex of minimum degree in $C_i$ $d_i$ be the degree of $v_i$ in $C_i$. $N_i$ be the neighborhood of $V_i$ in $C_i$. Without loss of generality, let $d_1\leq d_2\leq \dots\leq d_k$. Claim $N_1,\dots,N_k$ are pairwise disjoint. Proof of Claim Suppose there exists a vertex $x\in N_i\cap N_j$ for some $i<j$. From $(\spadesuit)$, we have $\deg_i(x) \ge n-d_i$. Moreover, $\deg_j(x)\ge d_j$. Thus, $\deg_i(x) + \deg_j(x) \geq n$, a contradiction. Claim If $x\in N_i$, $y\in N_j$ and $i<j$, then $xy$ must have edge color $i$ or uncolored. Proof If $xy$ has edge color $t$ for some $t\notin \{i,j\}$, then we note that \begin{align*} \deg_i(x) &\ge n-d_i, \\ \deg_t(x) + \deg_t(y) &\ge n\\ \deg_j(y) &\ge n-d_j \end{align*}Since $N_i$ and $N_j$ are disjoint, $d_i+d_j\leq n$. Thus, summing gives $$ 2n-2 \ge (\deg_i(x) + \deg_t(x)) + (\deg_t(y)+\deg_j(y) ) \ge 2n,$$a contradiction. If $xy$ has edge color $j$, then $\deg_j(x) \ge d_j$ by minimality, since $x$ is not an isolated vertex of $C_j$. We also have $\deg_i(x) \ge n-d_i$ since $x\in N_i$. Hence, $\deg_j(x) + \deg_i(x)\ge n$, contradiction. For any vertex $v\in N_j$, note that $xv$ does not have color $j$ for all $x\in N_1\sqcup \dots \sqcup N_{j-1}$. By counting edges incident to $v$, we obtain \begin{align*} &n-d_j\leq \deg_j(v) \le n-1-d_1-\dots-d_{j-1} \\ \implies& \hspace{1cm} d_j \geq 1+d_1+d_2+\dots+d_{j-1} \end{align*}Consequently, $d_j \ge 2^{j-1}$ for all $j=1,\dots,k$, so we have found at least $1+2+4+\dots+2^{k-1}=2^k-1$ vertices. Finally, suppose that $n=2^k-1$. By analyzing the equality case above, we have $d_j =2^{j-1}$ for all $j=1,\dots,k$; $N_1,N_2,\dots,N_k$ covers all vertices in $G$; and edges between $N_i$ and $N_j$ are labeled $\min(i,j)$ or uncolored. We can build a Hamiltonian path that does not use color $k$ by simply alternating between vertices in $N_k$ and vertices in $N_1,\dots, N_{k-1}$. This is a contradiction.