I have to prove that all sequences with length $n > 4$, contain only number $4$, are degree sequence.
So my sequence is: $\underbrace{4,4,4,\ldots,4}_{n\text{ times}}$.
I am new in graph theory. Maybe I can use mathematical induction with Havel-Hakimi algorithm, but I don't know how.
I guess an elegant proposition would be to look at Hamiltonian cycles of a complete graph. What we know is that complete graph $K_n$ has $\frac{n-1}{2}$ separate (in a sense that there is no edge contained in both cycles) Hamiltonian cycles: How many Hamiltonian cycles are there in a complete graph $K_n$ ($n\geq 3$) Why? That means that e.g. $K_5$ has two separate Hamiltonian cycles, and each $K_n$ for $n \geq 5$ has at least two such cycles. Now let's take a complete graph $K_n$ and remove all the edges that are not contained in any of two selected cycles. What we are left with is a $4$-regular graph, as the two cycles were separate. We can do this for any $n \geq 5$, so for any $n \geq 5$ there exists a connected graph having degree sequence $(4, \dots, 4)$
It’s not too hard to construct explicit examples.
$K_5$ takes care of $n=5$. For $n=2m$ with $m\ge 3$ we can construct a $4$-regular graph $G_n$ as follows. Let the vertices of $G_n$ be $u_1,u_2,\ldots,u_m, v_1,v_2,\ldots,v_m$. Start with the edges are $\{u_k,u_{k+1}\}$ and $\{v_k,v_{k+1}\}$ for $k=1\ldots,m-1$, $\{u_m,u_1\}$, $\{v_m,v_1\}$; this produces two disjoint $m$-cycles. Now add the edges $\{u_k,v_k\}$ for $k=1,\ldots,m$ to get a prism graph. Finally, add the edges $\{u_k,v_{k+1}\}$ for $k=1,\ldots,m-1$ and $\{u_m,v_1\}$.
It only remains to construct $4$-regular graphs $G_{2m+1}$ for $m\ge 3$. Start with $G_{2m}$ as just constructed; add a vertex $w$, remove the edges $\{u_1,v_2\}$ and $\{u_2,v_3\}$ from $G_{2m}$, and add edges $\{w,u_1\}$, $\{w,u_2\}$, $\{w,v_2\}$, and $\{w,v_3\}$, and you’re done.
Arrange your $n$ vertices in a circle and connect each one to its four closest neighbors.
