# Prove that the graph is connected

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.

• Possible duplicate of math.stackexchange.com/questions/927151/… – Bhaskar Vashishth May 4 '15 at 0:36
• @BhaskarVashishth I checked that out, it didn't help me, but thanks. – Csci319 May 4 '15 at 0:47
• Note that, if $n$ is even, the graph is not just connected but, by Dirac's theorem, it has a Hamiltonian cycle. – David Richerby May 4 '15 at 11:33

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$

• thanks! so what are standard formulas that I should I know when I approach questions likes these? – Csci319 May 4 '15 at 0:50
• The only formula I used here was the set theoretic inclusion-exclusion formula for counting stuff in unions/intersections. The main trick used here was to associate "degrees" with "neighbourhoods" and to think about how we could force a common neighbour. This is a standard graph theory trick. – Adriano May 4 '15 at 0:53
• This looks very complicated. Is something wrong with David's/my answer? – Stefan Pochmann May 4 '15 at 4:42
• @StefanPochmann It is precisely the same argument. My approach is direct, whereas yours and David's is by contradiction. – Adriano May 4 '15 at 6:57
• Brilliant answer. On a slightly related note, are there properties that allow one to prove a component of a graph? (Say graph G(V,E), and we want to show that a subset S of V and Q of E form a component of G? Assuming of course that S and Q do represent a connected graph) – user929304 Aug 20 '16 at 14:33

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.

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

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$

• "Isolate any subgraph $S_k$ with $k$ vertices [...]. By induction, $S_k$ is path-connected." – Carsten S May 4 '15 at 8:37
• Because every vertex in $S_k$ has degree at least $k/2$, satisfying the induction hypothesis, i.e., it is a graph on $k$ vertices and at least $(k-1)/2$ edges. What is wrong with that? – Gary. May 4 '15 at 15:39
• My comment was indeed wrong, I apologise. But why is the minimal degree in $S_k$ at least $(k-1)/2$? I only see $(k+1-1)/2 -1 =(k-1)/2 - 1/2$. – Carsten S May 4 '15 at 16:06
• Indeed I can have a graph on $3$ vertices with each vertex of degree $1$ and remove a vertex so that the remaining graph is not connected. – Carsten S May 4 '15 at 16:09
• No problem. Let me double check. – Gary. May 4 '15 at 16:12