threshold graph and degree sequence proof

Question

$\textbf{Definition:}$ $G$ is a threshold graph if and only if $G$ can be constructed from the one-vertex graph by repeatedly adding an isolated vertex or a dominating vertex.

I am trying to prove the following problem:

Let $d$ = $\{d_1 \geq \cdots \geq d_n \}$ be a degree sequence and define, $r_i = \max\{j : d_j \geq i\}$ and $f = \max\{j : d_j \geq j\}$. Prove that $d$ is a degree sequence of a threshold graph if and only if $r_i = d_i + 1$ for $i=1,\ldots,f$.

I think the overall idea would be to show that if $r_i$ is as claimed, then $d$ must be a degree sequence of a threshold graph because the pattern represents the recursive construction of a threshold graph. And then prove the converse.

I would appreciate some help. Thank you.

Answer 1

One approach would be a careful induction proof. A threshold graph has a recursive structure: it's a smaller threshold graph, with either a dominating vertex or an isolated vertex added on. So you can try to prove that:

1. One of the following holds:
   • The vertex with degree $d_1$ is a dominating vertex, or
   • The vertex with degree $d_n$ is an isolated vertex.
2. If you delete the vertex found in step 1, then the degree sequence of the remaining graph continues to satisfy the condition in the problem.