기초수학평면그래프#357

평면그래프

Planar Graphs

평면그래프는 꼭짓점 이외에서 변이 교차하지 않게 평면에 그릴 수 있는 그래프다. 연결된 경우 꼭짓점 수에서 변 수를 빼고 바깥 면까지 포함한 면 수를 더하면 2가 되며, 이 관계로 변 수의 상한을 얻어 K5와 K3,3이 평면그래프가 아님을 보인다.

읽는 시간
약 8분
선수 개념
꼭짓점의 차수

직관 — 연결을 바꾸지 않고 선을 옮긴다

직관

한 장의 종이에 부품과 배선을 그릴 때 선들이 엇갈렸다고 하자. 부품끼리의 연결은 그대로 두고 위치와 선의 굽음을 바꾸면 교차를 없앨 수도 있다. 처음 그림에 교차가 있다는 사실만으로는 불가능하다고 결론 내릴 수 없다.

이 글의 대상은 단순 무방향그래프다. 선을 곧게 그려야 한다는 제한은 없다. ‘다시 그릴 수 있는가’라는 그래프의 성질과 ‘지금 그린 그림에 교차가 있는가’를 구별한다. 회로 기판의 배선이나 노선도처럼 선이 겹치면 곤란한 설계가 이 질문에서 출발한다.

평면그래프는 교차 없는 배치가 존재하는 그래프다

평면그래프(planar graph)는 서로 다른 변이 공통 끝점 외에서는 만나지 않도록 평면에 그릴 수 있는 그래프다. 그런 방식으로 그린 그림에서 선들이 나누는 영역을 면이라고 하며, 바깥으로 끝없이 이어지는 영역도 한 면으로 센다.

연결된 평면그래프를 교차 없이 그렸을 때 다음 오일러 공식이 성립한다.

n−m+f=2.(1)n-m+f=2. \tag{1}
정의
기호이름원어뜻
nn꼭짓점 수number of vertices그래프의 점 개수
mm변 수number of edges그래프의 연결 개수
ff면 수number of faces교차 없는 그림에서 바깥 면을 포함한 영역 수
KnK_n완전그래프complete graph서로 다른 모든 두 꼭짓점이 인접하는 그래프
Kr,sK_{r,s}완전이분그래프complete bipartite graph크기 r,sr,s인 두 집단 사이의 모든 변만 가진 그래프

교과서의 꼭짓점 수 vv, 변 수 ee 대신 여기서는 앞 글과 같은 n,mn,m을 쓴다. 꼭짓점이 하나이고 변이 없으면 평면 전체가 면 하나여서 1−0+1=21-0+1=2다.

그림 1의 K4K_4는 꼭짓점 4개와 변 6개를 갖는다. 사각형의 두 대각선처럼 그리면 교차하지만, 한 꼭짓점을 삼각형 안으로 옮기면 교차 없이 그릴 수 있다. 이때 작은 삼각형 면 3개와 바깥 면 1개여서 f=4f=4이고 4−6+4=24-6+4=2다.

위는 K₄의 교차가 있는 그림, 아래는 같은 여섯 변을 교차 없이 그린 그림이다. 아래의 1·2·3은 내부 면, 4는 바깥 면을 가리킨다. 위 교차점에는 꼭짓점이 없다.
그림 1 위는 K₄의 교차가 있는 그림, 아래는 같은 여섯 변을 교차 없이 그린 그림이다. 아래의 1·2·3은 내부 면, 4는 바깥 면을 가리킨다. 위 교차점에는 꼭짓점이 없다. figures/planar_redraw.py

그림 1 위의 영역을 그대로 세면 안쪽 삼각형 4개와 바깥 1개로 5개다. 이 값을 넣으면 4−6+5=34-6+5=3이 되어 식 (1)과 맞지 않는다. 교차점은 꼭짓점이 아니므로, 면은 교차 없이 다시 그린 그림에서만 센다.

평면그래프를 그릴 때 변을 곡선으로 그려도 되나요?

가능하다. 중요한 것은 연결 관계와 교차 여부다. 곡선이 꼭짓점이 아닌 곳에서 다른 변이나 자기 자신을 만나지 않도록 그리면 된다. 그림 4 아래의 변 CPCP도 곡선으로 그려 교차를 줄였다.

오일러 공식은 왜 유지될까?

교차 없는 연결 그래프에 단순회로가 있으면, 그 회로 위 변 하나를 지워도 두 끝점은 회로의 나머지 길로 이어진다. 연결성은 유지되고 이 변 양쪽의 서로 다른 두 면은 하나가 된다. 따라서 변 수와 면 수가 각각 1 줄어 n−m+fn-m+f는 변하지 않는다.

