Is a graph simple, given the number of vertices and the degree sequence? Does there exist a simple graph with five vertices of the following degrees?
(a) 3,3,3,3,2
I know that the answer is no, however I do not know how to explain this.
(b) 1,2,3,4,3
No, as the sum of the degrees of an undirected graph is even.
(c) 1,2,3,4,4
Again, I believe the answer is no however I don't know the rule to explain why.
(d) 2,2,2,1,1
Same as above.
What method should I use to work out whether a graph is simple, given the number of vertices and the degree sequence? 
 A: The answer to both a, and d, is that in fact such graphs exit. It is not hard to find them.
The answer for c is that there cannot be such a graph - since there are 2 vertices with degree 4, they must be connected to all other vertices. Therefore, the vertex with degree one, is an impossibility.
A: (a) 3,3,3,3,2   - YES!  Graph Justifies claim
(b)1,2,3,4,3   - NO -Follows from the Handshaking Lemma
(c)1,2,3,4,4   - ANYBODY? (has no problem by Handshaking Lemma)
(d)2,2,2,1,1  - YES! Graph Justifies Claim
A: See http://en.wikipedia.org/wiki/Degree_%28graph_theory%29 or google for "degree sequence". I have only seen Havel-Hakimi theorem before, but wikipedia also mentions other results.
A: a.) Apply Havel-Hakimi:
$$
\begin{align}
& 3,3,3,3,2 \\
\to & 0,2,2,2,2 \\
\to & 2,2,2,2
\end{align}
$$
Since the sequence $2,2,2,2$ is graphic (it is the degree sequence of $C_4$), then the original sequence is graphic. 
c.) Reorder and apply Havel-Hakimi:
$$
\begin{align}
& 4,4,3,2,1 \\
\to & 0,3,2,1,0 \\
\to & 3,2,1
\end{align}
$$
Since the sequence $3,2,1$ is not graphic (a graph on 3 vertices can have maximum degree of 2), then the original sequence is not graphic. 
d.) Apply Havel-Hakimi:
$$
\begin{align}
& 2,2,2,1,1 \\
\to & 0,1,1,1,1 \\
\to & 1,1,1,1
\end{align}
$$
Since the sequence $1,1,1,1$ is graphic (it is the degree sequence of $K_2+K_2$), then the original sequence is graphic. 
A: You can use the Handshaking lemma and the Havel-Hakimi algorithm to solve these problems.  Here is a link to a powerpoint on it.
Basically, it goes like this (using the degree sequence [3 2 2 1] as an example):


*

*If any degree is greater than or equal to the number of nodes, it is not a simple graph.

*Handshaking lemma: if the number of vertices with odd degrees is odd, it is not a simple graph.

*Order the degree sequence into descending order, like 3 2 2 1

*Remove the leftmost degree: 2 2 1 , and call the first degree k, so k=3 here

*Subtract 1 from the leftmost k degrees: 1 1 0

*If any of the degrees are negative, it is not a simple graph.

*Go back to step 3 and repeat 3-7 until we find it is not a simple graph, or all degrees are 0, or we reach another situation we know it is a simple graph (like a cycle with 2 2 2 ...).


In the case of 3 2 2 1, we would do it like this
3 2 2 1
2 2 1 <- intermediate step (4), do not apply the handshaking theorem here yet
1 1 0 <- after step 5; this is a simple graph, so we stop here and find that 3 2 2 1 is a simple graph.
(a)
So for your (a), it would be
3 3 3 3 2 <- looks good through steps 1 and 2
3 3 3 2 <- step 4
2 2 2 2 <- step 5, subtract 1 from the left 3 degrees.  Now we have a cycle, which is a simple graph, so we can stop and say 3 3 3 3 2 is a simple graph.  Or keep going:
2 2 2
1 1 2
1 1
0 0 <- everything is a 0 after going through the full Havel-Hakimi algo, so yes, 3 3 3 3 2 is a simple graph.
(c)
4 4 3 2 1
4 3 2 1
3 2 1 0 <- looks good after one iteration through havel-hakimi
2 1 0
1 0 -1 <- negative degrees aren't possible, so we know that 4 4 3 2 1 is not a simple graph.
(d)
you should be able to draw (d) pretty easily.  2 vertices connected as a pair, and 3 in a cycle.
