Definition:Regular Graph

Definition

Let $G = \struct {V, E}$ be an simple graph whose vertices all have the same degree $r$.

Then $G$ is called regular of degree $r$, or $r$-regular.

Examples

Incomplete $0$-Regular

The $0$-regular graphs which are not complete are the edgeless graphs $N_n$ of order $n$ for $n > 1$.

For example, $N_2$:

Incomplete $1$-Regular

An example of a $1$-regular graph which is not complete is shown below:

Incomplete $2$-Regular

The $2$-regular graphs which are not complete are the cycle graphs $C_n$ of order $n$ for $n > 3$.

For example, $C_4$:

Note that $C_3$ is both $2$-regular and complete.

Incomplete $3$-Regular

An example of a $3$-regular graph which is not complete is shown below:

Also see

• Definition:Edgeless Graph: a $0$-regular graph.
• Definition:Cycle Graph: a $2$-regular graph.
• Definition:Cubic Graph: a $3$-regular graph.

• Results about regular graphs can be found here.

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.1$: The Degree of a Vertex
• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): graph: 2.
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): graph: 2.
• 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): regular graph
• 2021: Richard Earl and James Nicholson: The Concise Oxford Dictionary of Mathematics (6th ed.) ... (previous) ... (next): regular graph