6
$\begingroup$

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.


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

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$

$\endgroup$
  • $\begingroup$ thanks! so what are standard formulas that I should I know when I approach questions likes these? $\endgroup$ – Csci319 May 4 '15 at 0:50
  • 2
    $\begingroup$ 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. $\endgroup$ – Adriano May 4 '15 at 0:53
  • $\begingroup$ This looks very complicated. Is something wrong with David's/my answer? $\endgroup$ – Stefan Pochmann May 4 '15 at 4:42
  • $\begingroup$ @StefanPochmann It is precisely the same argument. My approach is direct, whereas yours and David's is by contradiction. $\endgroup$ – Adriano May 4 '15 at 6:57
  • $\begingroup$ 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) $\endgroup$ – user929304 Aug 20 '16 at 14:33
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ "Isolate any subgraph $S_k$ with $k$ vertices [...]. By induction, $S_k$ is path-connected." $\endgroup$ – Carsten S May 4 '15 at 8:37
  • $\begingroup$ 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? $\endgroup$ – Gary. May 4 '15 at 15:39
  • $\begingroup$ 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$. $\endgroup$ – Carsten S May 4 '15 at 16:06
  • $\begingroup$ 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. $\endgroup$ – Carsten S May 4 '15 at 16:09
  • $\begingroup$ No problem. Let me double check. $\endgroup$ – Gary. May 4 '15 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.