How can I prove that a graph with a required amount of edges per node is invalid?

Question

For the following example I assume that no node may be connected to itself.

Nodes: A, B, C, D, E

Required amount of edges per node:

• d(A) = 2
• d(B) = 3
• d(C) = 2
• d(D) = 3
• d(E) = 3

I determined by trial and error and drawing the graph that it is not valid, because there is one edge too less, but if I increase d(E) = 3 to d(E) = 4 I can draw the graph.

What I am looking for here is a way to argue why the graph in the example is invalid.

Answer 1

In general this is fairly interesting (although solved). The Erdős–Gallai theorem gives necessary and sufficient conditions for there to exist a graph whose vertices have specified degrees, and the Havel-Hakimi algorithm is an algorithm for efficiently determining whether the conditions are satisfied.

In your case it's simpler, because one of the conditions of the Erdős–Gallai theorem is the very easy condition that the sum of the degrees must be an even number; since the sum in your example is 13 it's immediately clear that there is no graph with these degrees. To see this, count the number of edges that touch each vertex. This adds up to 13, but since we counted each edge exactly twice, there must be exactly $\frac{13}2$ edges, which is impossible.

Answer 2

In this case it's simple: the sum of the grades must be even for the Handshaking Lemma.

In general, there's a rule for deciding if a sequence of numbers is a grafic sequence, that is, there exists a graph whit that sequence as the degree sequence of his nodes: general rule