Graph Theory (Multi-Tree's existence)

Question

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$.

Answer 1

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.