#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/3/problems/g

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/3/problems/g

Repovive

Tree Desompisition - Repovive Premier Round 2 | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

3G. Tree Desompisition

3000 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Page 1

We need to partition the edges of $K_n$ into $T=\frac{n}{2}$ spanning trees. In every tree, each vertex has degree either $1$ or $d$ .

Fix one tree and let $m$ be the number of vertices of degree $d$ in this tree. Then the remaining $n-m$ vertices have degree $1$ , and by the handshake lemma: $m\cdot d + (n-m)\cdot 1 = 2(n-1)$ .

Rearranging gives: $m(d-1)=n-2$ .

So $d-1$ must divide $n-2$ .

Now look at all $T$ trees together. For a fixed vertex $v$ , let $x_v$ be the number of trees where $v$ has degree $d$ . In the other $T-x_v$ trees, it has degree $1$ . Hence the total degree of $v$ across all trees equals: $x_v\cdot d + (T-x_v)\cdot 1 = T + x_v(d-1)$ , so it is congruent to $T$ modulo $d-1$ .

But across the whole decomposition, the total degree of $v$ is exactly its degree in $K_n$ , which is $n-1$ . Therefore: $n-1 \equiv T \pmod{d-1} \quad\Longrightarrow\quad \frac{n}{2}-1 \equiv 0 \pmod{d-1} \quad\Longrightarrow\quad n \equiv 2 \pmod{2(d-1)}.$

So a necessary condition is: $(n-2)\bmod (2(d-1)) = 0$ .

We need to partition the edges of $K_n$ into $T=\frac{n}{2}$ spanning trees. In every tree, each vertex has degree either $1$ or $d$ .

Fix one tree and let $m$ be the number of vertices of degree $d$ in this tree. Then the remaining $n-m$ vertices have degree $1$ , and by the handshake lemma: $m\cdot d + (n-m)\cdot 1 = 2(n-1)$ .

Rearranging gives: $m(d-1)=n-2$ .

So $d-1$ must divide $n-2$ .

So a necessary condition is: $(n-2)\bmod (2(d-1)) = 0$ .