Regular Graph
Definition 1
- A graph is called a Regular Graph if all vertices have the same degree. Specifically, if all vertices have a degree of $r$, it is called a $r$-Regular Graph. In other words, a graph $G$ that satisfies the following is referred to as a $r$-Regular Graph. $$ \deg (v) = r \qquad , \forall v \in V(G) $$
- A $2$-Regular connected graph is called a Cycle.
Examples
Regular Graphs
- Petersen Graph
- Platonic Graphs: These are graphs representing Platonic solids. Like the Petersen graph, they are $3$-Regular Graphs, and only the following five exist.
- Complete Graphs: When the number of vertices in a graph is $n$, the $(n-1)$-Regular Graph becomes a Complete Graph.
Cycles
Cycles represent the simplest form of graphs and receive a lot of interest in pure graph theory. Of course, it’s not exactly about cycle graphs themselves, but about parts within a graph that form a cycle shape. [ NOTE: A graph with just one edge removed from a cycle is also called a Path. ] You can understand why a $2$-Regular is called a cycle just by looking at the shape of a cycle.
The following example explains why a cycle needs to be connected to truly be a cycle. The next graph, consisting of two components, is indeed $2$-Regular, but since it can be represented as a union of two cycles, it is inappropriate to call it a true cycle. Of course, each of $A$ and $B$ is a cycle.
Wilson. (1970). Introduction to Graph Theory: p17. ↩︎