Una condición suficiente para que un grafo tenga un camino Hamiltoniano es que la suma de 2 vértices sea mayor o igual a #V - 1 para cualquier par de vértices. Como es regular vas a tener 2*gr(v) >= 18-1 para todo v en V. Luego gr(v)>=9 para todo vértice, como te piden el mínimo tomas 9. Luego por la fórmula de la sumatoria de los grados de los vértices y como el grafo es regular sacas que 18*9 = 2m, luego m=81