Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I read this statement related to Havel and Hakimi.

Suppose that $\textbf{d}=(d_1,d_2,\ldots,d_n)$ be a nonincreasing sequence of nonnegative integers. Let $\textbf{d'}=(d_2-1,d_3-1,\ldots, d_{d_1+1}-1,d_{d_1+2},\ldots,d_n)$. Then $\textbf{d}$ is graphical if and only if $\textbf{d'}$ is graphical.

Why is this the case? For suppose $G$ is the graph associated to the first sequence. It seems the the second sequence is obtained by removing the vertex $v_1$ from $G$, which induces a subgraph by deleting all $d_1$ edges adjacent to $v_1$, and this would decrease the degree of $d_1$ vertices, giving a graph $G'$ with the second degree sequence. But this argument seems to assume that $v_1$ is connected to the next $d_1$ vertices of highest degree. What is $v_1$ is adjacent to $v_n$ or any $v_k$ for any $k>{d_1+1}$? Why would the claim still be true? Thank you.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Both the statement in the question and a little don's answer seem to rely on the following theorem:

If a sequence $d$ is graphic, then there is a graph with degree sequence $d$ such that a vertex with highest degree is adjacent to $d_1$ vertices whose degrees are greater or equal to the degrees of the remaining vertices.

Let a graph with degree sequence $d$ be given, and let $v_1$ be a vertex with highest degree. If there are vertices $v_2$ and $v_3$ such that $v_2$ has higher degree than $v_3$ but $v_1$ is connected to $v_3$ and not to $v_2$, then choose any edge incident to $v_2$ but not to $v_3$. (There is one, since the degree of $v_2$ is greater than that of $v_3$.) Let $v_4$ be the vertex it leads to, with $v_4\neq v_3$ and $v_4\neq v_1$ by construction. Now replace the edges $(v_1,v_3)$ and $(v_2,v_4)$ by the edges $(v_1,v_2)$ and $(v_3,v_4)$. This leaves all degrees invariant. Now $v_1$ is adjacent to $v_2$ as required. Since we have increased the sum of the degrees of the vertices adjacent to $v_1$ and that sum is bounded, we can only perform this operation (with the same $v_1$ but varying $v_2$ to $v_4$) finitely many times, so this will necessarily construct the desired graph.

share|improve this answer

Don't think of it as removing, think of it as adding. We know there is a graph for this:

$\textbf{d'}=(d_2-1,d_3-1,\ldots, d_{d_1+1}-1,d_{d_1+2},\ldots,d_n)$ so if we add $d_1$ and connect it to the first $d_1$ elements we have:

$\textbf{d}=(d_1,d_2,\ldots,d_n)$ which will also be a graphical.


Working in the other direction. Begin by putting dots on your paper for each vertex, write the desired degree by each dot. Now, to test if these assignments are graphical start with the vertex of highest degree, connect it to the next $d_1$ vertices of highest desired degree. Now update the numbers so they reflect how many more edge connections each vertex needs. (That is, subtract 1 from the $d_1$ vertices of next highest degree.) Again start with the vertex with the greatest 'need' and connect... repeat.

Either you will create an example of a graph that matches your degree sequence... or it will fail and the sequence is impossible.

This process is the same idea as the theorem.

share|improve this answer
    
Thanks a little don, I'll experiment with this. –  Hobbie Apr 22 '11 at 5:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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