Regular Graphs
Table of Contents

Regular Graphs

Definition: A graph $G = (V(G), E(G))$ with $k$ vertices is said to be Regular if all vertices of the graph have the same degree. That is for all of the vertices in the graph, $x_1, x_2, x_3, ..., x_k \in V(G)$ we have $\deg(x_i) = deg(x_j)$ for every $i, j \in \{ 1, 2, ..., k \}$

A graph is said to be $r$-regular when all vertices in the graph have $r$ edges incident to them. For example, here are some $2$-regular graphs:

Screen%20Shot%202014-02-09%20at%2010.42.21%20PM.png

And now let's look at some $3$-regular graphs:

Screen%20Shot%202014-02-09%20at%2010.43.40%20PM.png

Note that regular graphs do not need to be connected graphs or simple graphs. Furthermore, note that since $r$-regular graphs have the all vertices with degree $r$ we have that $\delta (G) = \Delta (G) = r$.

Now one special type of $r$-regular graphs are when $r = 3$ to which we give the following name.

Definition: A graph $G = (V(G), E(G))$ is said to be Cubic if $G$ is $3$-regular.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License