https://arca.live/b/math/22485561?p=1

G=(V, E)라는 그래프를 생각해 보죠.   (V는 vertex들의 집합, E는 edge들의 집합.  여기로 따지면 E는 포장 도로들의 집합, V는 도시들의 집합이죠.) 

이제 G의 vertex 개수를 n개라고 하죠. 

그리고 모든 vertex에 대해, 각 vertex v에 대해, v에 연결된 edge의 개수가 k_v개라고 정의하죠. 

그러면, 다음의 식이 성립합니다. 

1/2∑k_v (where v∈V)   = |E| = edge의 개수.

이는 수학적 귀납법으로 증명할 수도 있고, 간결한 해설을 좋아하신다면,

각 edge에는 2개의 vertex만을 연결하고 있으므로, 

vertex의 연결된 edge의 개수를 다 더하면, edge들이 2번씩 세어진 것이므로 edge 총 개수의 2베가 됩니다. 

그러면, ∑k_v (where v∈V) = 2|E| 로서, 언제나 짝수가 된다는 것을 알 수 있죠.

근데, 홀수 개의 홀수들을 더하면 홀수이므로,  k_v들이 전부 홀수이면, |V|는 짝수여야 합니다.