Euler paths and circuits

Result 1, only if. Proof. Let (v_0, e_1, v_1, \ldots, e_k, v_k) with v_k = v_0 be an Euler circuit and fix a vertex v. At each position v_i, 1 \le i \le k, two steps meet: e_i arrives and e_{i+1} leaves, where e_{k+1} means e_1. Each meeting at v uses two edge ends at v. Every edge is used once, so each edge end at v belongs to exactly one meeting. Hence \deg(v) is twice the number of meetings at v, an even number. \square

A lemma. In a multigraph where every degree is even, every vertex v of positive degree starts a closed trail. Proof. Walk from v along unused edges for as long as possible. On arriving at a vertex w \ne v, the walk has used an odd number of edge ends at w: two for each earlier pass and one for the arrival. As \deg(w) is even, an unused edge remains and the walk goes on. The edges are finite, so the walk stops, and only at v. It used at least one edge, so it is a closed trail. \square

Result 1, if. Proof. By Strong induction and well-ordering on the number of edges q \ge 1. Let G be connected with q edges and even degrees, and assume the result for connected multigraphs with fewer edges. The lemma gives a closed trail T. Delete the edges of T, keeping every vertex, to get H. By the first half, T uses an even number of edge ends at each vertex, so H has even degrees. If H has no edges, T is an Euler circuit. Otherwise let H_1, \ldots, H_r be the components of H with an edge. Each is connected with even degrees and fewer than q edges, so it has an Euler circuit C_j.

Each H_j meets T. Take x in H_j, a walk (x = w_0, \ldots, w_s) in G ending on T, and its first vertex w_t on T. For i \le t the edge from w_{i-1} to w_i has an end off T, so it is not an edge of T; it is in H, and w_t lies in H_j. Now go round T, and the first time it reaches a vertex of H_j, go round C_j from there (rotated to start there) before going on. Doing this for each j gives a closed walk that uses every edge of T and of each C_j once: every edge of G. \square

Result 2. Proof. Let u and v be the only odd vertices. Add a new edge f joining them. Every degree is now even and the multigraph is connected, so it has an Euler circuit, which may be started (u, f, v, \ldots, u). Dropping the first step leaves an Euler trail of G from v to u, open since u \ne v. Conversely, let an open Euler trail run from u to v \ne u. An added edge f from v to u closes it into an Euler circuit, so with f every degree is even by Result 1. Removing f lowers \deg(u) and \deg(v) by one: in G exactly u and v are odd. \square

Result 3. Proof. An added edge changes the degrees of its two ends by one each, so it changes the number of odd vertices by -2, 0 or 2; going from 2m to 0 takes at least m edges. The m pairing edges make every degree even and keep the graph connected, so Result 1 applies.

In any split of the edges into trails, the degree of a vertex is the sum of its degrees in the trails. A closed trail, or an open one passing through, adds an even amount; only the ends of an open trail add an odd amount. So every odd vertex of G ends some trail, and s trails have at most 2s ends: s \ge m. For m trails, take an Euler circuit C of G with the pairing edges. Each odd vertex meets exactly one new edge and each new edge has odd ends, so no two new edges are consecutive in C. Deleting the m new edges cuts C into m pieces with at least one edge each, and they are trails of G. \square