그림 2는 이 과정을 실제로 따라간다. 꼭짓점 5개, 변 7개, 면 4개에서 출발해 회로 위의 변 ACAC, CDCD, ABAB를 차례로 지운다. 변과 면이 하나씩 함께 줄어 네 단계 모두 값이 2다.

꼭짓점 5개, 변 7개인 연결 평면그래프에서 회로 위의 변(주황 점선)을 하나씩 지우는 과정이다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 변과 면이 하나씩 함께 줄고, 마지막 수형도에는 바깥 면 하나만 남는다.
그림 2 꼭짓점 5개, 변 7개인 연결 평면그래프에서 회로 위의 변(주황 점선)을 하나씩 지우는 과정이다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 변과 면이 하나씩 함께 줄고, 마지막 수형도에는 바깥 면 하나만 남는다. figures/euler_reduction.py

이 과정을 더 이상 회로가 없을 때까지 반복한다. 남은 연결 그래프는 수형도이며 면은 바깥 면 하나뿐이다. 이때 변은 n−1n-1개다. 그 이유도 짧게 확인할 수 있다.

꼭짓점이 둘 이상 남아 있을 때, 가장 긴 단순경로의 끝에는 변이 하나만 닿는다. 다른 점으로 더 뻗으면 경로가 더 길어지고, 이미 지난 점으로 연결되면 회로가 생기기 때문이다. 이 끝점과 변 하나를 차례로 지우면 마지막 한 점까지 점과 변이 함께 줄어, 처음 변 수는 점 수보다 1 작다.

그러므로 마지막에는 n−(n−1)+1=2n-(n-1)+1=2다. 지우기 전에도 값이 같았으므로 식 (1)이 성립한다. 실제로 그려 본 몇 사례만이 아니라, 임의의 연결된 평면그래프를 줄여 가는 일반 논증이다.

오일러 공식은 떨어진 그래프에도 그대로 쓰나요?

오일러 공식의 값 2는 연결된 평면그래프에서만 나온다. 떨어진 삼각형 두 개는 꼭짓점 6개, 변 6개, 면 3개여서 6−6+3=36-6+3=3이다. 두 삼각형 바깥 영역이 함께 이어진 한 면이기 때문이다. 덩어리가 kk개이면 값은 1+k1+k이고, k=1k=1일 때 식 (1)이 된다.

수형도에는 안쪽 면이 없는데 면 수가 0인가요?

바깥 면 하나가 남으므로 1이다. 점 4개를 변 3개로 일렬로 이으면 4−3+1=24-3+1=2가 된다. 닫힌 영역만 세면 오일러 공식과 맞지 않는다.

변이 너무 많으면 평면에 그릴 수 없을까?

그렇다. 꼭짓점이 3개 이상인 연결된 단순 평면그래프는 변이 3n−63n-6개를 넘을 수 없다. 이 상한은 면의 경계를 세는 데서 나온다.

면 하나의 경계를 따라 한 바퀴 돌며 지나는 변을 센다. 한 변의 양쪽이 같은 면이면 그 변은 두 번 센다. 그러면 모든 변이 정확히 두 번 세어져, 모든 면의 횟수를 더하면 2m2m이다. 그림 3에서 두 삼각형 면은 3씩, 바깥 면은 매달린 변 CECE를 왕복해 6이므로 합은 12=2×612=2\times6이다.

꼭짓점 5개, 변 6개인 평면그래프에서 면마다 경계를 따라 센 변의 등장 횟수다. 바깥 면은 점선을 따라 A, B, C, E, C, D, A로 돌며 매달린 변 CE를 두 번 센다. 횟수의 합 12는 변 수의 두 배다.
그림 3 꼭짓점 5개, 변 6개인 평면그래프에서 면마다 경계를 따라 센 변의 등장 횟수다. 바깥 면은 점선을 따라 A, B, C, E, C, D, A로 돌며 매달린 변 CE를 두 번 센다. 횟수의 합 12는 변 수의 두 배다. figures/face_boundary_count.py

단순 그래프에는 자기 연결과 중복 변이 없어서 회로의 변은 3개 이상이다. 그래서 경계에 회로가 있는 면은 적어도 3번 센다. 회로가 없는 수형도라도 n≥3n\ge3이면 유일한 면이 변 2개 이상을 왕복해 4번 이상 센다. 모든 면이 3번 이상이므로 다음이 성립한다.

3f≤2m.(2)3f\le2m. \tag{2}

식 (1)에서 f=2−n+mf=2-n+m이므로 이를 식 (2)에 대입한다.

