1
$\begingroup$

For example, why is the degree sequence 3,3,1,1 not possible? I said because there are only 4 vertices and if two of them have degree 3 then the other 2 must have degree 2. Is this "proving it"? What else can be said in these types of questions to be more convincing?

$\endgroup$
  • 2
    $\begingroup$ What you said seems convincing enough for me. In general though, degree sequences can be determined to be valid or invalid through theorems like Havel-Hakimi or Erdős-Gallai. $\endgroup$ – EuYu Dec 14 '13 at 11:14
  • 1
    $\begingroup$ If self-edges (loops) are allowed, then the degree sequence $3,3,1,1$ can be attained. Conventionally a self-edge is counted twice for the degree of its vertex, as this interpretation preserves the handshaking lemma that the sum of degrees is twice the number of edges. $\endgroup$ – hardmath Dec 14 '13 at 13:59
1
$\begingroup$

While what you said was clear and convincing, one method to make the argument more concrete is to represent any possible graph by an adjacency matrix that attains the given degrees.

As your Question implicitly frames it, the degree sequence can be ordered arbitrarily, and thus sorting it is a convenient starting point. Any adjacency matrix would be $4\times 4$ with binary entries ($0$s and $1$s), symmetric (for undirected graphs), and have only $0$s on the diagonal (no self-edges in simple graphs).

Taking the first row/column to represent a vertex of degree $3$, we would have this:

$$ \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & ? & ? \\ 1 & ? & 0 & ? \\ 1 & ? & ? & 0 \end{bmatrix} $$

But as your argument notes, we are obstructed when we try to make the next vertex have degree $3$, because filling in those entries forces the two remaining vertices to have degree (at least) $2$:

$$ \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & ? \\ 1 & 1 & ? & 0 \end{bmatrix} $$


A different approach to proving the nonexistence of a graph with this degree sequence would be to count the edges, $|E|$, which must be half the sum of all the degrees. That is, $|E|=4$ if the degrees add up to $8$ as they would here.

Now the complete graph $K_4$ on four vertices only has six edges, so we can picture starting with that and removing two edges, which would either be two connected edges or two unconnected edges. The first choice leaves a degree sequence $3,2,2,1$, and the second leaves a degree sequence $2,2,2,2$. Since neither choice gives us what we want, we get what we need!


Also, as @EuYu points out in a Comment, the Erdős–Gallai theorem restricts the possible degree sequences and can be applied here to exclude the possibility of $3,3,1,1$.

To be realized as the (descending) degrees of a simple graph, nonnegative integers $d_1 \ge d_2 \ge \ldots \ge d_n$ must satisfy for each $1 \le k \le n$:

$$ \sum_{i=1}^k d_i \le k(k-1) + \sum_{i=k+1}^n \min(d_i,k) $$

In particular for our target degree sequence with $k=2$, $d_1 + d_2 = 6$ but:

$$2(2-1) + \min(1,3) + \min(1,4) = 4$$

and the necessary condition fails.

$\endgroup$

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.