4
$\begingroup$

this is the exercise:

If possible draw a graph with 15 vertices having
3 vertices with degree 4;
4 vertices with degree 3;
6 vertices with degree 2;
0 vertices with degree greater than the ones of the above.

This is the graph I have done by myself:
Graph of 15 vertices

my questions are,

the graph I have done is right?

and also, since in the given exercise we have the number of vertices and the degree of some of them, is there exists any theorem or algorithm that says to us if a graph with a certain configuration is possibie to draw? It is labourious sometimes to try to draw a graph going by attempts, and without any certainty of its existance.

Can you help me? Thanks!

$\endgroup$
3
$\begingroup$

Your example is correct. The Havel–Hakimi algorithm is an effective procedure for determining whether a given degree sequence can be realized (by a simple graph) and constructing such a graph if possible.

P.S. In a comment you ask if the algorithm works for trees. In general, if we apply the Havel–Hakimi algorithm to the degree sequence of a tree, the output graph will not necessarily be a tree; for example, $3,3,3,1,1,1,1,1$ is the degree sequence of a tree, but the algorithm does not produce a tree. However, the algorithm can easily be adapted so as to produce a tree whenever that is possible.

Let $d_1,\dots,d_n$ be a sequence of nonnegative integers, $n\gt1.$ If some $d_i=0$ then it's not the degree sequence of a tree, because a tree (with more than one vertex) can't have an isolated vertex. Hence we may assume that all $d_i$ are positive. Moreover, we may assume that $d_1+\cdots+d_n=2(n-1),$ otherwise it can't be the degree sequence of a tree.

Let $G$ be the output of the Havel–Hakimi algorithm. The graph $G$ has $n$ vertices and $n-1$ edges. If it is not already a tree, then it has at least two components, at least one of which is not a tree. Let $H_1,H_2$ be two components of $G,$ and suppose that $H_2$ is not a tree. Let $uv$ be any edge of $H_1,$ and let $xy$ be an edge of $H_2$ which lies on a cycle, so that $H_2-xy$ is connected. If we delete the edges $xy$ and $uv$ and replace them with edges $xu$ and $yv,$ the resulting graph $G'=G-xy-uv+xv$ has the same degree sequence as $G$ but one less component. Repeat this construction until we get a graph with the same degree sequence but just one component, i.e., a tree.

$\endgroup$
  • $\begingroup$ once completed this algorithm, reading from end to beginning, step by step, is it possible to draw a graph? $\endgroup$ – JB-Franco Feb 14 '17 at 1:11
  • $\begingroup$ With the Havel–Hakimi algorithm, at each step you choose a vertex and draw some edges. If the input sequence is not "graphic" (meaning there is no simple graph with the given degrees), then at some point it will be carry out the next step. If the sequence is graphic, the algorithm will produce a graph with the given degree sequence. $\endgroup$ – bof Feb 14 '17 at 1:20
  • 1
    $\begingroup$ Note that the Havel–Hakimi algorithm is quite different from the Erdős–Gallai theorem described in the other answer. The Erdős–Gallai gives you a yes/no answer but does not show you how to construct the graph. $\endgroup$ – bof Feb 14 '17 at 1:22
  • $\begingroup$ in every step, different from the last, I have to add a vertex. $\endgroup$ – JB-Franco Feb 14 '17 at 1:46
  • 1
    $\begingroup$ I'm editing my answer to include a discussion of trees. $\endgroup$ – bof Feb 14 '17 at 3:56
3
$\begingroup$

The theorem concerning existence you are interested in is probably the following comprehensive result for simple graphs (no loops or multi edges): https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem. There is also an algorithmic approach, which another answer addresses, but if what you are after is a sanity check before you start trying to realize the degree sequence with a graph, then Erdos-Gallai should help. I would just write a simple program to use the theorem as a verifier for a given sequence. (A possible python implementation is given at the bottom)

But we can also verify by hand of course. In your case, the conditions given determine your degree sequence to be: $$(4,4,4,3,3,3,3,2,2,2,2,2,2,x,y)$$ where $x \geq y$ and $x,y \in \{0,1\}$. As you can see from your own work, $(x,y)$ could be $(1,1)$ or $(0,0)$. But the handshake lemma shows that $(1,0)$ is not possible (sum of degree sequence must be even).

Let's work with your sequence, $$(4,4,4,3,3,3,3,2,2,2,2,2,2,1,1)$$. First of all, the handshake lemma checks out because the sum of the degree sequence is even.

The partial sums of your degree sequence are $$(4,8,12,15,18,21,24,26,28,30,32,34,36,37,38)$$ The sequence $(k(k-1))$ for $k=1\ldots n$ is $$(0,2,6,12,20,30,42,56,72,90,110,132,156,182,210)$$ The $\sum\limits_{i=k+1}^{n}\min(d_i,k)$ summation yields the sequence: $$(14, 24, 26, 23, 20, 17, 14, 12, 10, 8, 6, 4, 2, 1, 0)$$ Summing the previous two sequences we see that that the RHS sequence in the theorem is $$(14, 26, 32, 35, 40, 47, 56, 68, 82, 98, 116, 136, 158, 183, 210)$$ Which is everywhere greater than the LHS sequence of partial sums of the degree sequence $$(4,8,12,15,18,21,24,26,28,30,32,34,36,37,38)$$ This verifies that a graph exists satisfying your degree sequence, which you now know because you constructed just such a graph!

Possible Python implementation of the code: def erdos_gallai(ds): n = len(ds) lhs = reduce(lambda c, x: c + [c[-1] + x], ds, [0])[1:] rhs1 = [k*(k-1) for k in range (1, n+1)] rhs2 = [sum([min(ds[i], k+1) for i in range (k+1, n)]) for k in range (0,n)] for i in range (n): if lhs[i] > rhs1[i] + rhs2[i]: return False return True

$\endgroup$
  • $\begingroup$ Sorry I don't understand the summation $\sum\limits_{i=k+1}^{n}\min(d_i,k)$. For example: if $k=1), min(d_2,1) = min(4,1) = 1$ if $k = 2), min(d_2,1) + min(d_3,2) = min(4,1) + min(4,2) = 1 + 2 = 3$ from what springs that $14$? $\endgroup$ – JB-Franco Feb 13 '17 at 23:44
  • 1
    $\begingroup$ Note that $k$ stays fixed over the summation ($i$ varies). For $k=1$, the summation is $\sum\limits_{i=2}^{15}\min(d_i, 1)=\min(d_2, 1) + \min(d_3, 1) + \ldots + \min(d_{15},1)$. Since $d_i \geq 1$ for all $i$, this is just $\sum\limits_{i=2}^{15} 1 = 14$ $\endgroup$ – Badam Baplan Feb 14 '17 at 2:44
  • $\begingroup$ The degree sequence could also be $(4,4,4,3,3,3,3,2,2,2,2,2,2,0,0)$. That graph is also feasible. $\endgroup$ – Joffan Feb 14 '17 at 6:05
  • $\begingroup$ Oh definitely, good point. For some reason I thought the question stipulated $0$ vertices with degree $0$. $\endgroup$ – Badam Baplan Feb 14 '17 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.