Câu hỏi 13
Với số nguyên dương $k$, một chu trình độ dài $k$ trong một đồ thị là một dãy $v_1, e_1, v_2, e_2, \dots, v_k, e_k$, trong đó các $v_i$ là các đỉnh (không nhất thiết phân biệt), các $e_i$ là các cạnh (không nhất thiết phân biệt), và mỗi $e_i$ nối $v_i$ với $v_{i+1}$ (các chỉ số lấy theo modulo $k$); chu trình đi qua cạnh $e$ nếu $e = e_i$ với một chỉ số $i$ nào đó. Chứng minh rằng một đồ thị liên thông với tập đỉnh $V$ và tập cạnh $E$ có một chu trình độ dài không quá $|V| + |E| - 1$ đi qua mọi cạnh của đồ thị.