조건을 만족하는 그래프를 만들 수 있는 필요충분조건은 가 이상의 짝수인 것이다. 이 조건을 만족하지 않으면 -1을 출력한다.
조건을 만족하면 먼저 정점을 번호 순서대로 원형으로 잇는다. 즉, 인 각 에 대해 간선 을 추가하고, 간선 을 추가한다. 이어서 인 각 에 대해 간선 을 추가한다.
이렇게 추가하는 간선은 모두 개이다. 따라서 먼저 이 개수를 출력한 뒤, 위 순서대로 각 간선을 바로 출력하면 된다.
구성할 수 있는 경우의 시간 복잡도는 이며, 간선을 저장하지 않고 바로 출력하므로 추가 공간 복잡도는 이다. 구성할 수 없는 경우에는 시간이 걸린다.
증명
각 정점의 차수가 이면 모든 정점의 차수 합은 이다. 간선 하나는 양 끝점의 차수에 각각 씩 기여하므로 차수 합은 간선 개수의 두 배와 같다. 따라서 는 짝수이고, 도 짝수여야 한다.
자기 자신을 잇는 간선과 중복 간선이 없으므로 각 정점은 서로 다른 세 정점과 연결되어야 한다. 따라서 도 필요하다.
Solution written by GPT6
이제 가 이상의 짝수라고 하자. 번호 순서대로 원형으로 잇는 간선은 각 정점에 서로 다른 두 이웃을 만든다. 추가한 간선 들은 각 정점을 정확히 한 번씩 끝점으로 사용하므로, 각 정점에 간선이 하나씩 더 연결된다.
추가한 간선은 서로 다른 두 정점을 잇는다. 또한 이므로 원 위에서 마주 보는 두 정점은 이웃한 정점이 아니다. 따라서 추가한 간선은 원형으로 이은 간선과 겹치지 않는다. 추가한 간선들끼리도 끝점이 겹치지 않으므로 중복되지 않는다.
그러므로 구성한 그래프에는 자기 자신을 잇는 간선과 중복 간선이 없고, 모든 정점의 차수는 정확히 이다. 필요조건을 만족할 때 항상 이러한 그래프를 만들 수 있으므로 제시한 조건은 충분조건이기도 하다.
