# 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?

-

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.

-
I don't understand what you mean by "subdivide so edges." Can you elaborate a bit please? – K-RAN Feb 3 '11 at 19:40
If one places a dot on an edge in a drawing of a graph then one gets a new 2-valent (degree 2) vertex. One can do this on several edges, and now join up these these new degree 2 vertices so make all the new vertices have degree 4. – Joseph Malkevitch Feb 3 '11 at 21:32
Given n = 5, we get K5. Using the method that you described, 3 vertices had to be created, or I could just place 1 vertex on the intersection of 2 of the edges. Pardon my slowness, but I have no idea what this implies... – K-RAN Feb 4 '11 at 0:18
So you see a way to get a 4-valent graph with 8 vertices from one with 5 vertices. You also described how to a get a graph with 6 vertices which is 4-valent from one which has 5 vertices. So how about repeating these "operations" somehow on the larger graphs you now have constructed and see what values of n you can get which have larger and larger values for the numbers of their vertices but always have only vertices of degree (valence) 4? – Joseph Malkevitch Feb 4 '11 at 1:58

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).

-

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 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$.

-
If this is a theorem, I can't use it because I have not learned it yet. Thanks for the suggestion though! – K-RAN Feb 3 '11 at 19:39
This is called the Erdos-Gallai theorem. See en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem. – Srivatsan Jul 24 '11 at 8:07