📂Graph Theory

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) $$
2. 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.