1. (a) 3 and 4 have degree 3, the others 4 or 2: an open Euler trail from 3 to 4, such as (3, 2, 1, 5, 4, 1, 3, 4). (b) Every vertex has degree 3: six odd vertices, neither. (c) Every vertex has degree 4: an Euler circuit, (p, q, r, p, q, r, p).
2. Yes. \deg(N) = 4, \deg(I) = 5, \deg(S) = 3, so the walk starts at I or S and ends at the other (Result 2), for example (I, N, I, N, S, I, S). No closed walk does it.
3. 12 edges, as the degrees add to 24. Exactly two odd vertices, so an open Euler trail and no Euler circuit; it starts at one vertex of degree 3 and ends at the other.
4. 1 and n have degree 2, 2, \ldots, n - 1 degree 3, and h degree n. n = 2: a triangle, circuit (1, 2, h, 1). n = 3: odd 2 and h, trail (2, 1, h, 3, 2, h). n = 4: odd 2 and 3, trail (2, 1, h, 2, 3, h, 4, 3). n \ge 5: the n - 2 \ge 3 vertices 2, \ldots, n - 1 are odd, so neither.
5. Connected with n \ge 2 vertices, so no vertex is isolated. By Result 1 every degree is even, so at least 2, and the handshake lemma gives 2\lvert E \rvert \ge 2n.
6. Strong induction and well-ordering on the number of edges. With none, use no cycles. Otherwise a vertex of positive degree starts a closed trail (the lemma), and every closed trail contains a cycle Z (Walks, paths, cycles and connected graphs, Exercise 16). Removing the edges of Z lowers each degree by 0 or 2, so degrees stay even; the rest splits into cycles by hypothesis, and Z joins them. \square
7. The complete graph K_4: connected, every degree 3, so four odd vertices and no Euler trail (Results 1 and 2).
8. u and v gain one each and become even, w has degree 2, and the result is connected, so Result 1 gives a circuit. It passes w once; start it there and reverse it if needed, to get (w, u, \ldots, v, w). Deleting w and its two edges leaves (u, \ldots, v), an Euler trail of G. The new graph stays simple, while a second edge uv makes a multigraph.
9. Unused: 34, 45, 53, 56, 67, 75. Splice (3, 4, 5, 3) at 3: (1, 2, 3, 4, 5, 3, 1). Splice (5, 6, 7, 5) at 5: (1, 2, 3, 4, 5, 6, 7, 5, 3, 1), all 9 edges.
10. Every degree is 4, and (0, 1, \ldots, 6, 0) reaches every vertex. The two closed trails use the \pm 1 edges and the \pm 2 edges. Splicing at 0: (0, 1, 2, 3, 4, 5, 6, 0, 2, 4, 6, 1, 3, 5, 0), all 14 edges.
11. 4. The board has 16 points and 24 segments. The 4 outer corners have degree 2, the 8 other boundary points degree 3, the 4 inner points degree 4. Eight odd vertices give \displaystyle \frac{8}{2} = 4 strokes by Result 3.
12. 3: there are six odd vertices and each added edge evens at most two. The six non-edges form the cycle (a, y, c, x, b, z, a), so exactly two triples work: ay, cx, bz or yc, xb, za. Each gives every vertex degree 4, connected.
13. 3. The odd intersections are 1 and 5. As in Example 7, the repeats contain a walk from 1 to 5, so at least d(1, 5) = 3 blocks (the ring takes 4). Repeating the avenue: (1, 2, 3, 4, 5, 10, 9, 1, 8, 7, 6, 5, 10, 9, 1), 14 blocks.
14. (a) Yes. a and c have \deg^+ = \deg^- = 2, b and d have 1 and 1, and the streets are connected, so Result 4 applies: (a, b, c, a, c, d, a). (b) No: \deg^+(a) = 3 but \deg^-(a) = 1.
15. With n vertices, G has 2n edges, an even number, and an Euler circuit (Result 1). Color its steps red and blue in turn; as 2n is even, the last and first steps also differ. At each meeting at a vertex the two steps are consecutive, so one is red and one blue. A vertex of degree 4 has two meetings: two red and two blue edges. \square
16. Each step leaves its start and enters its end. Each arrival at v is followed by a departure from v (the last arrival by the first step), which pairs arrivals with departures. Every edge is used once, so the arrivals number \deg^-(v) and the departures \deg^+(v). \square
17. The lemma says where the walk stops, not that it used every edge. It can return to the start with edges left elsewhere, as in Example 5, where the walk from a stopped after 4 of the 10 edges. The missing step is splicing.