Regular Graphs: When All Vertices Are Equal

In the diverse world of graphs, regular graphs stand out for their beautiful symmetry and uniform structure. These special graphs have a property that makes them particularly elegant: every vertex has exactly the same degree.

What is a Regular Graph?

Definition: A graph in which all vertices have the same degree is called a regular graph.

More specifically, if every vertex in a graph has degree $k$, we call it a $k$-regular graph.

The Beauty of Uniformity

Think of a regular graph as the graph theory equivalent of a perfectly balanced system:
- In a social network: everyone has exactly the same number of friends
- In a communication network: every node has the same number of connections
- In molecular chemistry: atoms with identical bonding patterns

This uniformity gives regular graphs special properties and makes them important in both theoretical studies and practical applications.

Understanding $k$-Regular Graphs

The Notation

When we say a graph is $k$-regular, we mean:
- Every vertex has degree exactly $k$
- No vertex has more or fewer than $k$ edges
- The degree sequence is simply $[k, k, k, ..., k]$ (repeated $n$ times for a graph of order $n$)

Example: A 3-Regular Graph

Let’s examine a 3-regular graph of order 6:

In this graph:
- There are 6 vertices (order = 6)
- Each vertex has degree 3 (it’s 3-regular)
- Degree sequence: $[3, 3, 3, 3, 3, 3]$
- Every vertex connects to exactly 3 other vertices

Simple Examples

1-Regular Graphs:
A 1-regular graph is just a collection of disconnected edges (a perfect matching).

Example with order 4:

Each vertex has degree 1.

2-Regular Graphs:
A 2-regular graph forms one or more disjoint cycles.

Example with order 5 (a pentagon):

Each vertex has degree 2, forming a single cycle.

Complete Graphs:
The complete graph $K_n$ is $(n-1)$-regular because each vertex connects to all other $n-1$ vertices.

For example, $K_4$ is 3-regular:

Practice Problems: Constructing Regular Graphs

Now it’s your turn! Try to construct the following regular graphs. Think about what’s possible and what constraints exist.

Challenge Problems

1. 1-regular graph of order 2
   - How many edges needed?
   - Can you draw it?

2. 1-regular graph of order 6
   - How would this look?
   - How many separate components?

3. 2-regular graph of order 3
   - What shape does this form?

4. 2-regular graph of order 5
   - What geometric shape appears?

5. 4-regular graph of order 5
   - Is this even possible? Why or why not?

6. 4-regular graph of order 6
   - How many edges will this have?

7. 4-regular graph of order 7
   - Think carefully - can this exist?

8. 5-regular graph of order 6
   - What does this look like?

Hint for Construction

The Edge Formula for Regular Graphs

Here’s an important question: How many edges does a $k$-regular graph of order $n$ have?

Deriving the Formula

Let’s think through this step by step:

1. Start with the Handshaking Lemma:
   $$\sum_{i=1}^{n} \deg(v_i) = 2|E|$$

2. For a $k$-regular graph: Every vertex has degree $k$, so:
   $$\sum_{i=1}^{n} \deg(v_i) = \underbrace{k + k + k + ... + k}_{n \text{ times}} = nk$$

3. Substitute into the Handshaking Lemma:
   $$nk = 2|E|$$

4. Solve for number of edges:
   $$|E| = \frac{nk}{2}$$

The Formula

For a $k$-regular graph of order $n$:

$$\boxed{|E| = \frac{nk}{2}}$$

Examples

Let’s verify with our 3-regular graph of order 6:
- $n = 6$, $k = 3$
- $|E| = \frac{6 \times 3}{2} = \frac{18}{2} = 9$ edges

Check: If each of 6 vertices has degree 3, total degree sum is 18, which equals $2 \times 9$. ✓

The Odd-Odd Impossibility

The edge formula reveals a crucial constraint about regular graphs.

The Problem with Odd Numbers

Notice that $|E| = \frac{nk}{2}$ must be a whole number (you can’t have half an edge!).

This means: $nk$ must be even.

When is $nk$ Even?

$nk$ is even when:
- $n$ is even (regardless of $k$), OR
- $k$ is even (regardless of $n$), OR
- Both are even

$nk$ is odd when:
- Both $n$ and $k$ are odd

The Impossibility Theorem

Theorem: A $k$-regular graph of order $n$ cannot exist if both $n$ and $k$ are odd.

