For which values of m is an euler OR hamilton curcuit exist? Let G be a graph over the vertices $\{3,4...m\}$ for $m\ge4$ , such that $v_i$ & $v_j$ are neighbors iff $i\neq j$ and $i\cdot j ≡ 0(mod3)$. 
A - for which values of m there exist an euler circuit ?
B- for which values of m there exist a hamilton citrcuit?
My solution
As known, a graph has an euler circuit iff all it's vertices have even degrees. I tried to find a pattern for it, and realized the number of multiplications of $3$ must be even, and my guess is that $m-1$ is a multiplication of 3 - Only from some sketches I have made.
Even if I'm correct, I would appreciate an explanation to my intuition.
As for B - as I understand there is no condition for a hamilton circuit to exist, however there is "ORE" 's theorem which gives a sufficient condition for a graph to contain a hamilton cycle.
I didn't know how to use it though.
Any help would be great.
Thanks.
 A: A more helpful way to phrase $i \cdot j \equiv 0 \ \ (\text{mod} \ 3)$ is that $3$ divides at least one of $i$ and $j$.
Let us compute the degree of each vertex in $G$; this seems sensible, since both Ore's condition and the characterization of Eulerian graphs depend on the degrees. If $3$ divides $i$, then $v_i$ is adjacent to every other vertex of the graph, so that $d(v_i) = (m - 2) - 1 = m-3$. On the other hand, if $3$ does not divide $i$, then $v_i$ is adjacent to $v_{3j}$ for every $j = 1, \dots, \lfloor\frac{m}{3}\rfloor$, so in this case $d(v_i) = \lfloor \frac{m}{3}\rfloor$.
Now we see that for part a), we need that both $m-3$ and $\lfloor\frac{m}{3}\rfloor$ are even. This agrees with your intuition (of course $m-3$ is even if and only if $m-1$ is even). You can also check that $\lfloor\frac{m}{3}\rfloor$ is even if and only if $m  \ (\text{mod} \ 6)$ is either $0,1$ or $2$.
Edit: Previously I claimed that Ore's theorem can be used to show that $G$ has a Hamiltonian circuit for $m \geq 5$. This is incorrect - turns out that $2\lfloor\frac{m}{3}\rfloor$ does not exceed $m-3$ (oops). In fact, $G$ only has a Hamiltonian circuit for $m = 6$. This follows, for example, from the fact that $\{v_i: 3 \text{ does not divide } i\}$ is an independent set of size about $\frac{2m}{3}$, while in a Hamiltonian graph an independent set may only contain at most half of the vertices of the graph. For $m = 6$, $G$ is a circuit of size four, so it is Hamiltonian.
