Definition D1
The degree deg(v) of a vertex v denotes the number of edges having v as an endpoint.
Proof.
Each edge has two distinct endpoints, so an edge contributes 1 to the degree of a vertex.convention, A1
∎
Definition D2
A walk W is v₀ e₁ v₁ e₂ ⋯ eₘ vₘ, where the two endpoints of each eᵢ are vᵢ₋₁ and vᵢ.
Proof.
(1)Call v₀ the starting point and vₘ the ending point.convention
(2)The two endpoints of each edge are distinct, so vᵢ₋₁ ≠ vᵢ.(1), A1
∎
Definition D3
A walk using every edge of E exactly once is called an Eulerian trail.
Proof.
No edge is omitted and no edge is used twice.convention, A2
∎
Lemma L1
Σ deg(v) = 2 |E|
Proof.
(1)Collect all pairs of the form (vertex v, edge e having v as an endpoint).D1
(2)Counting from the vertex side, each v contributes deg(v) pairs, so the number of pairs is Σ deg(v).(1), D1, A3
(3)Counting from the edge side, each edge has two distinct endpoints, so each edge contributes 2 pairs.(1), A1
(4)The same set was counted in two ways, so Σ deg(v) = 2|E|(2), (3), A3
∎
Lemma L2
The number of vertices of odd degree is even.
Proof.
(1)Split V into vertices of even degree and vertices of odd degree.A8
(2)Σ deg(v) = (sum of even degrees) + (sum of odd degrees)(1), A3
(3)The sum of the even degrees is even.(1), A4
(4)Σ deg(v) = 2|E|, and 2|E| is even.L1, A7
(5)Adding an even number preserves parity, so the sum of the odd degrees is also even.(2), (3), (4), A5
(6)A sum of k odd numbers is even, so k is even.(5), A6
∎
Lemma L3
Suppose an Eulerian trail W exists. For a vertex v, let t be the number of times v appears in an interior position vᵢ (0 < i < m) of W, and let s be the number of times v appears in the end positions v₀ · vₘ. Then deg(v) = 2t + s.
Proof.
(1)W uses every edge of E exactly once, so each edge having v as an endpoint appears exactly once in W.D3, A2, D1
(2)At a position vᵢ, edges having v as an endpoint are used. If 0 < i < m there are two, eᵢ and eᵢ₊₁; if i = 0 there is one, e₁; if i = m there is one, eₘ.D2
(3)The two endpoints of each edge are distinct, so vᵢ₋₁ ≠ vᵢ, and two positions where v appears are never adjacent. Therefore edges used at distinct positions are distinct.(2), D2, A1
(4)Each edge e having v as an endpoint appears in W; writing e = eᵢ, one of vᵢ₋₁ and vᵢ is v, so e is used at that position. No edge is missed.(1), (2), D2
(5)The t interior positions use 2 edges each and the s end positions use 1 edge each, so deg(v) = 2t + s(2), (3), (4), D1, N
∎
Theorem T1
If an Eulerian trail W exists, every vertex other than the starting and ending points has even degree. If the starting and ending points differ, those two vertices have odd degree; if they coincide, every vertex has even degree.
Proof.
(1)If v ∉ {v₀, vₘ} then s = 0, so deg(v) = 2t, which is even.L3, A7
(2)If v₀ ≠ vₘ then s = 1 at v₀, so deg(v₀) = 2t + 1, which is odd.L3, A7
(3)For the same reason deg(vₘ) is also odd.L3, A7
(4)If v₀ = vₘ then s = 2 at that vertex, so deg(v₀) = 2t + 2 = 2(t+1), which is even.L3, A7, N
(5)Every other vertex is even by (1).(1)
∎
Corollary C
In a graph admitting an Eulerian trail, the number of vertices of odd degree is 0 or 2.
Proof.
(1)If v₀ = vₘ, every vertex has even degree, so the number of odd vertices is 0.T1
(2)If v₀ ≠ vₘ, only those two vertices are odd, so the number of odd vertices is 2.T1
(3)These two cases are exhaustive.(1), (2)
(4)The number of odd vertices is even in every graph, so 1 or 3 never occurs in the first place.L2
(5)This proof started from the assumption that an Eulerian trail exists. What is obtained is therefore a necessary condition; conversely, that the number of odd vertices is 0 or 2 does not by itself yield the existence of an Eulerian trail.(3), D3
∎