I thought it for a long time,but I still do not know how to do it.

1) If we know the degree of the vertices, we can determine: is such graph exist.
2) Write a full search. You will quickly find an answer. You can sent this code and get AC or look at the answer and found a pattern.

1)Havel-Hakimi algorithm
2) Hypothesis(my): sequence n/2 n/2 ... 3 3 2 2 1 1 0 0
realizable for each n
P.S. In timus there is a problem about full search:
monkey aplly full search on keyboard. When it create theorem.

Edited by author 09.10.2010 22:30

svr, your hypothesis is true. It's obvious if we draw the adjacency matrix of these graphs (for even N):

N = 4:
0 0 0 1
0 0 1 1
0 1 0 0
1 1 0 0

N = 6:
0 0 0 0 0 1
0 0 0 0 1 1
0 0 0 1 1 1
0 0 1 0 0 0
0 1 1 0 0 0
1 1 1 0 0 0

N = 8:
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 1 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 0
0 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0