Proof: If both $n$ and $k$ are odd, then $nk$ is odd. This means $\frac{nk}{2}$ is not an integer, which is impossible since the number of edges must be a whole number. ∎

Practical Examples

Possible Regular Graphs:
- 3-regular, order 4: $|E| = \frac{4 \times 3}{2} = 6$ ✓ (even order)
- 4-regular, order 5: $|E| = \frac{5 \times 4}{2} = 10$ ✓ (even degree)
- 2-regular, order 8: $|E| = \frac{8 \times 2}{2} = 8$ ✓ (both even)

Impossible Regular Graphs:
- 3-regular, order 5: $|E| = \frac{5 \times 3}{2} = 7.5$ ✗ (both odd!)
- 5-regular, order 7: $|E| = \frac{7 \times 5}{2} = 17.5$ ✗ (both odd!)
- 1-regular, order 3: $|E| = \frac{3 \times 1}{2} = 1.5$ ✗ (both odd!)

This is why problem 5 (4-regular of order 5) is solvable, but a 5-regular of order 5 would be impossible!

Solutions to Practice Problems

Now that you’ve tried the problems, let’s check which ones are possible:

Special Types of Regular Graphs

Cycles ($C_n$)

All cycles are 2-regular graphs. Every vertex in a cycle has exactly 2 neighbors.

$C_3$: Triangle (2-regular, order 3)

$C_4$: Square (2-regular, order 4)

$C_5$: Pentagon (2-regular, order 5)

Complete Graphs ($K_n$)

The complete graph $K_n$ is $(n-1)$-regular. Every vertex connects to all other vertices.

$K_3$: 2-regular (triangle)

$K_4$: 3-regular (tetrahedron graph)

$K_5$: 4-regular

Platonic Solids

The graphs of the Platonic solids are all regular:

Tetrahedron: 3-regular (same as $K_4$)

Cube: 3-regular, order 8

The cube graph has 8 vertices (the corners of a cube) and 12 edges. Each vertex connects to exactly 3 other vertices.

Octahedron: 4-regular, order 6

The octahedron has 6 vertices and 12 edges. Each vertex has degree 4.

Dodecahedron: 3-regular, order 20

Note: Due to its complexity (20 vertices, 30 edges), the dodecahedron graph is best explored in 3D visualization tools.

Icosahedron: 5-regular, order 12

The icosahedron has 12 vertices and 30 edges. Each vertex connects to 5 others, making it 5-regular.

Real-World Applications

Network Design

Regular graphs are useful in designing robust networks where:
- Load is evenly distributed (each node handles the same traffic)
- Fault tolerance is uniform (losing any node has the same impact)
- Routing algorithms can be simplified

Chemistry

Many molecules have regular graph structures:
- Benzene ($C_6H_6$): Carbon atoms form a 2-regular hexagon
- Methane ($CH_4$): Central carbon connects to 4 hydrogens (related to $K_5$ with one vertex removed)

Coding Theory

Regular graphs appear in error-correcting codes and network coding schemes where uniform properties are desired.

Advanced Properties

Eigenvalues

Regular graphs have special spectral properties. For a $k$-regular graph:
- The largest eigenvalue of the adjacency matrix is $k$
- This eigenvalue corresponds to the all-ones eigenvector

Random Regular Graphs

In probability and combinatorics, random $k$-regular graphs are studied to understand typical properties of graphs with uniform degree distribution.

Strongly Regular Graphs

A special subclass where not only is every vertex’s degree the same, but also:
- Any two adjacent vertices have the same number of common neighbors
- Any two non-adjacent vertices have the same number of common neighbors

Summary

Key Takeaways:

✓ Definition: A regular graph has all vertices with the same degree

✓ $k$-Regular: Each vertex has degree exactly $k$

✓ Edge Formula: $|E| = \frac{nk}{2}$ for a $k$-regular graph of order $n$

✓ Impossibility: Cannot have both $n$ and $k$ odd (would require fractional edges)

✓ Special Cases:
- Cycles are 2-regular
- Complete graphs $K_n$ are $(n-1)$-regular
- Perfect matchings are 1-regular

✓ Applications: Network design, molecular chemistry, coding theory, and combinatorics

The Fundamental Rule:

For a regular graph to exist, the product $nk$ must be even. This means at least one of $n$ or $k$ must be even.

Try constructing your own regular graphs in our interactive playground and experiment with different values of $n$ and $k$!