직관 — 연결을 바꾸지 않고 선을 옮긴다
한 장의 종이에 부품과 배선을 그릴 때 선들이 엇갈렸다고 하자. 부품끼리의 연결은 그대로 두고 위치와 선의 굽음을 바꾸면 교차를 없앨 수도 있다. 처음 그림에 교차가 있다는 사실만으로는 불가능하다고 결론 내릴 수 없다.
이 글의 대상은 단순 무방향그래프다. 선을 곧게 그려야 한다는 제한은 없다. ‘다시 그릴 수 있는가’라는 그래프의 성질과 ‘지금 그린 그림에 교차가 있는가’를 구별한다. 회로 기판의 배선이나 노선도처럼 선이 겹치면 곤란한 설계가 이 질문에서 출발한다.
평면그래프는 교차 없는 배치가 존재하는 그래프다
평면그래프(planar graph)는 서로 다른 변이 공통 끝점 외에서는 만나지 않도록 평면에 그릴 수 있는 그래프다. 그런 방식으로 그린 그림에서 선들이 나누는 영역을 면이라고 하며, 바깥으로 끝없이 이어지는 영역도 한 면으로 센다.
연결된 평면그래프를 교차 없이 그렸을 때 다음 오일러 공식이 성립한다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 꼭짓점 수 | number of vertices | 그래프의 점 개수 | |
| 변 수 | number of edges | 그래프의 연결 개수 | |
| 면 수 | number of faces | 교차 없는 그림에서 바깥 면을 포함한 영역 수 | |
| 완전그래프 | complete graph | 서로 다른 모든 두 꼭짓점이 인접하는 그래프 | |
| 완전이분그래프 | complete bipartite graph | 크기 인 두 집단 사이의 모든 변만 가진 그래프 |
교과서의 꼭짓점 수 , 변 수 대신 여기서는 앞 글과 같은 을 쓴다. 꼭짓점이 하나이고 변이 없으면 평면 전체가 면 하나여서 다.
그림 1의 는 꼭짓점 4개와 변 6개를 갖는다. 사각형의 두 대각선처럼 그리면 교차하지만, 한 꼭짓점을 삼각형 안으로 옮기면 교차 없이 그릴 수 있다. 이때 작은 삼각형 면 3개와 바깥 면 1개여서 이고 다.
figures/planar_redraw.py그림 1 위의 영역을 그대로 세면 안쪽 삼각형 4개와 바깥 1개로 5개다. 이 값을 넣으면 이 되어 식 (1)과 맞지 않는다. 교차점은 꼭짓점이 아니므로, 면은 교차 없이 다시 그린 그림에서만 센다.
평면그래프를 그릴 때 변을 곡선으로 그려도 되나요?
가능하다. 중요한 것은 연결 관계와 교차 여부다. 곡선이 꼭짓점이 아닌 곳에서 다른 변이나 자기 자신을 만나지 않도록 그리면 된다. 그림 4 아래의 변 도 곡선으로 그려 교차를 줄였다.
오일러 공식은 왜 유지될까?
교차 없는 연결 그래프에 단순회로가 있으면, 그 회로 위 변 하나를 지워도 두 끝점은 회로의 나머지 길로 이어진다. 연결성은 유지되고 이 변 양쪽의 서로 다른 두 면은 하나가 된다. 따라서 변 수와 면 수가 각각 1 줄어 는 변하지 않는다.
그림 2는 이 과정을 실제로 따라간다. 꼭짓점 5개, 변 7개, 면 4개에서 출발해 회로 위의 변 , , 를 차례로 지운다. 변과 면이 하나씩 함께 줄어 네 단계 모두 값이 2다.
figures/euler_reduction.py이 과정을 더 이상 회로가 없을 때까지 반복한다. 남은 연결 그래프는 수형도이며 면은 바깥 면 하나뿐이다. 이때 변은 개다. 그 이유도 짧게 확인할 수 있다.
꼭짓점이 둘 이상 남아 있을 때, 가장 긴 단순경로의 끝에는 변이 하나만 닿는다. 다른 점으로 더 뻗으면 경로가 더 길어지고, 이미 지난 점으로 연결되면 회로가 생기기 때문이다. 이 끝점과 변 하나를 차례로 지우면 마지막 한 점까지 점과 변이 함께 줄어, 처음 변 수는 점 수보다 1 작다.
그러므로 마지막에는 다. 지우기 전에도 값이 같았으므로 식 (1)이 성립한다. 실제로 그려 본 몇 사례만이 아니라, 임의의 연결된 평면그래프를 줄여 가는 일반 논증이다.
오일러 공식은 떨어진 그래프에도 그대로 쓰나요?
오일러 공식의 값 2는 연결된 평면그래프에서만 나온다. 떨어진 삼각형 두 개는 꼭짓점 6개, 변 6개, 면 3개여서 이다. 두 삼각형 바깥 영역이 함께 이어진 한 면이기 때문이다. 덩어리가 개이면 값은 이고, 일 때 식 (1)이 된다.
수형도에는 안쪽 면이 없는데 면 수가 0인가요?
바깥 면 하나가 남으므로 1이다. 점 4개를 변 3개로 일렬로 이으면 가 된다. 닫힌 영역만 세면 오일러 공식과 맞지 않는다.
변이 너무 많으면 평면에 그릴 수 없을까?
그렇다. 꼭짓점이 3개 이상인 연결된 단순 평면그래프는 변이 개를 넘을 수 없다. 이 상한은 면의 경계를 세는 데서 나온다.
면 하나의 경계를 따라 한 바퀴 돌며 지나는 변을 센다. 한 변의 양쪽이 같은 면이면 그 변은 두 번 센다. 그러면 모든 변이 정확히 두 번 세어져, 모든 면의 횟수를 더하면 이다. 그림 3에서 두 삼각형 면은 3씩, 바깥 면은 매달린 변 를 왕복해 6이므로 합은 이다.
figures/face_boundary_count.py단순 그래프에는 자기 연결과 중복 변이 없어서 회로의 변은 3개 이상이다. 그래서 경계에 회로가 있는 면은 적어도 3번 센다. 회로가 없는 수형도라도 이면 유일한 면이 변 2개 이상을 왕복해 4번 이상 센다. 모든 면이 3번 이상이므로 다음이 성립한다.
식 (1)에서 이므로 이를 식 (2)에 대입한다.
괄호를 풀면 이고, 을 왼쪽으로 모으면 다음 상한을 얻는다.
모든 면이 삼각형이면 식 (2)가 등호이므로 식 (4)도 등호가 된다. 그림 1 아래의 가 그 예로, 이다.
K5와 K3,3은 왜 평면그래프가 아닐까?
는 , 이다. 식 (4)가 요구하는 를 어기므로 평면그래프가 아니다. 그림을 아무리 바꿔도 교차를 모두 없앨 수 없고, 그림 4 위처럼 한 곳까지만 줄일 수 있다.
꼭짓점을 두 집단으로 나누고 서로 다른 집단끼리만 인접하게 할 수 있으면 이분그래프다. 회로를 따라 집단이 번갈아 바뀌므로 단순회로의 길이는 짝수이며 적어도 4다. 그래서 꼭짓점이 3개 이상인 연결된 단순 이분 평면그래프에서는 면 하나의 경계 횟수가 4 이상이어서 이고, 식 (3)과 같은 대입으로 더 강한 조건을 얻는다.
은 두 집단에 각각 3개씩, 꼭짓점 6개와 변 개가 있다. 식 (4)의 상한 12는 넘지 않지만 식 (5)의 상한 8을 넘으므로 평면그래프가 아니다. 세 집을 수도·전기·가스 세 시설과 모두 잇되 관이 엇갈리지 않게 하라는 ‘세 집 문제’가 불가능한 이유다.
figures/k5_k33_crossings.py그림 4는 두 그래프의 교차를 한 곳까지 줄였고, 식 (4)·(5)는 0곳이 불가능함을 보인다. 그래서 둘 다 교차를 가장 적게 만든 그림의 교차는 정확히 한 곳이다.
그림 4 위에서 엇갈린 두 변 , 중 하나를 지우면 교차가 사라진다. 그래서 에서 변 하나를 뺀 그래프는 평면그래프이고, 으로 식 (4)의 등호를 이룬다. 이 결론은 상한을 만족해서가 아니라 교차 없는 그림을 실제로 찾았기 때문에 얻는다.
평면그래프는 교차 없이 다시 그릴 수 있는 그래프이고, 연결된 경우 바깥 면까지 세어 꼭짓점 수−변 수+면 수=2다. 여기서 나온 변 수의 상한은 필요조건일 뿐 충분조건이 아니다.
평면그래프인지 확실히 판정하는 조건이 있나요?
쿠라토프스키 정리가 평면그래프의 필요충분조건을 준다. 그래프가 평면그래프가 아닐 필요충분조건은 나 의 변 위에 점을 찍어 늘린 모양을 부분그래프로 갖는 것이다. 이 단원에서는 주로 식 (4)·(5)로 불가능을 보이고, 가능은 교차 없는 그림으로 보인다.
다면체의 꼭짓점·모서리·면도 오일러 공식을 따를까?
따른다. 볼록 다면체의 꼭짓점과 모서리는 교차 없는 연결 평면그래프로 옮길 수 있고, 다면체의 면은 그래프의 면이 된다. 정육면체를 한 면 쪽에서 들여다보듯 펼치면 그림 5 아래가 된다.
figures/cube_planar.py앞면 는 바깥 면 6이 되고, 뒷면 는 가운데 면 1이 된다. 꼭짓점 8개, 모서리 12개, 면 6개여서 다. 중학교 다면체에서 세던 꼭짓점·모서리·면의 관계가 식 (1)과 같은 이야기이고, 정사면체를 같은 방법으로 펼치면 그림 1 아래의 가 된다.
정육면체의 그래프는 이분그래프이고 면이 모두 사각형이다. 그래서 변 12개가 식 (5)의 상한 와 정확히 같다.
평면그래프의 흔한 오해
- 한 그림에서 선이 교차하면 비평면그래프다. — 그림 1의 처럼 다른 배치에서 교차를 없앨 수 있다.
- 변 수가 상한 이하면 평면그래프다. — 식 (4)는 필요조건이며, 변 9개인 은 상한 12를 만족하는 비평면 반례다.
직접 해보기
- 연결된 평면그래프의 꼭짓점이 7개, 변이 10개다. 교차 없는 그림의 면 수를 구하시오.
- 의 변 수를 구하고 평면그래프인지 판정하시오.
- 꼭짓점 8개인 연결된 단순 이분그래프에 변 13개가 있다. 평면그래프일 수 있는가?
- 에 새 꼭짓점 하나와 그 점을 원래 점 하나에 잇는 변 하나를 추가했다. 두 상한을 만족하는지, 평면그래프인지 판단하시오.
- 꼭짓점 6개인 연결된 단순 평면그래프를 교차 없이 그렸더니 모든 면이 삼각형이었다. 변 수와 면 수를 구하시오.
답과 풀이
- 이므로 다. 바깥 면을 포함한 값이다.
- 변은 개다. 식 (4)의 상한은 이므로 비평면이다.
- 식 (5)의 상한은 다. 변 13개는 이를 넘으므로 불가능하다.
- 이므로 와 을 모두 만족한다. 그래도 비평면이다. 교차 없이 그릴 수 있다면 새 점과 변을 지워 도 교차 없이 그릴 수 있게 되어 앞의 결론과 모순이다. 상한은 충분조건이 아니다.
- 모든 면이 삼각형이면 식 (2)가 등호여서 이다. 식 (1)의 을 넣으면 이므로 , 이다. 식 (4)의 등호 와 같고, 정팔면체가 이런 예다.
더 읽기
- 교육부 2022 개정 교육과정 고시 — 별책20 [12이수04-04]의 평면그래프와 성질.
- Levin, Planar Graphs — 바깥 면을 포함한 오일러 공식, 세 집 문제(), 다면체 절을 대조했다. 본문은 연결성과 조건을 붙여 사용한다.
- Buckingham, Graph Theory — 4장 「Planarity」 첫머리의 쿠라토프스키 정리, 4.1의 교차수(와 모두 1), 4.2의 변 양쪽을 세는 면의 차수, 4.3 「Euler’s formula」를 대조했다.
영상 노트
- 00:00 K₄를 두 모양으로 그려 교차 유무와 영역 수 비교하기
- 00:45 바깥 면을 넣어 식 (1) 계산하기
- 01:20 그림 2처럼 회로 위 변을 지워도 오일러 공식의 값이 보존되는 이유
- 02:10 그림 3의 면 경계 세기로 식 (2)에서 식 (4) 유도하기
- 03:00 식 (4)와 식 (5)로 K₅와 K₃,₃을 구별하고 세 집 문제 풀기
- 03:50 정육면체를 펼쳐 8−12+6=2 확인하기
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 교차 그림의 영역 수 반례, 변 지우기 과정과 면 경계 세기 도식, 상한 유도를 단계별로 분리, K5·K3,3 그림과 세 집 문제, 다면체 연결, 떨어진 그래프 일반식·쿠라토프스키 질문, 해보기 5번 추가 (에이전트 수정, 그림 1→5)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림