Recipe

Test whether a k-regular graph can exist

Use when: you're given a vertex count n and a target degree k and asked whether a k-regular graph on n vertices exists

Goal: a feasibility verdict (yes or no), the edge count when it exists, and an explicit graph achieving it

Taught in Regular graphs, revisited

1. 1

   Multiply the vertex count n by the target degree k. Handshaking requires that product to be even, since it must equal 2|E|.

   Example

   For n=8 and k=3: nk = 8 \times 3 = 24, which is even.

   • nk is odd — stop; no k-regular graph on n vertices exists, no matter how the edges are arranged.
   • nk is even — the parity test passes; continue to the degree ceiling.

   Why: an odd degree sum could never equal 2|E|, which is always even.

2. 2

   Confirm k \leq n-1. A simple graph forbids loops and repeated edges, so no vertex can be adjacent to more than every other vertex.

   Example

   For n=7 and k=4: k=4 \leq n-1=6, so the degree stays within what 7 vertices allow.

   • k > n-1 — stop; no k-regular graph on n vertices exists, even though nk is even.
   • k \leq n-1 — both conditions hold; a k-regular graph on n vertices exists, continue to the edge count.

   Why: these two conditions together are not just necessary but also sufficient for existence.

3. 3

   Once existence is confirmed, divide the degree sum by two to get the number of edges: |E| = nk/2.

   Example

   For n=12 and k=5: the degree sum is nk = 60, so |E| = 60/2 = 30.

   Why: handshaking says the degree sum always equals 2|E|, so dividing by two recovers the edge count.

4. 4

   Arrange the n vertices in a circle and join each vertex to its nearest neighbors, following the circulant pattern for the parity of k.

   Example

   For n=10 and k=5: join each vertex to its 2 nearest neighbors on each side, then add the edge to the vertex directly opposite it.

   • k is even — join each vertex to its k/2 nearest neighbors on each side; every vertex reaches degree k.
   • k is odd — build the (k-1)-regular circulant first, then join each vertex to the vertex directly opposite it on the circle.

   ⚡ Shortcut

   When k = n-1, skip construction entirely: K_n itself is already (n-1)-regular, since every vertex connects to every other one.

   Why: symmetry guarantees every vertex gains the same number of neighbors, so checking one vertex's degree checks them all.