Verifica della soluzione del ciclo hamiltoniano in O (n^2), n è la lunghezza della codifica di G

Question

Nel libro di testo di CLRS, 'Ch. 34.2 Verifica del tempo polinomiale 'dice quanto segue:

Supponiamo che un amico ti dica che un determinato grafico G è Hamiltonian, e poi si offra di dimostrarlo dandoti i vertici in ordine lungo il ciclo di hamiltoniano. Sarebbe certamente abbastanza facile verificare la prova: semplicemente verificare che il ciclo fornito sia hamiltoniano controllando se si tratta di una permutazione dei vertici di $ V $ e se ciascuno dei bordi consecutivi lungo il ciclo esiste effettivamente nel grafico. Potresti certamente implementare questo algoritmo di verifica in cui eseguire $ O (n^2) $ tempo, dove $ n $ è la lunghezza della codifica di $ G $.

Per me, per ogni coppia consecutiva $ (u, v) $ del ciclo dato, potremmo verificare se si tratta di un vantaggio $ G $. Inoltre potremmo usare un po 'di codifica a colori per ogni vertice per assicurarci di non rivisitare un vertice. In questo modo, potremmo verificare se il ciclo dato è hamiltoniano in $ O (e) = o (m^2) $ tempo dove $ m $ è il numero di vertici in $ G $. Inoltre possiamo vedere la codifica minima $ n $ di $ G $ è $ m^2 = n $. così $ O (e) = o (m^2) = o (n) $. Qualcuno può aiutarmi a capire, perché è menzionato come $ O (n^2) $ invece!