Astra가 푼 60년 난제 에르되시–쇼시 추측에 대해 알아보자

점들을 충분히 많이 연결하면, 원하는 나뭇가지 모양을 반드시 찾을 수 있을까? 이게 에르되시–쇼시 추측임.

1. 어떤 모양을 찾는 건데?

모든 점이 이어져 있고 고리는 없는 구조를 ‘트리’라고 함. 일자로 이어져도 되고, 여러 갈래로 갈라져도 됨.

모양이 휘어도 상관없음. 어떤 점끼리 연결됐는지가 중요함.

2. 원래 그림에서 선만 골라내기

점 4개를 모두 연결한 뒤, 있던 선 중 일부만 골라 봄.

점 위치는 그대로이고, 파란 실선만 고른 선임. 회색 점선은 이번에 쓰지 않은 선임. 점 4개짜리 트리는 위의 두 종류가 전부임.

3. 얼마나 많이 연결돼야 할까?

점 4개짜리는 평균 2 초과, 점 5개짜리는 3 초과가 기준임. 위 그림은 점마다 선이 3개씩 닿으므로 평균도 3. 기준을 만족함.

평균 연결 수＝선 개수 × 2 ÷ 점 개수. 선 하나가 양 끝의 점에 각각 한 번씩 잡히기 때문임.

4. 점 5개로 늘리면?

이번에는 점 5개를 모두 연결하되 D–E 선만 뺌. 평균은 (4＋4＋4＋3＋3) ÷ 5＝3.6이라 기준인 3을 넘음.

점 5개짜리 트리는 이 세 종류가 전부임. 같은 배치에서 선 4개씩만 골라 모두 찾았음. 모양마다 같은 점과 선을 다시 써도 됨.

5. 연결이 적은 점이 있어도 됨

점 4개를 모두 연결하고, D에만 연결된 E를 붙인 경우임.

평균은 14 ÷ 5＝2.8. E의 연결은 하나뿐이어도 점 4개짜리 기준인 2를 넘음. 각 점이 아니라 전체 평균이 기준이고, 원래 연결망의 모든 점을 쓸 필요도 없음.

6. 기준을 못 넘으면?

왼쪽은 평균이 정확히 2지만, 각 덩어리에 점이 3개뿐이라 점 4개짜리 트리를 못 찾음. 그래서 ‘2 이상’이 아니라 ‘2 초과’임.

반대로 오른쪽은 평균 1.5여도 별 모양은 있음. 즉 기준을 넘으면 모든 모양이 보장되고, 못 넘으면 평균만으로는 보장할 수 없다는 뜻임.

7. Astra가 한 일

2026년 9월 14일 공개된 옥스퍼드 Riordan·Scott의 논문은 Astra가 이 추측의 완전한 증명을 찾았다고 설명함. 연구진은 증명을 간소화하고 관련 추측에도 적용했음.

핵심은 작은 그림 몇 개를 확인한 것이 아니라, 모든 크기와 연결 방식에서 성립하는 논증을 제시했다는 점임. 출처는 공개 프리프린트임.

---------------- 여기서부터는 핵심 보조정리+결론 ----------------

8. 어떻게 증명했는지, 한 단계씩 따라가 보기

여기부터는 증명의 흐름임. 필요한 개념부터 다시 설명하므로 이 부분만 읽어도 됨. 핵심 보조정리 하나의 증명만 생략하고, 그것을 받아들이면 결론이 왜 나오는지 끝까지 연결하겠음.

① 먼저, 무엇을 증명하려는 건가?

‘트리’는 모든 점이 이어져 있으면서 고리는 없는 모양임. 일자나 나뭇가지 모양을 생각하면 됨. 원래 연결망에서 일부 점과 선을 골라 이런 모양을 찾는 문제임. 고르지 않은 선은 무시해도 됨.

원하는 트리의 점 개수를 k, 원래 연결망의 점 하나당 평균 연결 수를 d라고 쓰겠음. 선 하나는 양 끝에서 한 번씩 세므로 d＝선 개수 × 2 ÷ 점 개수임.

증명할 내용은 “d가 k−2보다 크면, 원하는 점 k개짜리 트리를 반드시 찾을 수 있다”임. 예를 들어 점 5개짜리라면 평균 연결 수가 3을 넘는 경우임.

