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.

This entry was posted on Wednesday, March 12th, 2008 at 6:00 am and is filed under computer science, graph theory, maths. You can follow any responses to this entry through the RSS 2.0 feed.
Both comments and pings are currently closed.

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. 🙂