# Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G

In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following:

Suppose that a friend tells you that a given graph G is hamiltonian, and then offers to prove it by giving you the vertices in order along the hamiltonian cycle. It would certainly be easy enough to verify the proof: simply verify that the provided cycle is hamiltonian by checking whether it is a permutation of the vertices of $$V$$ and whether each of the consecutive edges along the cycle actually exists in the graph. You could certainly implement this verification algorithm to run in $$O(n^2)$$ time, where $$n$$ is the length of the encoding of $$G$$.

To me, for each consecutive pair $$(u,v)$$ of the given cycle, we could verify if it's an edge in $$G$$. Further we could use some color coding for each vertex to ensure we don't revisit a vertex. By doing so, we could verify if the given cycle is Hamiltonian in $$O(E)=O(m^2)$$ time where $$m$$ is the number of vertices in $$G$$. Further we can see the minimum encoding $$n$$ of $$G$$ is $$m^2=n$$. Thus $$O(E)=O(m^2)=O(n)$$. Can anyone help me understand, why it is mentioned as $$O(n^2)$$ instead!

The statement in CRLS is not wrong in any case; an algorithm that runs in $$O(n)$$ time also runs in $$O(n^2)$$ time. Of course, it would be more precise to state the running time as $$O(n)$$ if this were true, so why doesn't CLRS do this?
First off, this depends on the encoding chosen for $$G$$. If an adjacency matrix is used, a graph with $$V$$ vertices always has an encoding of size $$V^2$$. However, if an adjacency list encoding is used, we would only need an encoding of size $$O(E \log V + V)$$.
Your algorithm does indeed run in $$O(n)$$ time for a dense graph (with $$\sim V^2$$ edges); does it also run in $$O(n)$$ time if the graph is sparse ($$O(V)$$ edges)? In that case, the encoding might be shorter (if an adjacency matrix is used). Is your algorithm still $$O(n)$$ in that case? If it enumerates over all potential edges or creates and adjacency matrix, it would not be.
CLRS wants to avoid peculiarities with having to implement the algorithm in a particular way or having to specify a specific encoding, which is why they state "you could certainly implement this algorithm to run in $$O(n^2)$$ time". The "certainly" means "in any case, you can get $$O(n^2)$$, but it might be possible to do better". In any case, all they care about is that it is polynomial, which both $$O(n)$$ and $$O(n^2)$$ are.