The imbalance theorem

The imbalance conjecture is now a theorem. James Alexander Schreib and Yousof Yavari posted a proof last week. What does the conjecture theorem say? Start with a graph G and for every edge, calculate the absolute value of the difference of the degree of each end. Then the theorem says there exists another graph H whose vertices have degrees corresponding to the differences of degrees in G. For example, let G be the graph below. The edges from the top red vertex A to each of the blue vertices around it all have degree difference 5 because A has degree 6 and the vertices a0 to a4 have degree 1. The edge between the two red vertices, A and B, has degree difference 2. The remaining vertices have degree difference 3. So the multiset of degree differences is {5, 5, 5, 5, 5, 2, 3, 3, 3} The imbalance theorem says there exists a graph H whose nodes have these degrees. Here is an example of such an H. Note that in H, the 5 red nodes have degree 5, the single green node has degree 2, and the…