If you're like me you're wondering how people came up with the potential, you can reduce it to another thing with a clever potential function but hopefully one you're familiar with. Also this is a chance for me to practice the hedgehog algorithm :). I will ignore consts and assume $n>4ln(m)$ for simplicity. At the end of the post I will mention some general intuition, but it will be easier to process it after seeing the proof.
In online optimization, one has the multiplicative weights algorithm. I will be using the notation of https://lucatrevisan.wordpress.com/2019/04/22/online-optimization-post-0-definitions/ and I suggest reading the first 2 blogposts (so the link and the next one). Luca even provides nice intuition for the algorithm in blogpost 3.
In any case we do the usual trick- the edges will represent the cost functions represening loss. More specifically since we want two sided control so we will need to duplicate it. I will now be formal:
At time $t$, we define $f^t_1,..,f^t_{2m}$ - so that there are $2m$ experts. Index the edges $e_1 ,..,e_m$. We will be giving our vertices $x_1,..,x_n$ values along the times $t=1,..,n$ one by one.
For $i=1,..,m$, at time $t$ we define $f_i$ to be $x_t$ for $x_t \in \{-1,1\}$ to be decided if $x_t \in e(i)$, and zero otherwise. Similiarly for $j=m+i$ with $i=1,..,m$, except now we put $-x_t$ instead of $x_t$.
It is easy to see that we can always choose $x_t$ so that the algorithm loses a nonnegative amount.
By the regret bound for $T=n$, we get at the end that for each edge, the sum of its vertices at least $-\sqrt{nln(2m)}$, and the sum of minus its vertices is at least $-\sqrt{nln(2m)}$, giving a bound of $\sqrt{nln(2m)}$ on the discpercancy (this seems to be better by a factor of $2$ from the above answer, so hopefully I did not make a mistake).
Now for some explanation for what's going on (this is mostly repeating stuff from the blog post but this might be useful)-
The online learning algorithm allows us to do something amazing- as long as we can adaptively(!) be able to deal local (in terms of doing turn by turn) punches on distributions on a family of functions (a punch means the weighted sum is large), our local punches are guaranteed to combine into a global punch onto each single function.
Here we wanted a global values for the $x_i$ that have large sum of each edge (and so does the minus, but this is just a 'trick'), so we just needed to be able to prove we enlarge locally the weighted sum of ALL edges and antiedges, which was easy by an average argument.