Task list filter?
Task rankings
Task tags
«
«
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 VG={1,…,n}.
If k is even, we join with an edge vertices whose numbers differ by at most k2, formally EG={(u,v):|uv|≤k2}.
If k is odd, then n is even. We connect vertices whose numbers differ by at most k−12 (these add to each vertex k−1 neighbors) or when they differ by n2 (opposite vertices). Formally EG={(u,v):|u−v|≤k−12∨|u−v|=n2}.