② 원하는 모양에서 끝점 하나를 떼어냄

원하는 트리를 T라고 부르자. 여기서 선이 하나만 달린 점을 하나 고름. 이런 점을 ‘끝점’ 또는 ‘잎’이라고 함. 점이 둘 이상인 트리에는 반드시 끝점이 있음. 트리 안에서 가장 길게 이어진 길의 양 끝을 보면 됨.

끝점 하나와 거기에 달린 선을 떼어내도, 나머지는 여전히 트리임. 가운데 연결을 끊은 것이 아니므로 남은 점들이 떨어지지 않고, 새로운 고리가 생길 일도 없기 때문임. 이 작은 트리를 S라고 하겠음.

그림에서는 E와 A–E 선을 떼었음. T에는 점이 5개, S에는 4개가 남음. 회색 E는 떼어낸 점을 표시한 것이며 S에 포함되지 않음.

중요한 것은 다시 붙일 자리가 A로 정해져 있다는 점임. 아무 점에나 붙이면 다른 모양이 될 수 있음. 일반적으로 이 ‘붙일 자리’를 r이라고 쓰겠음.

③ 작은 트리를 찾는 것만으로는 부족함

원래 연결망 안에서 S를 찾았다고 해 보자. 여기서 r에 연결된 선 하나를 더 고르면 끝날 것 같지만, 그 선의 반대쪽 점을 이미 S에서 쓰고 있을 수도 있음.

그러면 점이 하나 늘어나지 않음. 우리에게 필요한 것은 r에서 출발해서, S에 쓰이지 않은 새 점으로 이어지는 선임. 그 선이 있으면 끝점을 복구해 정확히 T를 만들 수 있음.

④ 점들에 순서를 붙여서 ‘새 점’임을 보장함

원래 연결망의 모든 점을 1번째, 2번째, 3번째…로 나열해 보자. 연결 관계를 바꾸는 게 아니라, 점들에 앞뒤 순서만 정하는 것임.

그 순서에서 다음 조건을 만족하는 선을 셈.

1. 선의 한쪽 끝은 맨 첫 번째 점이어야 함.
2. 붙일 자리 r이 그 첫 점에 놓이도록, 작은 트리 S를 찾을 수 있어야 함.
3. 선의 반대쪽 끝은 그 S의 모든 점보다 뒤에 있어야 함.

그림에서는 순서가 A, B, C, D, E임. 파란 트리 S는 A·B·C·D를 쓰고, 붙일 자리 A가 맨 앞임. 주황색 A–E 선의 끝 E는 S의 모든 점보다 뒤에 있음.

따라서 E가 S에서 이미 사용된 점일 가능성은 없음. 주황색 선을 붙이면 점이 정확히 하나 늘어나고, 원래 원했던 T가 완성됨.

이 조건을 만족하는 선을 아래에서는 ‘붙일 선’이라고 부르겠음. S를 놓는 방법이 여러 개라면, 그중 하나라도 조건을 만족할 때 그 선을 셈. 같은 선은 한 번만 세고, 조건에 맞는 선이 없으면 0개로 셈.

⑤ 여기서 핵심 보조정리가 등장함 >>> Astra가 증명한 핵심 부분

순서를 바꾸면 S를 놓을 수 있는 자리도, 붙일 선의 개수도 달라짐. 그렇다면 가능한 모든 순서에서 센 개수를 평균 내면 얼마나 될까?

이 보조정리의 증명은 여기서 생략함. 어려운 수학은 이 평균의 하한을 보장하는 데 들어가 있음. 이제부터는 이 정리가 참이라는 전제에서, 추측이 어떻게 따라오는지만 보면 됨.

⑥ ‘평균이 양수’라는 게 왜 중요한가?

숫자로 먼저 보자. 점 5개를 모두 연결하되 D–E 선만 빼면 선은 9개, 평균 연결 수는 d＝9 × 2 ÷ 5＝3.6임. 이 안에서 그림 6의 점 5개짜리 T를 찾으려는 상황임.

끝점 하나를 뗀 S에는 점이 4개이므로 m＝4. 보조정리에 대입하면 붙일 선의 평균은 3.6−4＋1＝0.6개 이상임.

