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:
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!
Best Answer
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.