정의 D1
꼭짓점 v 의 차수 deg(v) 는 v 를 끝점으로 하는 변의 개수를 뜻한다.
증명.
각 변은 서로 다른 두 끝점을 가지므로, 한 변이 한 꼭짓점의 차수에 보태는 것은 1 이다.약속, A1
∎
정의 D2
걷기 W 는 v₀ e₁ v₁ e₂ ⋯ eₘ vₘ 이며, 각 eᵢ 의 두 끝점은 vᵢ₋₁ 과 vᵢ 이다.
증명.
(1)v₀ 를 시작점, vₘ 을 끝점이라 한다.약속
(2)각 변의 두 끝점은 서로 다르므로 vᵢ₋₁ ≠ vᵢ 이다.(1), A1
∎
정의 D3
E 의 모든 변을 꼭 한 번씩 쓰는 걷기를 한붓그리기라 한다.
증명.
빠뜨린 변도, 두 번 쓴 변도 없다.약속, A2
∎
보조정리 L1
Σ deg(v) = 2 |E|
증명.
(1)(꼭짓점 v, v 를 끝점으로 하는 변 e) 꼴의 쌍을 모두 모은다.D1
(2)꼭짓점 쪽에서 세면 v 마다 deg(v) 개이므로 쌍의 개수는 Σ deg(v) 다.(1), D1, A3
(3)변 쪽에서 세면 각 변은 서로 다른 두 끝점을 가지므로 변마다 2 개다.(1), A1
(4)같은 것을 두 방식으로 세었으므로 Σ deg(v) = 2|E|(2), (3), A3
∎
보조정리 L2
차수가 홀수인 꼭짓점의 개수는 짝수다.
증명.
(1)V 를 차수가 짝수인 것과 홀수인 것으로 나눈다.A8
(2)Σ deg(v) = (짝수 차수의 합) + (홀수 차수의 합)(1), A3
(3)짝수 차수의 합은 짝수다.(1), A4
(4)Σ deg(v) = 2|E| 이고 2|E| 는 짝수다.L1, A7
(5)짝수를 더해도 홀짝은 그대로이므로 홀수 차수의 합도 짝수다.(2), (3), (4), A5
(6)홀수 k 개의 합이 짝수이므로 k 는 짝수다.(5), A6
∎
보조정리 L3
한붓그리기 W 가 있다고 하자. 꼭짓점 v 에 대하여 t 를 v 가 W 의 내부 자리 vᵢ (0 < i < m) 로 나타난 횟수, s 를 v 가 양 끝 자리 v₀ · vₘ 으로 나타난 횟수라 하면 deg(v) = 2t + s 이다.
증명.
(1)W 는 E 의 모든 변을 꼭 한 번씩 쓰므로, v 를 끝점으로 하는 변은 W 에 꼭 한 번씩 나타난다.D3, A2, D1
(2)자리 vᵢ 에서 v 를 끝점으로 하는 변이 쓰인다. 0 < i < m 이면 eᵢ 와 eᵢ₊₁ 둘이고, i = 0 이면 e₁ 하나, i = m 이면 eₘ 하나다.D2
(3)각 변의 두 끝점은 서로 다르므로 vᵢ₋₁ ≠ vᵢ 이고, v 가 나타나는 두 자리는 이웃하지 않는다. 그러므로 서로 다른 자리에서 쓰이는 변은 서로 다르다.(2), D2, A1
(4)v 를 끝점으로 하는 변 e 는 W 에 나타나고, e = eᵢ 라 하면 vᵢ₋₁ 과 vᵢ 중 하나가 v 이므로 그 자리에서 쓰인다. 빠지는 변은 없다.(1), (2), D2
(5)내부 자리 t 개가 2 개씩, 끝 자리 s 개가 1 개씩 쓰므로 deg(v) = 2t + s(2), (3), (4), D1, N
∎
정리 T1
한붓그리기 W 가 있으면, 시작점과 끝점이 아닌 모든 꼭짓점의 차수는 짝수다. 시작점과 끝점이 다르면 그 두 점의 차수는 홀수이고, 같으면 모든 꼭짓점의 차수가 짝수다.
증명.
(1)v ∉ {v₀, vₘ} 이면 s = 0 이므로 deg(v) = 2t 이고 짝수다.L3, A7
(2)v₀ ≠ vₘ 이면 v₀ 에서 s = 1 이므로 deg(v₀) = 2t + 1 이고 홀수다.L3, A7
(3)같은 이유로 deg(vₘ) 도 홀수다.L3, A7
(4)v₀ = vₘ 이면 그 점에서 s = 2 이므로 deg(v₀) = 2t + 2 = 2(t+1) 이고 짝수다.L3, A7, N
(5)그 밖의 꼭짓점은 (1) 에 의하여 짝수다.(1)
∎
따름정리 C
한붓그리기가 있는 그래프에서 차수가 홀수인 꼭짓점은 0 개이거나 2 개다.
증명.
(1)v₀ = vₘ 이면 모든 꼭짓점의 차수가 짝수이므로 홀수인 꼭짓점은 0 개다.T1
(2)v₀ ≠ vₘ 이면 그 두 점만 홀수이므로 홀수인 꼭짓점은 2 개다.T1
(3)두 경우가 전부다.(1), (2)
(4)홀수인 꼭짓점의 개수는 어떤 그래프에서도 짝수이므로, 1 개나 3 개는 애초에 나타나지 않는다.L2
(5)이 증명은 한붓그리기가 있다는 가정에서 출발했다. 그러므로 얻은 것은 필요조건이며, 거꾸로 홀수인 꼭짓점이 0 개나 2 개라는 것에서 한붓그리기의 존재는 따라 나오지 않는다.(3), D3
∎