  Let G be a simple graph without isolated vertices. For a vertex i in G, the
degree d_i is the number of vertices adjacent to i and the average 2-degree m_i
is the mean of the degrees of the vertices which are adjacent to i. The
sequence of pairs (d_i, m_i) is called the sequence of degree pairs of G. We
provide some necessary conditions for a sequence of real pairs (a_i, b_i) of
length n to be the degree pairs of a graph of order n. A graph G is called
pseudo k-regular if m_i=k for every vertex i while d_i is not a constant. Let
N(k) denote the minimum number of vertices in a pseudo k-regular graph. We
utilize the above necessary conditions to find all pseudo 3-regular graphs of
orders no more than 10, and all pseudo $k$-regular graphs of order N(k) for k
up to 7. We give bounds of N(k) and show that N(k) is at most k+6.
