1
$\begingroup$

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?

4 Answers 4

2

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.

  • 0
    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?2011-02-04
2

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

  • 0
    This is called the Erdos-Gallai theorem. See http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem.2011-07-24
2

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

1

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

  • 0
    Actually this argument settles the problem!2018-08-08