In this post, I discuss a few results about connected regular graphs that are fairly obvious. However, to the best of my knowledge they have not been discussed explicitly in literature.
- If a connected graph of n (n > 2) nodes is regular, then it is at least 2-regular. In other words, the lower bound on the regularity r of a connected graph of more than 2 nodes, is 2.
Proof: Let us start with a minimally connected graph of n > 2 nodes. It is a straight line graph with n−1 edges, in which every node, except the two end nodes of the straight line, is connected to a “predecessor” and a “successor”. To make this regular, we add one more edge between the two end nodes of the straight line. The graph now is a circle, with every node connected to 2 other nodes, thus making it the minimal connected regular graph.
- The upper bound on the regularity r of a n node (n > 0) graph is n − 1.
Proof: In a graph of n nodes, every node can connect to a maximum of n − 1 nodes, forming a complete graph. Hence the above result follows.
- As a corollary of the above result, we have: the lower bound on the number of nodes n required to construct a r regular graph is r + 1.
First Principles 
Isn’t the first result rather vaccuous? A connected regular graph can’t have a regularity less than 2, right? Or am I missing something?
Oops. Well, it’s not vaccuous, as I realise, but “too obvious” that it appeared vaccuous. My bad.
It is fairly apparent. I just included the theoretical bounds for the sake of completeness. 🙂