A valid graph exists if and only if is even and at least . If this condition is not satisfied, output -1.
Otherwise, first connect the vertices in a cycle in numerical order. Add the edge for each , and add the edge . Then add the edge for each .
The total number of edges added is . Output this number first, then output each edge directly in the order described above.
When a graph can be constructed, the time complexity is . The auxiliary space complexity is because the edges can be output without storing them. An impossible case takes time.
Proof
If every vertex has degree , the sum of all vertex degrees is . Each edge contributes to the degree of each of its two endpoints, so the degree sum is twice the number of edges. Therefore, is even, which means that must be even.
Since self-loops and duplicate edges are forbidden, each vertex must be connected to three distinct other vertices. Thus, is also necessary.
Solution written by GPT6
Now suppose that is even and at least . The cycle connects each vertex to two distinct neighbors. The added edges use every vertex as an endpoint exactly once, giving each vertex one additional incident edge.
Each added edge connects two distinct vertices. Since , opposite vertices on the cycle are not adjacent. Thus, none of the added edges duplicates a cycle edge. The added edges share no endpoints with one another, so they do not duplicate one another either.
The resulting graph therefore has no self-loops or duplicate edges, and every vertex has degree exactly . Such a graph can always be constructed when the necessary conditions hold, proving that they are sufficient as well.
