문제출처
광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4
Solution
1. Let $C_u$ be a connected component of $G$ that contains the vertex $u$ with the maximum degree, and $C_v$ be a connected component of $G$ that contains the vertex $v$ with the minimum degree.
2. I will identify the contradiction that arises when $C_u$ and $C_v$ are disjoint.
3. $d(u)$ is $\lceil n/2 \rceil$, where $d(u)$ is the degree of vertex $u$. Thus, the number of vertices adjacent to $u$ is at least $\lceil n/2 \rceil$. Therefore, the number of vertices in $C_u$ is at least $\lceil n/2 \rceil + 1$.
4. $d(v)$ is $\lfloor n/2 \rfloor - 1$. Thus, the number of vertices adjacent to $v$ is at least $\lfloor n/2 \rfloor$. Therefore, the number of vertices in $C_v$ is at least $\lfloor n/2 \rfloor$.
5. If $C_u$ and $C_v$ are disjoint:
- $|V(G)| \geq |C_u| + |C_v|$ is clear.
- Since $|C_u| \geq \lceil n/2 \rceil + 1$ and $|C_v| \geq \lfloor n/2 \rfloor$,
$$
|C_u| + |C_v| \geq \lceil n/2 \rceil + \lfloor n/2 \rfloor + 1 = n + 1.
$$
6. Since $n + 1$ is greater than $n$, the total number of vertices in $G$, this is a contradiction.
7. Therefore, $C_u$ and $C_v$ must have a common vertex. Thus, $C_u = C_v$.
8. By the same logic, for any vertex $w$ in $G$, $C_u = C_w$. Thus, there exists only one connected component in $G$, and $G$ is connected.