Prove or disprove: If G is an n-vertex simple graph with maximum degree ⌈n/2⌉ andminimum degree ⌊n/2⌋ − 1, then G is connected.

문제출처

광주과학기술원(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.