Graph Theory (Multi-Tree's existence) I'm doing my combinatorics home assignment and got stuck on one of the problems. It's about necessary and sufficient condition of the existence of multitree. Could you solve number 7, please? 

$\mathbf{7}.$ A multitree is a multigraph whose condensation is a tree. Let $n\ge 2$. Let $d_1,d_2,\ldots,d_n$ be positive integers, and let $g$ be the greatest common divisor of the $d_i$. Show that there is a multitree with degree sequence $d_1,d_2,\ldots,d_n$ if and only if $\sum_{i=1}^nd_i/g\ge 2(n-1)$ and for some partition $I,J$ of $[n]$, $\sum_{i\in I}d_i=\sum_{i\in J}d_i$.

 A: HINT: I’ll get you started with an extended hint for one direction, showing that every multitree has a degree sequence with the desired properties.
First show that if $T$ is a tree with degree sequence $d_1,d_2,\ldots,d_n$, then:


*

*$g=1$,  

*$\sum_{i=1}^nd_i=2(n-1)$, and  

*there is a partition of $\{I,J\}$ of $[n]$ such that $\sum_{i\in I}d_i=\sum_{i\in J}d_i$. For this last part use the fact that every tree is bipartite.


Now suppose that we add some duplicate edges to $T$ to make a multitree $M$ whose condensation is $T$. Let the new degree sequence be $d_1',d_2',\ldots,d_n'$, with the vertices listed in the same order.


*

*Show that the third bullet point still holds (with the same partition, in fact) with $d_i'$ substituted for $d_i$.  

*For $1\le i<j\le n$ let $e(i,j)$ be the number of edges between $v_i$ and $v_j$ in $M$. Show that each $e(i,j)$ is a multiple of $g$.


This means that we can group the edges of $M$ into bundles of $g$ parallel edges with no edges left over. We can then replace each bundle by a single edge to get a multitree $M'$ whose degree sequence is $\frac{d_1'}g,\frac{d_2'}g,\ldots,\frac{d_n'}g$.


*

*Show that $\sum_{i=1}^n\frac{d_i'}g\ge 2(n-1)$.


Since every multitree can be constructed in this way, we can conclude that every multitree has a degree sequence with the properties listed in the question.
Added: For the other direction, we’ll first prove by induction on $n$ that if $d_1,d_2,\ldots,d_n$ are positive integers for which there is a partition $\{I,J\}$ of $[n]$ such that $\sum_{i\in I}d_i=\sum_{i\in J}d_i$, then there is a multiforest $F$ with degree sequence $d_1,\ldots,d_n$ such that every edge is between vertices $v_i$ and $v_j$ with $i\in I$ and $j\in J$. (In other words, $\{v_i:i\in I\}$ and $\{v_i:i\in J\}$ form a bipartition of the vertices of $T$.) 


*

*Verify that the result is true if $n=2$.


Now assume that $n>2$, and that the result holds for smaller values of $n$. Let $I=\{r_1,\ldots,r_\ell\}$ and $J=\{s_1,\ldots,s_m\}$, where of course $\ell+m=n$, and assume that $r_1\ge\ldots\ge r_\ell$ and $s_1\ge\ldots\ge s_m$. We may further assume that $d_i=r_i$ for $i=1,\ldots,\ell$ and $d_i=s_{\ell+i}$ for $i=\ell+1,\ldots,n$.


*

*Show that without loss of generality we may assume that $r_\ell\ge s_m$, and that if $r_\ell=s_m$, then $r_1\ge s_1$.  


Suppose first that $r_1=s_m$.


*

*Show that $d_i=g$ for $i=1,\ldots,n$ and $\ell=m$, and show that this implies the existence of the desired multiforest.  


Thus, we may assume that $r_1>s_m$. Let $d_1'=r_1-s_m$, $d_i'=r_i$ for $i=2,\ldots,\ell$, and $d_i'=s_i-\ell$ for $i=\ell+1,\ldots,n-1$. Let $I'=\{1,\ldots,\ell\}$ and $J'=\{\ell+1,\ldots,n-1\}$.


*

*Verify that $\sum_{i\in I'}d_i'=\sum_{i\in J'}d_i'$.


The induction hypothesis now yields a multiforest $F'$ with degree sequence $d_1',\ldots,d_{n-1}'$ such that every edge is between vertices $v_i$ and $v_j$ with $i\in I'$ and $j\in J'$. Add a vertex $v_n$ to $F'$ with $s_m$ edges between it and $v_1$. 


*

*Verify that the resulting multigraph is a multiforest with degree sequence $d_1,\ldots,d_n$, that $I=I'$ and $J=J'\cup\{n\}$, and that every edge is between vertices $v_i$ and $v_j$ with $i\in I$ and $j\in J$.


This completes the induction step.
Now let $d_1,\ldots,d_n$ be positive integers for which there is a partition $\{I,J\}$ of $[n]$ such that $\sum_{i\in I}d_i=\sum_{i\in J}d_i$, and let $g=\gcd(d_1,\ldots,d_n)$. We’ve just shown that there is a multiforest $F$ with degree sequence $d_1,\ldots,d_n$ such that every edge is between vertices $v_i$ and $v_j$ with $i\in I$ and $j\in J$. 


*

*Check that the argument that you used before for multitrees works here to show that the number of edges between any two vertices of $F$ is a multiple of $g$.


We can therefore ‘thin’ $F$ by grouping its edges into bundles of $g$ parallel edges and replace each bundle by a single edge to get a multiforest $F'$ with degree sequence $d_1',\ldots,d_n'$, where $d_i'=\frac{d_i}g$ for $i=1,\ldots,n$. The sets $\{v_i:i\in I\}$ and $\{v_i:i\in J\}$ still form a bipartition of the vertices.
Finally, we’ll show that if $\sum_{i=1}^nd_i'\ge 2(n-1)$, then $F'$ can be modified to yield a multitree $T'$ with vertex sequence $d_1',\ldots,d_n'$; we can then replace each edge of $T'$ with a bundle of $g$ parallel edges to get a multitree $T$ with degree sequence $d_1,\ldots,d_n$. We’ll do this by switching edges to connect the component multitrees of $F'$ without changing the degree of any vertex.
An edge switch works like this. Suppose that we have vertices $u$ and $v$ in one component with $r$ parallel edges between them and vertices $x$ and $y$ in another with $s$ parallel edges between them, where $r>s$. We delete the $s$ edges between $x$ and $y$ and $s$ of the $r$ edges between $u$ and $v$, and we add $s$ edges between $u$ and $x$ and another $s$ edges between $v$ and $y$. This is illustrated below with $r=5$ and $s=3$.



*

*Verify that the degrees of all vertices remain unchanged after the switch, and that the number of components has been reduced by $1$.


We just have to make sure that we can perform enough switches to reduce $F'$ to a multitree. Recall that $\gcd(d_1',\ldots,d_n')=1$.


*

*Show that either there are two edges of $F'$ with different multiplicities, or the multiplicity of every edge of $F'$ is $1$.  

*Show that if every edge of $F'$ has multiplicity $1$, then $F'$ is already connected and hence a multitree (and in fact a tree), and $\sum_{i=1}^nd_i'=2(n-1)$.  

*Show that if there are two edges of $F'$ with different multiplicities, then there are two edges of $F'$ that not only have different multiplicities but are in different components of $F'$.


Given edges with different multiplicities in different components of $F'$, we can perform a switch on them to reduce the number of components by $1$ and repeat the argument until we’ve reduced $F'$ to a multitree.