한 번 셀 때는 선이 0개, 1개처럼 정수로 나오지만, 여러 경우를 평균 내면 0.6 같은 소수가 나와도 이상하지 않음. 핵심은 0보다 크다는 것임.

이 예시는 점 순서가 5 × 4 × 3 × 2 × 1＝120가지뿐이라 직접 셀 수도 있음. 그림 6의 S와 붙일 자리를 기준으로 계산하면, 108가지에서는 붙일 선이 1개, 12가지에서는 0개임. 평균은 108 ÷ 120＝0.9개로, 보조정리가 보장한 최소값 0.6보다 큼.

여기서 점의 이름은 원래 연결망의 점을 구분하는 표식임. S를 찾을 때는 그 이름까지 맞출 필요 없이 연결 모양과 붙일 자리만 맞추면 됨. 붙일 자리 역시 순서에 따라 원래 연결망의 다른 점에 놓일 수 있음.

모든 경우가 0개라면 평균도 0이어야 함. 따라서 평균이 양수라는 사실만으로도, 적어도 한 순서에는 붙일 선이 있다는 결론이 나옴. 모든 순서에서 성공할 필요는 없음.

120가지의 집계는 이 글의 설명용 예시를 직접 계산한 결과임. 이 작은 예시가 일반적인 증명을 대신하는 것은 아님.

⑦ 이제 점이 몇 개든 똑같이 계산함

다시 점 k개짜리 T로 돌아가자. 끝점 하나를 뗐으므로 작은 트리의 점 개수는 m＝k−1임. 보조정리는 붙일 선의 평균이 다음 값 이상이라고 말함.

d−m＋1
＝d−(k−1)＋1
＝d−k＋2

우리가 처음에 가정한 조건은 d＞k−2였음. 양쪽에서 k−2를 빼면 d−k＋2＞0임. 따라서 붙일 선의 평균도 반드시 양수임.

그러면 적어도 한 순서에는 붙일 선이 존재함. 그 선과 조건에 맞는 S를 고르면, S에서 쓰지 않은 새 점이 정확히 r에 붙음. 끝점 하나가 복구되었으므로 원하는 T가 완성됨.

⑧ 왜 ‘모든 트리’에 대한 증명이 되는가?

앞에서 원하는 트리 T의 끝점을 떼어 S를 만들었음. 하지만 이것은 찾고 싶은 모양을 작게 만든 것이지, 원래 연결망 안에서 S를 이미 찾았다는 뜻은 아님.

그렇다면 S가 실제로 있는지는 누가 보장할까? 보조정리가 S와 붙일 선의 존재를 함께 보장함.

‘붙일 선’으로 세려면, 그 선에 대응하는 S도 연결망 안에 있어야 함. S를 놓을 방법이 없는 순서에서는 당연히 0개로 셈. 그런데 보조정리에 따르면, d＞k−2일 때 이 개수의 평균이 양수임.

따라서 어떤 순서에서는 S와 붙일 선이 함께 존재해야 함. 그 S에 새 끝점을 붙이면 T가 완성됨. 작은 트리의 존재를 따로 가정할 필요가 없는 이유임.

그럼 귀납법은 어디에 들어갔을까?

증명을 생략한 보조정리 자체에 들어감. 논문은 작은 트리의 점 개수 m에 대해 귀납법을 사용함.

• 시작: m＝1이면 S는 점 하나뿐임. 첫 점에 연결된 모든 선이 조건을 만족하고, 모든 순서에서 평균을 내면 정확히 d개임. 보조정리의 식 d−m＋1도 d가 됨.
• 다음 단계: 더 작은 트리들에서 보조정리가 성립한다고 가정하고, 이를 이용해 점이 m개인 트리에서도 성립함을 증명함. 가지를 나누고 순서를 바꾸며 선을 세는 어려운 부분이 여기에 있음.

이렇게 보조정리가 모든 크기와 모양의 트리에 대해 확보되면, 우리가 고른 T에서 끝점을 떼어 얻은 S에도 적용할 수 있음.

처음에 T의 모양은 아무것도 제한하지 않았음. 따라서 일자든 별 모양이든, 원하는 점 k개짜리 트리를 무엇으로 고르더라도 같은 논증이 성립함. 이것으로 추측의 결론이 나옴.

출처: A short proof of the Erdős–Sós Conjecture
그림은 이해를 돕기 위해 별도로 구성한 예시임.