18세기 프로이센의 도시 쾨니히스베르크에는 강 위에 다리가 7개 있었어요. 사람들은 "이 다리들을 한 번씩만 건너서 전부 다 지나갈 수 있을까?"를 궁금해했어요. 수학자 오일러가 이 질문에 답하면서, 그래프 이론이라는 완전히 새로운 수학 분야가 태어났어요.
땅덩어리를 점으로, 다리를 선으로 단순화하면 그림처럼 돼요. 점을 순서대로 클릭해서 모든 다리(선)를 한 번씩만 지나가 보세요 — 같은 다리를 두 번 건널 순 없어요. 직접 여러 번 시도해보면서 정말 가능한지 확인해봐요.
아무 점이나 클릭해서 시작하고, 다음 점들을 순서대로 클릭해서 다리 7개를 전부 건너보세요.
도형을 골라서 한붓그리기를 시도해보세요. 어떤 도형은 되고 어떤 도형은 안 되는 걸 직접 확인해보세요.
각 점에 연결된 선의 개수를 "차수"라고 해요. 차수가 홀수인 점(홀수점)이 몇 개인지 세어보면, 한붓그리기가 가능한지 미리 알 수 있어요.
홀수점이 0개면 → 아무 데서나 시작해도 한붓그리기가 가능하고, 출발점으로 다시 돌아올 수 있어요(오일러 회로).
홀수점이 2개면 → 그 두 점 중 한 곳에서 시작해서 다른 한 곳에서 끝나야만 가능해요(오일러 경로).
홀수점이 3개 이상이면 → 한붓그리기가 절대 불가능해요. 쾨니히스베르크는 홀수점이 4개나 있어서 불가능했던 거예요!
한붓그리기를 하는 동안, 어떤 점을 그냥 지나쳐만 갈 때는 반드시 그 점으로 들어오는 선 하나와 나가는 선 하나를 짝지어 써요. 그래서 출발점·도착점이 아닌 점들은 지나갈 때마다 선을 2개씩 소모하니까, 그 점에 연결된 선의 총 개수(차수)는 항상 짝수여야 해요.
홀수 개의 선이 연결된 점은 딱 두 종류만 있을 수 있어요 — 출발점(나가는 선이 하나 남아요)과 도착점(들어오는 선이 하나 남아요). 그래서 홀수점은 최대 2개까지만 있을 수 있고, 3개 이상이면 그 여러 홀수점을 전부 시작점이나 끝점으로 만들 수 없어서 한붓그리기가 불가능해져요.