Let Gn be the simple graph with vertex set v0, v1, · · · , vn−1 such that viand vj are adjacent if and only if |j − i| ∈ {4, 5}. Draw the graphs G5 andG6. Determine the number of components of Gn.

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

Solution

(i). G_{5}

(ii). G_{6}

Number of connected components in $G_{n}$ is
$$\begin{cases} n, & \text{if } 0 \leq n \leq 4, \\ 9 - n, & \text{if } 5 \leq n \leq 8, \\ 1, & \text{if } n \geq 9. \end{cases}$$