이 개념은 정규 교육과정 밖의 내용으로, 도형의 길이나 각도는 다 지우고 점과 선의 연결 관계만 남긴 구조를 다루며, 쾨니히스베르크 다리 문제에서 출발했다.
그래프(graph)는 점(꼭짓점, vertex)들과 그 점들을 잇는 선(변, edge)들로만 이루어진 구조다. 도형의 모양·길이·각도는 신경 쓰지 않고, "어떤 점과 어떤 점이 연결되어 있는가"라는 관계만 남긴다.
한 꼭짓점에 연결된 변의 개수를 그 꼭짓점의 차수(次數, degree)라고 한다. 꼭짓점 $A$의 차수는 $\deg(A)$(디그리 에이라고 읽는다)로 나타내기도 한다.
그래프의 모든 변을 딱 한 번씩만 지나가는 경로를 오일러 경로(Euler path)라 하고, 출발점과 도착점이 같은 오일러 경로를 오일러 회로(Euler circuit)라고 한다. "한붓그리기가 가능한가"라는 질문이 바로 오일러 경로가 존재하는지를 묻는 것이다.
지도에서 땅을 점으로, 다리를 선으로 바꿔 그린다고 생각하면 된다. 땅의 크기나 다리의 길이는 다 지워지고, "몇 개의 다리가 어느 땅과 어느 땅을 잇는가"만 남는다. 그러면 "종이에서 연필을 떼지 않고 모든 선을 한 번씩만 그릴 수 있는가"라는, 눈으로 바로 확인하기 힘든 문제가 남는다.
한붓그리기를 여러 도형으로 시도해 보면 어떤 것은 되고 어떤 것은 안 된다. 왜 그런지 따져 보자.
1단계. 경로가 어떤 꼭짓점을 그냥 지나쳐 갈 때(시작점도 끝점도 아닐 때), 그 꼭짓점에서는 변 하나로 들어와서 다른 변 하나로 나간다. 즉 그 꼭짓점을 한 번 지나칠 때마다 변을 정확히 2개씩 소모한다.
2단계. 그러므로 시작점·끝점이 아닌 꼭짓점은 연결된 변의 개수(차수)가 항상 짝수여야 한다. 홀수라면 마지막에 변 하나가 남아서 그 점을 완전히 빠져나올 수 없다.
3단계. 시작점은 예외다. 처음 나갈 때 변 하나를 더 쓰기 때문에, 시작점의 차수는 (지나칠 때 쓰는 짝수 개) + (처음 나가는 1개)로 홀수가 될 수 있다. 끝점도 마찬가지로 (마지막에 들어오는 1개)가 더해져 홀수가 될 수 있다. 단, 시작점과 끝점이 같아서 회로를 이루면 그 점도 다시 짝수여야 한다.
4단계. 정리하면: 홀수 차수인 꼭짓점은 경로의 시작점과 끝점, 최대 2개뿐이어야 한다. 그러므로
5단계. 쾨니히스베르크 다리 문제에 적용해 보면, 4개의 땅에 각각 차수 5, 3, 3, 3인 다리가 연결되어 있었다(홀수 차수 땅이 4개). 4단계의 결론에 따라 오일러 경로조차 존재하지 않으므로, "모든 다리를 한 번씩만 건너서 돌아오는 것"은 애초에 불가능하다.
꼭짓점 $A,B,C,D$에 변 $AB, BC, CD, DA, AC$(대각선 하나 포함)가 있는 그래프를 생각하자.
차수를 세면 $\deg(A)=3$ (AB, DA, AC), $\deg(B)=2$ (AB, BC), $\deg(C)=3$ (BC, CD, AC), $\deg(D)=2$ (CD, DA)다. 홀수 차수인 점은 $A, C$ 두 개뿐이므로 오일러 경로가 존재하며, $A$에서 시작해 $C$에서 끝나야 한다.
실제 경로: $A \to B \to C \to D \to A \to C$ — $AB, BC, CD, DA, AC$ 다섯 변을 정확히 한 번씩 사용했다.
제설차나 쓰레기 수거차가 마을의 모든 도로(변)를 한 번씩만 지나면서 순찰하려는 경로 계획이 오일러 경로 문제 그 자체다. 도로 교차점을 꼭짓점, 도로를 변으로 바꾼 뒤 홀수 차수 교차점의 개수를 세어 보면, 기름을 낭비하며 같은 길을 두 번 지나지 않고 한 번에 순찰을 마칠 수 있는지 미리 알 수 있다.
1736년 레온하르트 오일러는 쾨니히스베르크(현재 러시아 칼리닌그라드)의 7개 다리를 한 번씩만 건너 원래 자리로 돌아올 수 있는지를 묻는 문제를 풀었다. 그는 땅의 모양이나 다리의 길이를 모두 무시하고 "어느 땅과 어느 땅이 다리로 연결되어 있는가"라는 관계만 남긴 그림으로 문제를 바꾸었는데, 이것이 최초의 그래프였다. 그는 각 땅에 연결된 다리 수(차수)가 홀수인 땅이 몇 개인지에 따라 답이 결정된다는 것을 밝혀, 이 문제가 불가능함을 증명했다. 이 연구가 오늘날 그래프 이론이라 불리는 수학 분야의 출발점이 되었다.