3(2−n+m)≤2m.(3)3(2-n+m)\le2m. \tag{3}

괄호를 풀면 6−3n+3m≤2m6-3n+3m\le2m이고, mm을 왼쪽으로 모으면 다음 상한을 얻는다.

m≤3n−6(n≥3).(4)m\le3n-6\qquad(n\ge3). \tag{4}

모든 면이 삼각형이면 식 (2)가 등호이므로 식 (4)도 등호가 된다. 그림 1 아래의 K4K_4가 그 예로, 6=3×4−66=3\times4-6이다.

K5와 K3,3은 왜 평면그래프가 아닐까?

K5K_5는 n=5n=5, m=5×4÷2=10m=5\times4\div2=10이다. 식 (4)가 요구하는 m≤9m\le9를 어기므로 평면그래프가 아니다. 그림을 아무리 바꿔도 교차를 모두 없앨 수 없고, 그림 4 위처럼 한 곳까지만 줄일 수 있다.

꼭짓점을 두 집단으로 나누고 서로 다른 집단끼리만 인접하게 할 수 있으면 이분그래프다. 회로를 따라 집단이 번갈아 바뀌므로 단순회로의 길이는 짝수이며 적어도 4다. 그래서 꼭짓점이 3개 이상인 연결된 단순 이분 평면그래프에서는 면 하나의 경계 횟수가 4 이상이어서 4f≤2m4f\le2m이고, 식 (3)과 같은 대입으로 더 강한 조건을 얻는다.

m≤2n−4(n≥3).(5)m\le2n-4\qquad(n\ge3). \tag{5}

K3,3K_{3,3}은 두 집단에 각각 3개씩, 꼭짓점 6개와 변 3×3=93\times3=9개가 있다. 식 (4)의 상한 12는 넘지 않지만 식 (5)의 상한 8을 넘으므로 평면그래프가 아니다. 세 집을 수도·전기·가스 세 시설과 모두 잇되 관이 엇갈리지 않게 하라는 ‘세 집 문제’가 불가능한 이유다.

위는 K₅, 아래는 두 집단 A, B, C와 P, Q, R을 모두 이은 K₃,₃이다. 둘 다 교차를 주황 동그라미 한 곳까지 줄였지만 식 (4)와 식 (5)에 따라 0곳으로는 줄일 수 없다. 아래의 CP는 바깥으로 돌려 그린 곡선이다.
그림 4 위는 K₅, 아래는 두 집단 A, B, C와 P, Q, R을 모두 이은 K₃,₃이다. 둘 다 교차를 주황 동그라미 한 곳까지 줄였지만 식 (4)와 식 (5)에 따라 0곳으로는 줄일 수 없다. 아래의 CP는 바깥으로 돌려 그린 곡선이다. figures/k5_k33_crossings.py

그림 4는 두 그래프의 교차를 한 곳까지 줄였고, 식 (4)·(5)는 0곳이 불가능함을 보인다. 그래서 둘 다 교차를 가장 적게 만든 그림의 교차는 정확히 한 곳이다.

그림 4 위에서 엇갈린 두 변 BEBE, CDCD 중 하나를 지우면 교차가 사라진다. 그래서 K5K_5에서 변 하나를 뺀 그래프는 평면그래프이고, m=9=3×5−6m=9=3\times5-6으로 식 (4)의 등호를 이룬다. 이 결론은 상한을 만족해서가 아니라 교차 없는 그림을 실제로 찾았기 때문에 얻는다.

핵심

평면그래프는 교차 없이 다시 그릴 수 있는 그래프이고, 연결된 경우 바깥 면까지 세어 꼭짓점 수−변 수+면 수=2다. 여기서 나온 변 수의 상한은 필요조건일 뿐 충분조건이 아니다.

평면그래프인지 확실히 판정하는 조건이 있나요?

쿠라토프스키 정리가 평면그래프의 필요충분조건을 준다. 그래프가 평면그래프가 아닐 필요충분조건은 K5K_5나 K3,3K_{3,3}의 변 위에 점을 찍어 늘린 모양을 부분그래프로 갖는 것이다. 이 단원에서는 주로 식 (4)·(5)로 불가능을 보이고, 가능은 교차 없는 그림으로 보인다.

다면체의 꼭짓점·모서리·면도 오일러 공식을 따를까?

따른다. 볼록 다면체의 꼭짓점과 모서리는 교차 없는 연결 평면그래프로 옮길 수 있고, 다면체의 면은 그래프의 면이 된다. 정육면체를 한 면 쪽에서 들여다보듯 펼치면 그림 5 아래가 된다.

