주어진 그래프의 MST를 T라고 합시다. 

인접하지 않은 정점 A, B가 T에서 간선으로 연결되어있다고 가정하죠.

일반성을 잃지 않고 A, B 사이에 연결된 간선 무게가 |A_x - B_x| 라고 하죠. x 축으로 A, B 사이에 있는 정점 C가 존재합니다 (A_x <= C_x <= B_x)

여기서 A, B를 연결하는 간선을 제거하고 A, C 와 C, B를 연결합니다 (이 그래프를 G라고 하죠) G는 N개의 간선으로 이루어져 있고, 연결되어있다는건 자명합니다.

그리고 총 무게 변화는 최대 -|A_x - B_x| + |A_x - C_x| + |C_x - B_x| = 0 입니다. 즉 G의 싸이클에서 간선 아무거나 지워도 T보다 총 무게가 더 작습니다.

T가 MST라는 가정이 모순되니 MST에서 연결된 정점은 인접합니다.

갑사합니다 !! 답글 주신 내용 이해 해보겠습니다 !!

제가 정리한 내용을 공유하기 위해 남깁니다.

위의 jseo님의 논리와 핵심은 같습니다만 조금 더 풀어서 정리한 것입니다.

정답을 구성하는 터널 N-1개 중에서 어떤 한 터널을 택해서 해당 터널이 잇는 행성을 P, Q라고 하자.

정의에 의해 해당 터널의 길이는 |x_P-x_Q|, |y_P-y_Q|, |z_P-z_Q| 중 가장 작은 값이다.

|x_P-x_Q|가 해당 터널의 길이인 경우,

만약 어떤 한 행성 M의 x좌표 x_M이 x_P와 x_Q 사이의 값이라면 다음과 같은 과정을 통해 정답보다 전체 비용 합이 더 작은 조합을 만들 수 있다.

(정답이 정답이 아님, 모순)

1. P, Q를 잇는 해당 터널을 제거한다.

전체 비용은 |x_P-x_Q| 감소하며, Spanning Tree에서 간선 하나를 제거한 것이므로 M은 P와 Q 중에 하나와는 연결되어 있고 다른 하나와는 연결되어 있지 않게 된다.

처음에 P, Q를 정하는 순서를 임의로 정할 수 있으므로 이때 M과 연결되어 있지 않은 행성을 P라고 하자.

2. P와 M 사이에 터널을 새로 건설한다.

정의에 의해 새로 건설한 터널의 길이는 min(|x_P-x_M|, |y_P-y_M|, |z_P-z_M|) 이므로 |x_P-x_M| 이하이다.

건설 후 Spanning Tree 조건을 만족하게 되어 다시 모든 행성이 서로 연결되며, |x_P-x_M| < |x_P-x_Q| 이므로 전체 비용 합은 처음의 정답보다 더 작아진다.

|y_P-y_Q|가 해당 터널의 길이인 경우,

|z_P-z_Q|가 해당 터널의 길이인 경우도 동일한 과정으로 모순이 도출된다.

따라서 정답을 구성하는 터널이 존재하는 축을 기준으로 봤을 때 터널로 이어지는 두 행성 사이에는 다른 행성이 존재해선 안된다.

모든 축에 대해 인접하지 않은 두 정점 A와 B가 있다고 하자.

두 정점을 연결하는데 드는 비용을 결정하는 축의 값에 따라 모든 점을 축 위에 찍어 놓았다고 생각해보자.

A와 B는 사이에 점이 최소 1개 이상 있을 것이다.

이 점들을 r0​,r1​,⋯,rk​라고 이름 붙여 보자.

이렇게 한 후, 모든 간선을(O(N2)의 간선) 추가하고 크루스칼 알고리즘을 수행한다고 해보자.

크루스칼 알고리즘은 가중치가 작은 간선들부터 차례로 검사하므로 E(A,B)를 검사하기 전에 E(A,r0​),E(r0​,r1​),E(r1​,r2​),⋯,E(rk​,B) 들을 먼저 검사했을 것이다.

크루스칼 알고리즘은 간선을 두 가지중 하나로 처리하는데,
1. 간선을 추가
2. 간선이 연결된 두 정점이 이미 하나의 컴포넌트이므로 추가하지 않음.

어떤 경우든 간에 검사한 간선의 양 쪽 정점은 하나의 컴포넌트였거나, 하나의 컴포넌트가 되므로 검사 후에는 반드시 하나의 컴포넌트라는 사실을 알 수 있다.

따라서 E(A,B)를 검사하는 시점에서는 반드시 A,B가 하나의 컴포넌트라는 사실을 알 수 있으므로 E(A,B)는 크루스칼 알고리즘에서 절대 추가되지 않는 간선임을 알 수 있다.

결국 임의의 축에 대해 인접하지 않은 두 정점 사이의 간선은 크루스칼 알고리즘 수행 과정에서 사용되지 않는다는 것을 알 수 있으므로, 인접한 두 정점 사이의 간선만을 이용해도 된다는 것을 알 수 있다.