Task list filter?

Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.

Task rankings

Difficulty level

Task tags

Task type
«
«
«

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 n1. 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 k12 (these add to each vertex k1 neighbors) or when they differ by n2 (opposite vertices). Formally EG={(u,v):|uv|k12|uv|=n2}.

Difficulty level: Moderate task
Solution require uncommon idea
Cs translation
Send comment on task by email