logo

Regular Graph 📂Graph Theory

Regular Graph

Definition 1

  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 200px-Petersen1_tiny.svg.png
  • Platonic Graphs: These are graphs representing Platonic solids. Like the Petersen graph, they are $3$-Regular Graphs, and only the following five exist.
    160px-3-simplex_graph.svg.png 160px-3-cube_column_graph.svg.png 160px-3-cube_t2.svg.png 160px-Icosahedron_A2_projection.svg.png 160px-Dodecahedral_graph.neato.svg.png
  • 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.

20200211_141819.png

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.

20200211_142214.png


  1. Wilson. (1970). Introduction to Graph Theory: p17. ↩︎