(유한) 선형 그래프(linear graph) 는 하우스도르프 공간으로, 유한 개의 호(arc)들의 합집합으로 쓰이며, 임의의 두 호는 기껏해야 공통 끝점에서만 교차한다. 이 호들을 그래프의 변(edge) 이라 하고, 호들의 끝점들을 그래프의 꼭짓점(vertex) 이라 한다.
선형 그래프는 수학에서 많은 실생활 현상을 모델링하는 데 사용되지만, 여기서는 단순 닫힌 곡선의 일반화라고 할 수 있는 흥미로운 공간으로만 다룰 것이다.
임의의 그래프는 그 꼭짓점들을 나열하고 어떤 꼭짓점 쌍 사이에 변이 있는지를 명시함으로써 (동형사상을 제외하고) 완전히 결정된다는 점에 주목하자.
예제 1
만약 가 정확히 개의 꼭짓점을 포함하고, 의 임의의 두 서로 다른 꼭짓점 쌍에 대해 그들을 잇는 변이 존재한다면, 를 개의 꼭짓점을 갖는 완전 그래프(complete graph on n vertices) 라 하고 으로 표기한다. 몇 가지 그러한 그래프가 그려져 있다. 처음 세 그래프는 의 부분공간으로 그려져 있지만, 네 번째 그래프는 의 부분공간으로 그려져 있음을 주목하자. 약간의 실험을 해보면 이 그래프는 사실 에 매장될 수 없음을 확신하게 될 것이다. 우리는 이 결과를 곧 증명할 것이다.
예제 2
또 다른 흥미로운 그래프는 고전적인 퍼즐에서 비롯된다: “세 채의 집 와 세 가지 설비 (가스), (수도), (전기)가 주어졌을 때, 연결선들이 서로 교차하지 않게 각 설비를 각 집에 연결할 수 있는가?” 수학적으로 공식화하면, 이것은 그림에 그려진 그래프, 즉 설비 그래프(utilities graph) 가 에 매장될 수 있는지에 대한 질문일 뿐이다. 다시 한번, 약간의 실험을 해보면 그럴 수 없음을 확신하게 될 것이고, 우리는 이 사실을 곧 증명할 것이다.
정의
세타 공간(theta space) 는 하우스도르프 공간으로, 세 개의 호 의 합집합으로 쓰이며, 임의의 두 호는 정확히 그들의 끝점에서만 교차한다. (공간 는 물론 그리스 문자 세타()와 동형이다.)
정의된 대로라면 세타 공간 는 선형 그래프가 아닌데, 문제의 호들이 공통 끝점보다 더 많이 교차하기 때문이다. 그러나 각 호 를 공통 끝점을 갖는 두 개의 호로 나눔으로써 그래프로 쓸 수 있다.
보조정리 64.1
가 의 부분공간인 세타 공간이라 하고, 가 그 합집합이 인 호들이라 하자. 그러면 는 를 세 개의 성분으로 분리하며, 그 경계는 각각 이다. 를 경계로 갖는 성분은 의 성분 중 하나와 같다.
증명
와 를 호 의 끝점이라 하자. 단순 닫힌 곡선 를 생각하자; 이것은 를 두 개의 성분 와 로 분리하며, 각각은 에서 열려 있고 경계로 를 갖는다.
공간 는 연결되어 있으므로, 이 성분들 중 하나, 예를 들어 에 포함되어야 한다. 그러면 두 공간 와 를 생각하자; 각각은 연결되어 있다. 어느 것도 를 분리하지 않는데, 왜냐하면 는 호이고, 의 여집합은 연결 집합 이기 때문이다. 이 두 집합의 교집합이 두 점 와 로만 이루어져 있으므로, 정리 63.5에 의해 그들의 합집합은 를 두 성분 와 로 분리한다. 따라서 는 세 개의 서로소인 연결 집합 의 합집합이다; 이들이 에서 열려 있으므로, 이들은 의 성분들이다. 성분 는 를 경계로 가진다. 대칭성에 의해 다른 두 성분은 각각 와 를 경계로 가짐을 알 수 있다.
정리 64.2
설비 그래프 는 평면에 매장될 수 없다.
증명
만약 가 평면에 매장될 수 있다면, 에 매장될 수 있다. 따라서 가 의 부분공간이라고 가정하자. 모순을 이끌어낼 것이다.
예제 2의 표기법을 사용하자. 여기서 는 의 꼭짓점이다. 에 포함된 다음 호들을 라 하자:
이 호들의 각 쌍은 그들의 끝점 와 에서만 교차하므로, 는 세타 공간이다. 공간 는 를 세 성분 로 분리하며, 그 경계는 각각 이다.
이제 의 꼭짓점 는 이 세 성분 중 하나에 속해야 하므로, 의 호 는 그 성분의 폐포 안에 놓여야 한다. 그 성분은 가 될 수 없는데, 왜냐하면 는 에 포함되고, 이 집합은 점 를 포함하지 않기 때문이다. 유사하게, 를 포함하는 성분은 나 가 될 수 없는데, 왜냐하면 는 을 포함하지 않고, 는 를 포함하지 않기 때문이다. 따라서, 우리는 모순에 도달했다.
보조정리 64.3
가 네 꼭짓점 를 갖는 완전 그래프인 의 부분공간이라 하자. 그러면 는 를 네 개의 성분으로 분리한다. 이 성분들의 경계는 집합 이며, 여기서 는 를 꼭짓점으로 갖지 않는 의 변들의 합집합이다.
증명
를 호 를 제외한 의 모든 호의 합집합이라 하자. 그러면 우리는
로 설정함으로써 를 세타 공간으로 쓸 수 있다.
호 는 그들의 끝점 에서만 교차하며, 그들의 합집합은 이다.
공간 는 를 세 성분 로 분리하며, 그 경계는 각각 이다. 공간 는 연결되어 있으므로, 그들 중 하나에 속해야 한다. 가 를 포함하지 않으므로 에 속할 수 없다. 그리고 가 를 포함하지 않으므로 에 속할 수 없다. 따라서 그것은 에 속해야 한다.
이제 는 연결되어 있는데, 왜냐하면 와 가 연결되어 있고 비어 있지 않은 교집합 를 갖기 때문이다. 게다가, 집합 는 를 분리하지 않는데, 왜냐하면 그 여집합이 이기 때문이다. 유사하게, 호 는 연결되어 있고 를 분리하지 않는다. 그리고 집합 와 는 점 와 에서만 교차한다. 정리 63.5에 의해 는 를 두 성분 과 로 분리한다. 그러면 는 네 개의 서로소인 연결 집합 의 합집합이다. 이 집합들이 열려 있으므로, 이들은 의 성분들이다.
이제 이 성분들 중 하나, 즉 는 그래프 를 경계로 가진다. 대칭성에 의해 다른 세 성분은 각각 를 경계로 가짐을 알 수 있다.
정리 64.4
개의 꼭짓점을 갖는 완전 그래프는 평면에 매장될 수 없다.
증명
가 다섯 꼭짓점 를 갖는 완전 그래프인 의 부분공간이라고 가정하자. 를 를 꼭짓점으로 갖지 않는 의 변들의 합집합이라 하자; 그러면 는 네 개의 꼭짓점을 갖는 완전 그래프이다. 공간 는 를 네 개의 성분으로 분리하며, 그 경계는 각각 그래프 이다. 여기서 는 를 꼭짓점으로 갖지 않는 의 변들로 이루어져 있다. 이제 점 는 이 네 성분 중 하나에 속해야 한다. 따라서 연결 공간
즉 를 꼭짓점으로 갖는 의 변들의 합집합은 이 성분의 폐포 안에 있어야 한다. 그러면 모든 꼭짓점 는 이 성분의 경계에 놓여야 한다. 그러나 이것은 불가능한데, 왜냐하면 그래프 중 어느 것도 네 개의 꼭짓점 를 모두 포함하지 않기 때문이다. 따라서 우리는 모순에 도달했다.
이러한 정리들로부터, 만약 그래프 가 설비 그래프이거나 5개의 꼭짓점을 갖는 완전 그래프인 부분 그래프를 포함한다면, 는 평면에 매장될 수 없다는 결론이 나온다. 쿠라토프스키(Kuratowski)에 의한 주목할 만한 정리에 따르면, 그 역 또한 참이다! 증명은 쉽지 않다.