Proving that every graph $G$ with $\delta (G)\geq 2$ is degree-equivalent to a connected graph

228 Views Asked by At

Let $G$ be a graph on $\left \{v_1, ... , v_n \right \}$ with minimum degree at least $2$.

Prove that there is a connected graph $Q$ (on the same vertex set) so that $d_G(v_i)=d_Q(v_i)$ for every $1\leq i \leq n $ (same degree-sequence).

I've thought about using induction on $n$, but I can't really think of how it's done. How can one remove a vertex, still making sure that the new graph still has minimum degree at least 2?

Suggestions will be welcomed. Thank you!

1

There are 1 best solutions below

0
On BEST ANSWER

Hint: Induction on the number of connected components in the graph.

Note that "minimum degree at least 2" implies that every connected component contains a cycle.