A regular graph is a graph wherein all nodes in the graph have the same degree. In an r-regular graph, all nodes have a degree r. The number r is called the regularity of a regular graph. Regular graphs are undirected. (At least, I have not seen it to be defined for directed graphs.) They need not be connected. So, a 0-regular graph is a set of nodes; A 1-regular graph is a set of disconnected edges; and so on.
Another way to define regular graphs is to say the following: if in a graph the minimum degree is equal to the maximum degree, the graph is regular.
What I am more interested in are connected regular graphs. Despite the fact that connected regular graphs exhibit interesting properties, there does not seem to be an extensive body of literature on them. Nonetheless, in this series of posts, I will try to put down as much of my understanding of regular graphs as possible. In this series of posts, regular graphs mean connected regular graphs unless otherwise mentioned.
Let us first start with some basic properties of regular graphs.
- Since the total degree of any graph is even (2 * no of edges), regular graphs with
evenodd regularity cannot be constructed with odd number of nodes. For example, we cannot have a 3-regular graph with 7 nodes. (Connectedness does not matter.) - Degree distribution is uniform for regular graphs.
I had some misconceptions regarding regular graphs until recently. I had imagined that regularity corresponds to connectivity, which is untrue.
Regularity need not correspond to connectivity. An r-regular graph can have a connectivity value much less than r.- On a related note, betweenness centrality distribution need not be uniform for regular graphs. It can be skewed. This is clear from the graph below.
Regularity need not correspond to connectivity. An r-regular graph can have a connectivity value much less than r.
What this implies is that regular graphs are robust only to a certain extent. They ensure uniform degree distribution but not uniform centrality distribution. Centrality distribution is a better measure of robustness than degree distribution.
First Principles 
“regular graphs with even regularity cannot be constructed with odd number of nodes”
Don’t you mean “regular graphs with odd regularity cannot be constructed with odd number of nodes”?
Oops..you are right. Thanks, Siddhartha.