Construction of regular graphs
Task number: 4174
For every two positive integers \( k, n \) such that \( k < n \) and the product \( kn \) is even, find an example of a \( k \)-regular graph on \( n \) vertices.
Hint
Consider first even \(k=2{,}4,…\)
Solution
Note first that both conditions are necessary: The maximum degree in a graph on \( n \) vertices is \( n-1 \). Furthermore, from the parity principle, there cannot be a graph on an odd number of vertices where all degrees are odd.
For the construction, choose \( V_G = \{1,…, n \} \).
If \( k \) is even, we join with an edge vertices whose numbers differ by at most \( \frac{k}2 \), formally \( E_G = \{(u, v) : | uv | \le \frac{k}2 \} \).
If \( k \) is odd, then \( n \) is even. We connect vertices whose numbers differ by at most \( \frac{k-1}2 \) (these add to each vertex \( k-1 \) neighbors) or when they differ by \( \frac{n}2 \) (opposite vertices). Formally \( E_G = \{(u, v): | u-v | \le \frac{k-1}2 \vee | u-v | = \frac{n}2 \} \).
