A simple graph with degree greater than equal to $\dfrac{n-1}{2}$ then $G$ is connected. Then I thought that the vertices must be greater than or equal to $4$. That can be disconnected.
2026-03-28 11:54:07.1774698847
Show by means of an example that the condition degree greater than or equal to $\frac{n-1}{2}$ for a simple graph G need not imply that G is connected
505 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
We may assume the graph is $K_a \cup K_{n-a}$ for some $a \in \{1,\ldots,n-1\}$. (Otherwise we can add edges without connecting the graph, and without decreasing the vertex degrees.)
By definition, $K_a \cup K_{n-a}$ has minimum degree $\min(a-1,n-a-1)$, which is maximized when $a=\lfloor n/2 \rfloor$. Thus, an $n$-vertex disconnected graph has minimum degree at most $\lfloor n/2 \rfloor-1$.
This suffices to prove the claim in the question:
Since $\lfloor n/2 \rfloor-1$ is strictly less than $(n-1)/2$, there are no examples of disconnected $n$-vertex graphs with minimum degree $(n-1)/2$.
The closest we can get is $K_a \cup K_a$, such as
which has $6$ vertices and minimum degree $2$, and $K_a \cup K_{a+1}$, such as
which has $7$ vertices and minimum degree $2$.