Suppose that every vertex of a loopless graph G has degree at least 3.Prove that G has a cycle of even length.

문제출처

광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 3

Solution

1. (i). Let $P = (x_0, x_1, \dots, x_k)$ be a longest path in $G$. Vertices $x_0$ and $x_k$ are the endpoints of $P$.
2. (ii). Since every vertex in $G$ has degree at least 3, $x_0$, being one of the endpoints of $P$, must have at least two neighbors other than $x_1$, which is already on the path. These neighbors must be other vertices in the path $P$. Otherwise, the path could be extended, which would contradict the assumption that $P$ is the longest path. If $x_0$ had any neighbor not on $P$, we could extend $P$ by including that neighbor, but this would contradict the assumption that $P$ is the longest path.
3. (iii). Let $x_1, x_i, x_j \ (1 < i < j)$ be three distinct neighbors of $x_0$. These vertices are all part of the path $P$. Since $x_0$ has degree at least 3, and two of its neighbors must already be in $P$, we can choose such distinct neighbors within the path.
4. (iv). Consider the cycle that starts from $x_0$, follows the path through $x_1, x_2, \dots, x_i$ and then returns to $x_0$. This cycle is $x_0 - x_1 - \dots - x_i - x_0$, and its length is $i + 1$. If $i$ is odd, then the length of this cycle is even. Hence, we have found an even-length cycle.
5. (v). If both $i$ and $j$ are even, we can consider a different cycle that includes $x_j$. This cycle is $x_0 - x_1 - \dots - x_i - x_{i+1} - \dots - x_j - x_0$. The length of this cycle is $j - i + 2$. Since $j - i$ is even ,-because both $i$ and $j$ are even-, the total length $j - i + 2$ is also even.
6. (vi). Since the length of a cycle does not change regardless of which vertex we start from, the cases based on the parity of $i$ and $j$ are symmetric and equally applicable. Thus, by considering the two main cases where $i$ is odd or both $i$ and $j$ are even, we can guarantee that an even-length cycle exists in every possible configuration.
7. (vii). Therefore, it is proved.