Szabolcs Horvát

A simple algorithm for realizing a degree sequence as a connected graph

Note: A generalized version of this result is now included in the preprint Sz. Horvát and C. D. Modes: Connectivity matters: Construction and exact random sampling of connected graphs.

Introduction

In graph theory, the degree of a vertex is the number of connections it has. For example, the vertices of the below graph have degrees (3, 2, 2, 1).

It is easy to determine the degrees of a graph’s vertices (i.e. its degree sequence), but what about the reverse problem? Given a list of integers, how can we construct a simple graph that has them as its vertex degrees? Does such a graph even exist? This blog post deals with a special case of this problem: constructing connected simple graphs with a given degree sequence using a simple and straightforward algorithm.