Regular Graphs: Bounds

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

3 Responses to Regular Graphs: Bounds

  1. Sundar says:

    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?

  2. Sundar says:

    Oops. Well, it’s not vaccuous, as I realise, but “too obvious” that it appeared vaccuous. My bad.

  3. sanket says:

    It is fairly apparent. I just included the theoretical bounds for the sake of completeness. 🙂

%d bloggers like this: