Combinatorics and Graph Theory · Problem 5.5.7

Graph Theory — David Guichard

Mathematics — Combinatorics · trees

Problem

A multitree is a multigraph whose condensation is a tree. Let n≥2n \geq 2. Let d1,d2,…,dnd_1, d_2, \ldots, d_n be positive integers, and let gg be the greatest common divisor of the did_i. Show that there is a multitree with degree sequence d1,d2,…,dnd_1, d_2, \ldots, d_n if and only if ∑i=1ndi/g≥2(n−1)\sum_{i=1}^n d_i/g \geq 2(n-1) and for some partition II, JJ of [n][n], ∑i∈Idi=∑i∈Jdi\sum_{i \in I} d_i = \sum_{i \in J} d_i.

Related theory

Browse the problem library