위는 정육면체이고 파선은 가려진 모서리다. 아래는 앞면 ABCD를 크게 늘려 바깥 면으로 두고 나머지를 안으로 밀어 넣은 평면그래프다. 1~6은 면의 번호이며 6이 바깥 면이다.
그림 5 위는 정육면체이고 파선은 가려진 모서리다. 아래는 앞면 ABCD를 크게 늘려 바깥 면으로 두고 나머지를 안으로 밀어 넣은 평면그래프다. 1~6은 면의 번호이며 6이 바깥 면이다. figures/cube_planar.py

앞면 ABCDABCD는 바깥 면 6이 되고, 뒷면 EFGHEFGH는 가운데 면 1이 된다. 꼭짓점 8개, 모서리 12개, 면 6개여서 8−12+6=28-12+6=2다. 중학교 다면체에서 세던 꼭짓점·모서리·면의 관계가 식 (1)과 같은 이야기이고, 정사면체를 같은 방법으로 펼치면 그림 1 아래의 K4K_4가 된다.

정육면체의 그래프는 이분그래프이고 면이 모두 사각형이다. 그래서 변 12개가 식 (5)의 상한 2×8−4=122\times8-4=12와 정확히 같다.

평면그래프의 흔한 오해

  • 한 그림에서 선이 교차하면 비평면그래프다. — 그림 1의 K4K_4처럼 다른 배치에서 교차를 없앨 수 있다.
  • 변 수가 상한 이하면 평면그래프다. — 식 (4)는 필요조건이며, 변 9개인 K3,3K_{3,3}은 상한 12를 만족하는 비평면 반례다.

직접 해보기

  1. 연결된 평면그래프의 꼭짓점이 7개, 변이 10개다. 교차 없는 그림의 면 수를 구하시오.
  2. K6K_6의 변 수를 구하고 평면그래프인지 판정하시오.
  3. 꼭짓점 8개인 연결된 단순 이분그래프에 변 13개가 있다. 평면그래프일 수 있는가?
  4. K3,3K_{3,3}에 새 꼭짓점 하나와 그 점을 원래 점 하나에 잇는 변 하나를 추가했다. 두 상한을 만족하는지, 평면그래프인지 판단하시오.
  5. 꼭짓점 6개인 연결된 단순 평면그래프를 교차 없이 그렸더니 모든 면이 삼각형이었다. 변 수와 면 수를 구하시오.
답과 풀이
  1. 7−10+f=27-10+f=2이므로 f=5f=5다. 바깥 면을 포함한 값이다.
  2. 변은 6×5÷2=156\times5\div2=15개다. 식 (4)의 상한은 3×6−6=123\times6-6=12이므로 비평면이다.
  3. 식 (5)의 상한은 2×8−4=122\times8-4=12다. 변 13개는 이를 넘으므로 불가능하다.
  4. n=7,m=10n=7,m=10이므로 10≤1510\le15와 10≤1010\le10을 모두 만족한다. 그래도 비평면이다. 교차 없이 그릴 수 있다면 새 점과 변을 지워 K3,3K_{3,3}도 교차 없이 그릴 수 있게 되어 앞의 결론과 모순이다. 상한은 충분조건이 아니다.
  5. 모든 면이 삼각형이면 식 (2)가 등호여서 3f=2m3f=2m이다. 식 (1)의 f=2−6+mf=2-6+m을 넣으면 3(m−4)=2m3(m-4)=2m이므로 m=12m=12, f=8f=8이다. 식 (4)의 등호 3×6−6=123\times6-6=12와 같고, 정팔면체가 이런 예다.

더 읽기

  • 교육부 2022 개정 교육과정 고시 — 별책20 [12이수04-04]의 평면그래프와 성질.
  • Levin, Planar Graphs — 바깥 면을 포함한 오일러 공식, 세 집 문제(K3,3K_{3,3}), 다면체 절을 대조했다. 본문은 연결성과 n≥3n\ge3 조건을 붙여 사용한다.
  • Buckingham, Graph Theory — 4장 「Planarity」 첫머리의 쿠라토프스키 정리, 4.1의 교차수(K5K_5와 K3,3K_{3,3} 모두 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 확인하기

지도에서의 위치

그래프의 뜻기초수학꼭짓점의 차수기초수학평면그래프지금 이 페이지
선수 개념
이 페이지
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 교차 그림의 영역 수 반례, 변 지우기 과정과 면 경계 세기 도식, 상한 유도를 단계별로 분리, K5·K3,3 그림과 세 집 문제, 다면체 연결, 떨어진 그래프 일반식·쿠라토프스키 질문, 해보기 5번 추가 (에이전트 수정, 그림 1→5)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림