Graph theory (Graph Connectivity)

Question

I'm studying graph theory and got stuck in one of the problems. It's about graph connectivity with specific degree sequence condition. Please help me! Number 3 in original problem image

My Try: Vertex of degree $d_n$ and $d_n$ other vertices which is connected to it by $d_n$ edges form a connected graph of $d_n+1$ vertices. Then a vertice $d_{n-d_n-_1}$ should be also in a component that contains vertice of $d_n$ degree.(Since there are at most $n-d_n-1$ vertices.) I don't know how to progress from here...

Q: Suppose $G$ is simple with degree sequence $d_1\le d_2\le \cdots d_n$, and for $k\le n-d_n-1, d_k\ge k$. Show $G$ is connected.

Answer 1

Let's look at some values of $n$ and $d_n$ and see what is feasible. Note that if $d_n=n-1$ the graph is connected anyway. The threshold value calculated here, $n-d_n-1$, gives the minimum value for $d_1$ according to the problem statement.

$$\begin {array}{|c|c|c|} \hline n & d_n & n-d_n-1 & ?\\ \hline 2 & 0 & 1 & \times\\ \hline 3 & 1 & 1 & \text{all degree 1 }\times\\ \hline 4 & 1 & 2 & \times\\ \hline 4 & 2 & 1 & \text{connected [1]}\\ \hline \ge 4 & n-2 & 1 & \text{connected [1]}\\ \hline \end{array}$$

• Note [1] - when $d_n=n\!-\!2 \ (n\ge 4)$, the highest-degree node connects to all nodes except one; however the minimum degree is $1$ so that node must also connect to one of the other nodes $\to$ connected.

This gives us our clue as to why the conditions given force a connected graph. Given a maximum degree of $n-a$ leaves $a-1$ nodes not directly connected to the maximum degree node, $v_m$. However the threshold degree imposed means that each of these nodes must have degree of at least $n-(n-a)-1 = a-1$, so they must also connect to at least one of the nodes connected to $v_m$. Hence the graph is connected and has diameter of at most $4$.