Prove that the graph is connected

Question

I was wondering if someone can help me understand how prove that this graph is connected.

Given a graph with n vertices, prove that if the degree of each vertex is at least $(n − 1)/2$ then the graph is connected.

So far I know that about connected graphs:

An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph

The distance between two vertices in a graph is the length of the shortest path between them.

The diameter of a graph is the distance between the two vertices that are farthest apart.

---

Answer 1

Call the $n$-vertex graph $G$. Choose any two vertices $u,v \in V(G)$. We want to find a $(u,v)$-path. Now if $u = v$ or $uv \in E(G)$, then we are done. So we may assume that $u \neq v$ and $uv \notin E(G)$. We will prove the stronger claim that there is some path of the form $u \to w \to v$ for some $w \in V(G)$.

Consider the neighbourhoods of each endpoint: \begin{align*} A &= \{a \in V(G) \mid ua \in E(G)\} \\ B &= \{b \in V(G) \mid vb \in E(G)\} \end{align*} It suffices to show that these neighbourhoods overlap (if they do, then we can just pick any $w \in A \cap B$ and we are done). Indeed, observe that: \begin{align*} |A \cap B| &= |A| + |B| - |A \cup B| \\ &= \deg(u) + \deg(v) - |A \cup B| \\ &\geq \frac{n - 1}{2} + \frac{n - 1}{2} - (n - 2) \\ &= 1 \end{align*} Hence, we conclude that $A\cap B \neq \varnothing$, as desired. $~~\blacksquare$

Answer 2

Proof:

If each degree is at least that, then each component has at least one vertex and $\frac{n-1}{2}$ others, so at least $\frac{n-1}{2}+1=\frac{n+1}{2}$ vertices. Two components would have at least twice as many vertices, which is n+1, more than the graph has.

(I realize this is the same as David's, but I don't like unnecessary variables so I feel it's still worth posting.)

Edit: Different wording, appropriate for the OP's stated terminology/knowledge:

Alternative proof:

Take any two vertices. Each has at least $\frac{n-1}{2}$ neighbors. If there were no path between our two vertices, then the two neighborhoods must be separate and we'd have at least $2\cdot(1+\frac{n-1}{2})=n+1$ vertices, more than the graph has.

Answer 3

suppose the graph has at least two distinct connected components, $C_1$ and $C_2$. denote by $c_1,c_2$ two vertices, one in each component.

$C_1$ has the vertex $c_1$ and at least $\frac{n-1}2$ other vertices, one for each edge incident to $c_1$, a total of at least $\frac{n+1}2$. likewise $C_2$ must have at least $\frac{n+1}2$ vertices.

the graph must therefore have at least $$ \frac{n+1}2 + \frac{n+1}2 = n+1 $$ vertices, contradicting the assumption

Answer 4

I think this can be done by induction on the number of vertices: this is trivially true for $n=1,2$. Assume true for $n=k$, i.e., every graph on $k$ vertices where each vertex has degree $\geq (k-1)/2 ; k>2 $ ,is path-connected.

Now consider a graph $S_{k+1}$ on $k+1 $ vertices. Isolate any subgraph $S_k$ with $k$ vertices, and define $v_{k+1}:= S_{k+1}-S_k$, i.e., $v_{k+1}$ is just the vertex of $S_k$ thatis not in $S_{k+1}$ (EDIT : ignore edges out of/into $v_{k+1})$ . By induction, $S_k$ is path-connected. We know $Deg(v_{k+1}) \geq (k+1-1)/2=k/2 $. But now we just need $Deg(v_{k+1}) \geq 1 $ . Now join $v_{k+1}$ with any $v_j ; j \neq k+1$, which gives you, by path-connectedness of $S_k$ a path between $v_{k+1}$ and $v_j$; $k+1 \neq j$.

EDIT Alternatively, consider a path-connected graph on $k-1$ vertices, with $Deg(v_j) \geq (k-1)/2$ . Throw in a new vertex $v_{k+1}$ and draw and edge between $v_{k+1}$ and every other edge, and you have a path-connected graph with $Deg(v_j)=(k-1)/2+1 =(k+1)/2 \geq k/2$