For a simple graph G, prove that G is a cycle iff every vertex has degree 2.

문제출처

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

Solution

1. Necessary condition: If $G$ is a cycle, then every vertex in $G$ has degree 2.
   • (a). A cycle is a simple path that starts and ends at the same vertex. Every vertex is visited exactly once.
   • (b). In a cycle, each vertex is connected to exactly two other vertices: one edge connects to the previous vertex in the cycle, and one edge connects to the next vertex in the cycle.
   • (c). Thus, every vertex has degree 2.
2. Sufficient condition: If every vertex in $G$ has degree 2, then $G$ is a cycle.
   • (a). Assume that every vertex in $G$ has degree 2.
   • (b). Start at an arbitrary vertex $v$ in $G$.
   • (c). Follow the path starting at $v$. Since each vertex has degree 2, we always proceed to the next vertex.
   • (d). This process must eventually revisit a vertex - as $G$ is finite- .
   • (e). The first revisited vertex must be $v$ itself. If we revisit another vertex $u$ first, $u$ would have degree at least 3, contradicting our assumption.
   • (f). The path formed is a cycle, as it starts and ends at $v$ without repeating any other vertices.
   • (g). This cycle must include all vertices of $G$. If not, the remaining vertices would form one or more separate cycles (as they all have degree 2), contradicting the assumption that $G$ is connected.
   • (h). Therefore, for a simple connected graph $G$, $G$ is a cycle if and only if every vertex has degree 2.