Some progress, will finish later: Convert the problem to the obvious graph theory interpretation. If the graph isn't a tree, take a connected component that is (or an isolated vertices). \newline Assume $v_z$ is the vertice with the highest degree x and let $a_1, a_2, ... a_x$ be the degrees of the adjacent vertices $v_1, v_2, ... v_x$. Now since there are at most $Min(x(x-1), m^3 - x - 1)$ people that x shakes hands with, we have $x(x-1) > (x)(m-1)$ or $x > m$. Now we have $(m-1)x < \sum_{i = 1}^{x} (a_i -1)$ hence $mx+1 \leq \sum_{i=1}^{x} a_i$. \newline Now, for every vertice $v_i$ the number of vertices you can reach by moving twice (excluding $v_1, v_2 ...$) is at least $a_i(m-1) - (x-1) + 1$.\newline So now we use the results to get a lower bound on x. We have $m^3 \geq number of vertices \geq \sum_{i=1}^{x}(a_i(m-1) - (x-1) + 1) + ((m-1)x + 1) + x \geq xm^2 + m + 2x - x^2 $ from this inequality we can conclude that $ x > (m-1)(m)$. This shows how the graph should look with one large vertice, a few medium ant the rest small.

Here's a very clean solution assuming the stronger condition $m(m-1)\ge n^2$. Maybe it can be adapted to solve the entire problem. Assume the contradictory and let $h(v)$ be the number of people that shake hands with vertex $v$. Note that $h(v)\le n-d(v)$ so \[ n-d(v)\ge h(v)\ge (m-1)d(v)\implies d(v)\le \frac nm.\] Now we have \begin{align*} \sum_v h(v) &\le \sum_v \sum_{u\in N(v)} d(u)\\ &= \sum_v d(v)^2\\ &\le \frac{2n^2}{m}, \end{align*}where the last inequality is easily obtained e.g. by smoothing, with rough equality when $2m$ vertices have degree $\tfrac nm$. But by assumption we have \[ \sum_v h(v) > (m-1)\sum_v d(v)= 2n(m-1),\]upon which we get a contradiction.

$sum_v d(v)<= 2n$,so cannot get a contradiction.

Take the obvious graph theory interpretation, letting the graph be $G$. Evidently we may assume $G$ is connected, else we can find a connected component with $|E| \geq |V|$ and win by inductive hypothesis, since any valid $m$ for $G$ will also be valid for this connected component alone. Thus $G$ is either a tree, or a single cycle with a number of trees "branching" off of it. We first translate the condition. The number of people that shake hands with $A$ is evidently almost always equal to $$\sum_{v\sim A} (\deg(v)-1)=-\deg(A)+\sum_{v \sim A} \deg(v).$$The exception is when two vertices adjacent to $A$ share a neighbor other than $A$, which can only ever occur when $A$ is in the unique cycle of $G$, if it exists (actually, this would more strongly require that the cycle has size $4$, but this isn't needed). In this case, the number of people that shake hands with $A$ is one less than this expression. We want to prove that the number of handshakes is at most $-\deg(A)+m\deg(A)$ for some choice of $A$. Thus suppose for contradiction that for all $A$ we have $$\sum_{v \sim A} \deg(v) \geq m\deg(A),$$with equality not holding if $A$ is not part of the cycle of $G$. Now suppose that $G$ is a tree. Root it arbitrarily and suppose that its depth is at least $2$ (we let the root vertex have depth $0$). Let $w$ be the parent of the parent of a vertex on the highest depth. Let $v$ be a child of $w$ with the most children, which are all leaves. Then $v$ has $\deg(v)-1>0$ children, and by letting $A$ be one of its children it follows that $\deg(v) \geq m+1$. Then by taking $A=v$ it follows that $$(\deg(v)-1)+\deg(w)>m(\deg(v)) \implies \deg(w)>(m-1)\deg(v)+1 \geq m^2.$$Finally, by taking $A=w$, we find that the sum of the degrees of the vertices adjacent to $A$ is at least $m\deg(w)>m^3 \geq n$, which is a contradiction. Note that here we only have to use the weaker "equality" version of the assumption. On the other hand, every tree aside from the one with $2$ vertices can be rooted in some way to yield a tree with depth at least $2$. Since the problem is trivial for this case, it follows for all trees. If $G$ is a single cycle $C=v_1\ldots v_k$ with trees branching off, and one of these trees has depth at least $2$ when rooted at its (unique) vertex in $C$, then the above argument still works. Thus suppose that the only trees branching off of $G$ are are single edges. In this case, pick $v_i$ in the cycle with maximal degree. By taking $A=v_i$ we need $$(\deg(v_i)-2)\cdot 1+\deg(v_{i-1})+\deg(v_{i+1}) \geq m\deg(v_i),$$but the LHS is at most $3\deg(v_i)-2$ while the RHS is at least $3\deg(v_i)$, since $m \geq 3$. Thus in this case we reach a contradiction as well, implying the problem statement is indeed true. $\blacksquare$