Regularity

Definition of a $k$-regular Graph

A $\text{graph}$ is called $\text{k-regular}$ if every vertex has the same $\text{degree}$ $k$. In other words, for all $u\in V(G)$ we have $d(u)=k$.

This uniformity means each vertex participates in exactly $k$ edges, giving the graph a highly symmetric structure. Such graphs often serve as models of regular networks in chemistry, physics, and computer science.

Many standard families of graphs are $\text{k-regular}$, including complete graphs $K_n$ which are $(n-1)$-regular, and cycle graphs $C_n$ which are $2$-regular.

$\mathbf{\text{Example}}$
The complete graph $K_5$ on 5 vertices is $\text{4-regular}$, since each vertex connects to the other 4.

$\mathbf{\text{Metaphor}}$
Imagine a roundtable where each of $n$ participants shakes hands with exactly $k$ others; that’s the uniform handshake of a $k$-regular graph.

$0$-regular Graphs

A $\text{0-regular}$ graph has $\text{degree}$ $0$ at every vertex, which means there are no edges at all.

Such graphs consist of $n$ isolated vertices and are often called the empty graph on $n$ vertices, denoted $\overline{K_n}$.

These graphs are trivial in connectivity and have no nontrivial structure or paths, making them a base case in many graph-theoretic arguments.

$\mathbf{\text{Example}}$
An empty graph with 4 vertices has no edges and is $\text{0-regular}$.

$\mathbf{\text{Metaphor}}$
It’s like a party where everyone arrives but nobody talks to anyone else.

$1$-regular Graphs

A $\text{1-regular}$ graph has $\text{degree}$ $1$ at every vertex, so each vertex is incident to exactly one edge.

This forces the graph to decompose into disjoint edges, forming a perfect matching on the vertex set. Such a graph can exist only when the number of vertices $n$ is even.

These graphs are fundamental in matching theory and serve as the simplest nontrivial regular graphs beyond the empty case.

$\mathbf{\text{Example}}$
On 6 vertices, pairing them into 3 disjoint edges yields a $\text{1-regular}$ graph.

$\mathbf{\text{Metaphor}}$
Think of couples at a dance where each person has exactly one partner.

Finite $2$-regular Graphs

A $\text{2-regular}$ graph has $\text{degree}$ $2$ at every vertex, so each vertex lies on exactly two edges.

Every connected component of a finite $2$-regular graph is a cycle $C_m$ for some $m\ge 3$. Thus the entire graph is a disjoint union of cycles.

These graphs appear in routing problems and circular arrangements, where each node has exactly two neighbors.

$\mathbf{\text{Example}}$
A union of a 4-cycle and a 5-cycle on 9 vertices is $\text{2-regular}$.

$\mathbf{\text{Metaphor}}$
Imagine multiple circular necklaces, each bead linked to two neighbors.

Size of an $n$-vertex $k$-regular Graph

The $\text{size}$ of a graph is the number of edges $|E(G)|$. In a $\text{k-regular}$ graph on $n$ vertices, the Handshaking Lemma gives

Solving yields

This formula requires $kn$ to be even, placing a parity constraint on possible $(n,k)$ pairs.

$\mathbf{\text{Example}}$
A $\text{3-regular}$ graph on $8$ vertices has $\frac{3\cdot 8}{2}=12$ edges.

$\mathbf{\text{Metaphor}}$
Counting half the total handshakes when everyone shakes hands $k$ times.

Corollary: Odd $k$ Implies Even Order

If $k$ is $\text{odd}$, then $kn$ is even only when $n$ is even. Therefore any $\text{k-regular}$ graph with odd $k$ must have an even number of vertices.

This corollary restricts the possible sizes of cubic ($3$-regular), $5$-regular, and other odd-regular graphs.

$\mathbf{\text{Example}}$
A $\text{5-regular}$ graph cannot exist on 7 vertices because $5\cdot 7$ is odd.

$\mathbf{\text{Metaphor}}$
You need an even number of dancers if each dancer pairs off an odd number of times.

$3$-regular Graphs and the Decomposition Problem

$\text{3-regular}$ (cubic) graphs are more intricate; classic examples like the Petersen graph demonstrate nontrivial symmetry and no simple characterization.

A central open question asks whether every cubic graph can be decomposed into a disjoint union of a $\text{1-regular}$ subgraph (perfect matching) and a $\text{2-regular}$ subgraph (union of cycles).

This decomposition relates to edge-coloring theorems and factorization in regular graphs, and remains an area of active research.

$\mathbf{\text{Example}}$
The Petersen graph is a $3$-regular graph that does not decompose into a perfect matching plus cycles in the obvious way.

$\mathbf{\text{Metaphor}}$
It’s like trying to split a sturdy three-legged stool into one-leg and two-leg pieces that still stand.

Conclusion

We defined $\text{k-regular}$ graphs, explored the trivial cases of $0$-, $1$-, and $2$-regularity, and derived the size formula $|E|=\frac{kn}{2}$.

The parity corollary shows odd $k$ forces even order, shaping the landscape of possible regular graphs.

Finally, we highlighted the complexity of cubic graphs and the intriguing decomposition problem connecting matchings and cycles.