Walks, paths, cycles and connected graphs

Result 1. Proof. Among all walks from u to v whose edges are edges of the given walk, choose one of least length, (v_0, \ldots, v_k). Suppose v_i = v_j with i < j. Deleting v_{i+1}, \ldots, v_j leaves (v_0, \ldots, v_i, v_{j+1}, \ldots, v_k), still a walk from u to v (since v_i = v_j is adjacent to v_{j+1}), using only edges already used, and shorter by j - i \ge 1. That contradicts the choice, so the walk is a path. A shortest walk from u to v is itself such a choice, so it is a path. \square

Result 2. Proof. Reflexive: (u) is a walk. Symmetric: a walk read backward runs from v to u. Transitive: a walk from u to v followed by one from v to w, with v written once, runs from u to w. So V splits into Relations, equivalence classes and partitions. An edge uv is the walk (u, v), so its ends share a class. Every vertex of a walk from u is joined to u, so a walk between two vertices of a class lies, edges included, in that component: each component is connected. One class means every two vertices are joined. \square

Result 3. Use the walk (u), reversed walks, and a shortest walk from u to v followed by one from v to w (if either distance is \infty there is nothing to prove).

Result 4. Proof. Write \delta = \delta(G). Some vertex has a neighbor, so paths of length at least 1 exist. A path repeats no vertex, so there are finitely many paths; choose a longest, (v_0, v_1, \ldots, v_k), with k \ge 1. Every neighbor w of v_k lies on the path, or (v_0, \ldots, v_k, w) would be longer. So the at least \delta neighbors of v_k are among v_0, \ldots, v_{k-1}, and the earliest, v_i, has i \le k - \delta. Then (v_i, v_{i+1}, \ldots, v_k, v_i) is a cycle of length k - i + 1 \ge \delta + 1 \ge 3. \square Figure 2 shows a case with \deg(v_6) = 3.

Result 5. Proof. By Strong induction and well-ordering on the odd length k. Let W = (v_0, \ldots, v_k) be closed with k odd. A simple graph has no loops, so k \ge 3. If v_0, \ldots, v_{k-1} are all different, W is an odd cycle. Otherwise v_i = v_j for some 0 \le i < j \le k other than i = 0, j = k. Split W into the closed walks

of lengths j - i and k - (j - i). Both lie between 1 and k - 1 and they add to the odd number k, so one is odd. By the induction hypothesis it contains an odd cycle made of its edges, which are edges of W. \square

Result 6. Proof. Suppose G is disconnected. Let A be the vertex set of one component, with a vertices, 1 \le a \le n - 1, and B the other n - a. No edge joins A to B (Result 2), and the a(n - a) pairs with one end in each are exactly the pairs lost, so

Expanding (a - 1)(n - a - 1) \ge 0 gives a(n - a) \ge n - 1, so \lvert E \rvert \le \binom{n}{2} - (n - 1) = \binom{n-1}{2}. By contraposition, more edges force G to be connected. \square

1. (a) A cycle of length 4. (b) A trail of length 6: its edges 74, 43, 36, 61, 12, 23 are different, but 3 appears twice. (c) A walk of length 4, not a trail: 47 is used twice. (d) Not a walk: 64 is not an edge. (e) A path of length 4.
2. d(7, 7) = 0, d(7, 4) = 1, d(7, 3) = d(7, 5) = 2, d(7, 1) = d(7, 2) = d(7, 6) = 3, by layers from 7 as in Example 3.
3. Three: (1, 2, 3, 4, 5, 1) of length 5, (1, 2, 3, 6, 1) of length 4 and (1, 6, 3, 4, 5, 1) of length 5. No cycle uses 47, as \deg(7) = 1. A cycle through 6 uses 16, 36 and returns from 3 to 1 by 2 or by 4, 5; one avoiding 6 is the ring.
4. Vertex 2 returns in the fifth place; one cut leaves (2, 1, 5, 4, 3, 6), a path of length 5. Not shortest: 2, 6 are not adjacent and (2, 3, 6) has length 2, so d(2, 6) = 2. Cutting gives a path, not always a shortest one.
5. Length 9. Vertex 1 repeats in places 0 and 4; splitting gives (1, 2, 3, 6, 1) of length 4 and (1, 5, 4, 3, 6, 1), a cycle of length 5.
6. Vertex sets \{1, 4, 7\}, \{2, 5, 8, 9\} and \{3, 6, 10\}; d(2, 8) = 3, along (2, 9, 5, 8).
7. 28 = \binom{8}{2}, for example K_8 and one isolated vertex. More is impossible by Result 6.
8. 172. More than \binom{19}{2} = 171 forces connection; with 171, K_{19} and an isolated pavilion is disconnected.
9. 10, from K_5 and two isolated vertices. With component sizes a + b + c = 7 there are at most \binom{a}{2} + \binom{b}{2} + \binom{c}{2} edges; the sizes (5, 1, 1), (4, 2, 1), (3, 3, 1), (3, 2, 2) give 10, 7, 6, 5.
10. d(0, j) = \min(j, 9 - j), so d(0, 6) = 3, along (0, 8, 7, 6). The largest distance is 4, reached from 0 at 4 and 5.
11. K_4: degrees 3, and no cycle longer than 4 = \delta + 1, the length Result 4 promises.
12. The neighbors of 6 are 3 and 1, both on the path (v_0, \ldots, v_6). The earliest is 1 = v_3, giving the cycle (1, 2, 3, 6, 1) of length 4.
13. Choose a longest path (v_0, \ldots, v_k), so k \ge 1. A neighbor w \ne v_{k-1} of v_k would close a cycle if on the path and give a longer path if off it. So \deg(v_k) = 1, and likewise \deg(v_0) = 1. \square
14. Let u, v be the two, and K the component of u. Every edge at a vertex of K lies in K, so degrees in K are degrees in G. By the handshake lemma in K, K has an even number of odd vertices, so another besides u, which can only be v. By Result 1 they are joined by a path. \square
15. Let e = xy lie on the cycle (x, y, w_1, \ldots, w_m, x). Then (y, w_1, \ldots, w_m, x) joins y to x without e. In any walk of G, replace each use of e by this walk or its reverse. So vertices joined in G stay joined without e. \square
16. In a closed trail (v_0, \ldots, v_k), v_0 = v_k, so some vertex repeats. Choose v_i = v_j, i < j, with j - i least, so v_i, \ldots, v_{j-1} are different. Then j - i \ne 1 (no loops) and j - i \ne 2 ((v_i, v_{i+1}, v_i) reuses an edge), so j - i \ge 3 and (v_i, \ldots, v_j) is a cycle. \square
17. The walk (v_0, \ldots, v_i) gives d(u, v_i) \le i. A walk from u to v_i shorter than i, followed by (v_i, \ldots, v_k), would be a walk from u to v shorter than k = d(u, v). \square
18. Suppose not. With two or more components, a smallest has a vertex set A with \displaystyle \lvert A \rvert \le \frac{n}{2}. A vertex of A has all its neighbors in A, so its degree is at most \displaystyle \frac{n}{2} - 1 < \frac{n - 1}{2}, a contradiction. \square
19. On a triangle x, y, z, the closed walk (x, y, z, x, y, z, x) has length 6, but its edges form only the triangle, a cycle of length 3. (And (x, y, x, y, x) has length 4 and contains no cycle.)