Grinberg-Introduction-Graph-Theory · Problem 3.9

Multigraphs

Mathematics — Graph Theory · multigraph-degree-sequence-realization

Problem

Let n≥0n \geq 0. Let d1,d2,…,dnd_1, d_2, \ldots, d_n be nn nonnegative integers such that d1+d2+⋯+dnd_1 + d_2 + \cdots + d_n is even. (a) Prove that there exists a multigraph GG with vertex set {1,2,…,n}\{1, 2, \ldots, n\} such that all i∈{1,2,…,n}i \in \{1, 2, \ldots, n\} satisfy deg⁡i=di\deg i = d_i. (b) Prove that there exists a loopless multigraph GG with vertex set {1,2,…,n}\{1, 2, \ldots, n\} such that all i∈{1,2,…,n}i \in \{1, 2, \ldots, n\} satisfy deg⁡i=di\deg i = d_i if and only if each i∈{1,2,…,n}i \in \{1, 2, \ldots, n\} satisfies the inequality ∑j∈{1,2,…,n};j≠idj≥di.(3)\sum_{\substack{j \in \{1,2,\ldots,n\};\\ j \neq i}} d_j \geq d_i. \tag{3} [Remark: The inequality (3) is the ``nn-gon inequality'': It is equivalent to the existence of a (possibly degenerate) nn-gon with sidelengths d1,d2,…,dnd_1, d_2, \ldots, d_n.]

Related theory

Browse the problem library