Proving That A Degree Sequence is Graphical (Havel-Hakami) I've been thinking about this particular problem and I'm stumped.
For all $n g\geq 5$, show that there exists a graph, $G = \langle V,E \rangle$ such that all vertices of $V$ have degree of $4$.
I've tried using Havel-Hakami with a degree sequence of n-fours (ie: $[4,4,4,4,4,4,\ldots]$), but there were too many cases. I can't think of anything else. Any suggestions or ideas?
 A: Try drawing a physical diagram of such a graph (all vertices of degree (valence) 4) on a piece of paper. Now see if you can subdivide some edges with new vertices and adjust all these new verrtices to have degree 4. How many new vertices did you need to add? So now, what would you have to do to guarantee that you could find a collection of graphs with all longer sequences of only 4's? This approach should avoid too many cases.
A: A degree sequence $\{d_1, \dots, d_n \}$ is graphical iff the sum of the vertex degrees is even and $$ \sum_{i=1}^{r} d_i \leq r(r-1) + \sum_{i=r+1}^{n} \min(r, d_i)$$
for each integer $r \leq n-1$. So $4r \leq r(r-1)+4(n-r)$. So there exists a graph of order $n \geq 5$ which has all vertices of degree $4$.
A: In general, if $r$ is an even integer such that $r \geq 0$, then for all $n > r$, there exists a graph of order $n$ whose every vertex has degree $r$. This is called an $r$-regular graph of order $n$.
We use what are known as Harary graphs to prove this.
Without getting into too much technical detail: visualize the $n$ vertices of the graph to be in a circular layout, and think of each vertex as adjacent to the $r/2$ vertices "ahead" of it and the $r/2$ vertices behind it. Then, each vertex has degree $r$. 
A: Another answer similar in spirit to Joseph Malkevitch's answer but simpler (in my opinion).
Proof by induction on $n$.  For $n=5$, the graph is $K_5$. Now assume that there exists a 4-regular graph on $n-1 \ge 5$ vertices.  Pick two edges not incident to the same vertex.  (It is easy to see that such edges exists since $n-1 \ge 5$.)  "Cut" these two edges to make 4 dangling edges and connect them to a new vertex (which now has degree 4).
