Existence of connected regular and nearly regular graphs

Abstract

For integers $k\ge 2$ and $n\ge k+1$, we prove the following: If $n\cdot k$ is even, there is a connected $k$-regular graph on $n$ vertices. If $n\cdot k$ is odd, there is a connected nearly $k$-regular graph on $n$ vertices.

Cited by in corpus (1)

• Locally Differentially Private Analysis of Graph Statistics